7. Cayley Graphs

Let $\Gamma$ be a finitely generated group. It has a surjection $F_s \rightarrow \Gamma$ for S finite. Elements of the kernel are called relations and the elements of S are called genereators. Suppose the kernel is generated as a normal subgroup by a subgroup $K \subseteq F_S$ . Then we write $\Gamma \cong \langle S|R \rangle$ to mean $\Gamma \cong F_S/ \langle \langle R \rangle \rangle$ . If R is finite, the $\Gamma$ is said to be finitely presentable.

Example: $\mathbb{Z} \cong \langle b,c|bcb^{-1}c^{-1},b^2c^{-3} \rangle$ .

Let’s develop a topological point of view.

Let $X^{(1)}$ be the standard rose for $F_S$ . Each relation $r \in R$ corresponds to a (homotopy class of a) map $f_r:S^1 \rightarrow X^{(1)}$ . We construct a 2-complex X gluing on a 2-cell using the map $f_r$ for each relation $r \in R$ .

Lemma 6: $\pi_1(X) \cong \Gamma$
Proof: This is a simple application of the Seifert-van Kampen Theorem.

We call X a presentation complex for $\Gamma$ , and we deduce that every finitely generated group is $\pi_1$ of a 2-complex.

Exercise 8: Every finitely presented group is $\pi_1$ of a closed 4-manifold.

Therefore, $\Gamma$ acts freely and properly discontinuously on some 2-complex $\tilde{X}$ , the universal cover of $X$ .

Definition: Let S be a finite generating set for $\Gamma$ as above. Then $Cay_S(\Gamma)=\tilde{X}^{(1)}$ is the Cayley graph of $\Gamma$ with respect to S.

To see that this only depends on S, let’s give the more standard definition. The vertices of $Cay_S(\Gamma)$ are just the elements of $\Gamma$ . For each generator $g \in S$ , two vertices $\gamma ,\delta$ are joined by an edge iff $\gamma g=\delta$

The group $\Gamma$ acts by left translation.

Examples:

$\mathbb{Z}\cong \langle 1\rangle$ .
$\mathbb{Z} \cong \langle 2,3 \rangle$ .
The tree for $F_S$ .

Definition: The Cayley graph $Cay_S(\Gamma)$ induces a natural length metric on $\Gamma$ , denoted $d_S$ and called the word metric. Note that $d_S(1,\gamma)=l_S(\gamma)$ , the word length of $\gamma$ .

The action of $\Gamma$ on $Cay_S(\gamma)$ is by isometries.

Given a metric space $(X,d)$ , a geodesic is just an isometric embedding of a compact interval into $X$ .

A metric space is geodesic if any pair of point is joined by a geodesic. Note that $Cay_S(\Gamma)$ is a geodesic metric space.

Definition: Let $\lambda ,\epsilon \geq 0$ . A $(\lambda,\epsilon)$ -quasi isometric embedding is a map of metric space $f:X \rightarrow Y$ such that $\lambda^{-1}d_X(x_1,x_2)-\epsilon \leq d_Y(f(x_1),f(x_2)) \leq \lambda d_X(x_1,x_2)+\epsilon$ .
If for some $C$ , we also have that for every $y \in Y$ , there is $x \in X$ such that $d_Y(f(x),y) \leq C$ , then $f$ is a quasi-isometry.

Exercise 9: Quasi-isometry is an equivalent relation (use the Axiom of Choice).

Exercise 10: Let $S$ and $S'$ be two finite generating sets for $\Gamma$ . Then $id:(\Gamma,d_S) \rightarrow (\Gamma,d_{S'})$ is a $(\lambda,0)$ quasi-isometry.