Cayley graph

Each element ${\displaystyle g}$ of ${\displaystyle G}$ is assigned a vertex: the vertex set of ${\displaystyle \Gamma }$ is identified with ${\displaystyle G.}$

Each element ${\displaystyle s}$ of ${\displaystyle S}$ is assigned a color ${\displaystyle c_{s}}$.

For every ${\displaystyle g\in G}$ and ${\displaystyle s\in S}$, there is a directed edge of color ${\displaystyle c_{s}}$ from the vertex corresponding to ${\displaystyle g}$ to the one corresponding to ${\displaystyle gs}$.

Suppose that ${\displaystyle G=\mathbb {Z} }$ is the infinite cyclic group and the set ${\displaystyle S}$ consists of the standard generator 1 and its inverse (−1 in the additive notation); then the Cayley graph is an infinite path.

Similarly, if ${\displaystyle G=\mathbb {Z} _{n}}$ is the finite of order ${\displaystyle n}$ and the set ${\displaystyle S}$ consists of two elements, the standard generator of ${\displaystyle G}$ and its inverse, then the Cayley graph is the cycle ${\displaystyle C_{n}}$. More generally, the Cayley graphs of finite cyclic groups are exactly the circulant graphs.

cyclic group

The Cayley graph of the (with the cartesian product of generating sets as a generating set) is the cartesian product of the corresponding Cayley graphs.^[3] Thus the Cayley graph of the abelian group ${\displaystyle \mathbb {Z} ^{2}}$ with the set of generators consisting of four elements ${\displaystyle (\pm 1,0),(0,\pm 1)}$ is the infinite grid on the plane ${\displaystyle \mathbb {R} ^{2}}$, while for the direct product ${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{m}}$ with similar generators the Cayley graph is the ${\displaystyle n\times m}$ finite grid on a torus.

direct product of groups

The Cayley graph ${\displaystyle \Gamma (G,S)}$ depends in an essential way on the choice of the set ${\displaystyle S}$ of generators. For example, if the generating set ${\displaystyle S}$ has ${\displaystyle k}$ elements then each vertex of the Cayley graph has ${\displaystyle k}$ incoming and ${\displaystyle k}$ outgoing directed edges. In the case of a symmetric generating set ${\displaystyle S}$ with ${\displaystyle r}$ elements, the Cayley graph is a of degree ${\displaystyle r.}$

regular directed graph

(or closed walks) in the Cayley graph indicate relations among the elements of ${\displaystyle S.}$ In the more elaborate construction of the Cayley complex of a group, closed paths corresponding to relations are "filled in" by polygons. This means that the problem of constructing the Cayley graph of a given presentation ${\displaystyle {\mathcal {P}}}$ is equivalent to solving the Word Problem for ${\displaystyle {\mathcal {P}}}$.^[1]

Cycles

If ${\displaystyle f:G'\to G}$ is a group homomorphism and the images of the elements of the generating set ${\displaystyle S'}$ for ${\displaystyle G'}$ are distinct, then it induces a covering of graphs

$${\displaystyle {\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),}$$

where ${\displaystyle S=f(S').}$ In particular, if a group ${\displaystyle G}$ has ${\displaystyle k}$ generators, all of order different from 2, and the set ${\displaystyle S}$ consists of these generators together with their inverses, then the Cayley graph ${\displaystyle \Gamma (G,S)}$ is covered by the infinite regular tree of degree ${\displaystyle 2k}$ corresponding to the free group on the same set of generators.

surjective

For any finite Cayley graph, considered as undirected, the is at least equal to 2/3 of the degree of the graph. If the generating set is minimal (removal of any element and, if present, its inverse from the generating set leaves a set which is not generating), the vertex connectivity is equal to the degree. The edge connectivity is in all cases equal to the degree.^[6]

vertex connectivity

If ${\displaystyle \rho _{\text{reg}}(g)(x)=gx}$ is the left-regular representation with ${\displaystyle |G|\times |G|}$ matrix form denoted ${\displaystyle [\rho _{\text{reg}}(g)]}$, the adjacency matrix of ${\displaystyle \Gamma (G,S)}$ is ${\textstyle A=\sum _{s\in S}[\rho _{\text{reg}}(s)]}$.

Every group ${\displaystyle \chi }$ of the group ${\displaystyle G}$ induces an eigenvector of the adjacency matrix of ${\displaystyle \Gamma (G,S)}$. The associated eigenvalue is

$${\displaystyle \lambda _{\chi }=\sum _{s\in S}\chi (s),}$$

which, when ${\displaystyle G}$ is Abelian, takes the form

$${\displaystyle \sum _{s\in S}e^{2\pi ijs/|G|}}$$

for integers ${\displaystyle j=0,1,\dots ,|G|-1.}$ In particular, the associated eigenvalue of the trivial character (the one sending every element to 1) is the degree of ${\displaystyle \Gamma (G,S)}$, that is, the order of ${\displaystyle S}$. If ${\displaystyle G}$ is an Abelian group, there are exactly ${\displaystyle |G|}$ characters, determining all eigenvalues. The corresponding orthonormal basis of eigenvectors is given by ${\displaystyle v_{j}={\tfrac {1}{\sqrt {|G|}}}{\begin{pmatrix}1&e^{2\pi ij/|G|}&e^{2\cdot 2\pi ij/|G|}&e^{3\cdot 2\pi ij/|G|}&\cdots &e^{(|G|-1)2\pi ij/|G|}\end{pmatrix}}.}$ It is interesting to note that this eigenbasis is independent of the generating set ${\displaystyle S}$.

More generally for symmetric generating sets, take ${\displaystyle \rho _{1},\dots ,\rho _{k}}$ a complete set of irreducible representations of ${\displaystyle G,}$ and let ${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$ with eigenvalue set ${\displaystyle \Lambda _{i}(S)}$. Then the set of eigenvalues of ${\displaystyle \Gamma (G,S)}$ is exactly ${\textstyle \bigcup _{i}\Lambda _{i}(S),}$ where eigenvalue ${\displaystyle \lambda }$ appears with multiplicity ${\displaystyle \dim(\rho _{i})}$ for each occurrence of ${\displaystyle \lambda }$ as an eigenvalue of ${\displaystyle \rho _{i}(S).}$

character

${\displaystyle S=\{1,4\}}$: ${\displaystyle \Gamma (G,S)}$ is a ${\displaystyle 5}$-cycle with eigenvalues ${\displaystyle 2,{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}}}$

${\displaystyle S=\{1,2,3,4\}}$: ${\displaystyle \Gamma (G,S)}$ is ${\displaystyle K_{5}}$ with eigenvalues ${\displaystyle 4,-1,-1,-1,-1}$

Vertex-transitive graph

Generating set of a group

Lovász conjecture

Cube-connected cycles

Algebraic graph theory

Cycle graph (algebra)

Cayley diagrams

"Cayley graph". MathWorld.

Weisstein, Eric W.