On Cayley Graphs: Part 2
In the previous post, we were left with the construction of graph $\Gamma$ from group $G$ with a promise to transform the graph into a metric space. A metric space consists of vertices together with edges. Each edge is assumed to have a length of $1$. Let's denote the given space $X$. As for metric, we first define a distance between two vertices. A distance between two vertices $h,k$ corresponds to the length of the shortest path between them. Formally:
\[
d(g,h) = \min\{n\mid g^{-1}h = s_1s_2\ldots s_n \},\quad s_i\in S
\]
As for points on the edges, the distance defined similarly with consideration that each point should first travel to one of its two neighboring vertices. With this metric, $X$ or $Cay(G,S)$ becomes a metric space and referred to as Cayley graph of $G$ with respect to $S$. We can say few things about $X$ immediately. Firstly, $X$ is a proper metric space, i.e. its closed balls are compact. Secondly, $X$ is a geodesic metric space, i.e. there is a shortest path connecting any two points.
Time for action Let us now consider an action of $G$ on $X$. Let us define an action $\phi:G\to Aut(X)$ such that $\phi_g(x) = gx$ if $x$ is a vertex. As edges, a point lying between vertices $(h,k)$ maps into a point lying between $(gh,gk)$ so that corresponding distances are preserved. For the sake of convenience, we identify an action $\phi_g$ with $g$. This action enjoy following properties. Firstly, each action is an isometry. Indeed $d(h,k) = d(gh,gk)$, for a reason that actions correspond to left multiplication, whereas distances were defined using right multiplication of elements.
Secondly, this action is proper. Properness has to do with sparsity of orbit points. It tells: for any $x\in X$ and any ball $B\subset X$ there are only finitely many $g\in G$ such that $gx\in B$. One immediate implication of properness is lack of accumulation points in the orbit of $x\in X$. Thirdly, this action is cobounded. Coboundedness roughly corresponds to omnipresence of orbit points. It tells: there is a ball $B\subset X$ whose $G$-translates cover the whole $X$, i.e. $G\cdot B = X$. Equivalently, there is $x\in X$ and $r\in \mathbb{N}$ such that for all $y\in X$ there is $g\in G$ such that $d(x,gy)<r$.
Examples: Let us give some examples of Cayley graphs.
1. $G = \mathbb{Z}$, the $Cay(G,\{\pm1 \})$ is isomorphic to real line, $\mathbb{R}$;
2. $G = \mathbb{Z}/{n}$, the $Cay(G,\{\pm1\})$ is regular $n$-gon, which is isomorphic to a circle, $S^1 = \mathbb{R}/\mathbb{Z}$.
Let us end this post and this series dedicated to Cayley graphs here. In the next series of the posts, we hope to go through automatic groups.
\[
d(g,h) = \min\{n\mid g^{-1}h = s_1s_2\ldots s_n \},\quad s_i\in S
\]
As for points on the edges, the distance defined similarly with consideration that each point should first travel to one of its two neighboring vertices. With this metric, $X$ or $Cay(G,S)$ becomes a metric space and referred to as Cayley graph of $G$ with respect to $S$. We can say few things about $X$ immediately. Firstly, $X$ is a proper metric space, i.e. its closed balls are compact. Secondly, $X$ is a geodesic metric space, i.e. there is a shortest path connecting any two points.
Time for action Let us now consider an action of $G$ on $X$. Let us define an action $\phi:G\to Aut(X)$ such that $\phi_g(x) = gx$ if $x$ is a vertex. As edges, a point lying between vertices $(h,k)$ maps into a point lying between $(gh,gk)$ so that corresponding distances are preserved. For the sake of convenience, we identify an action $\phi_g$ with $g$. This action enjoy following properties. Firstly, each action is an isometry. Indeed $d(h,k) = d(gh,gk)$, for a reason that actions correspond to left multiplication, whereas distances were defined using right multiplication of elements.
Secondly, this action is proper. Properness has to do with sparsity of orbit points. It tells: for any $x\in X$ and any ball $B\subset X$ there are only finitely many $g\in G$ such that $gx\in B$. One immediate implication of properness is lack of accumulation points in the orbit of $x\in X$. Thirdly, this action is cobounded. Coboundedness roughly corresponds to omnipresence of orbit points. It tells: there is a ball $B\subset X$ whose $G$-translates cover the whole $X$, i.e. $G\cdot B = X$. Equivalently, there is $x\in X$ and $r\in \mathbb{N}$ such that for all $y\in X$ there is $g\in G$ such that $d(x,gy)<r$.
Examples: Let us give some examples of Cayley graphs.
1. $G = \mathbb{Z}$, the $Cay(G,\{\pm1 \})$ is isomorphic to real line, $\mathbb{R}$;
2. $G = \mathbb{Z}/{n}$, the $Cay(G,\{\pm1\})$ is regular $n$-gon, which is isomorphic to a circle, $S^1 = \mathbb{R}/\mathbb{Z}$.
Let us end this post and this series dedicated to Cayley graphs here. In the next series of the posts, we hope to go through automatic groups.
Comments
Post a Comment