11 Cayley expander graphs
For a group \(H\) and symmetric \(S\subseteq H\), \(C(H,S)\) has vertex set \(H\) and edge \((g,gs)\) for \(s\in S\); it is \(|S|\)-regular and connected iff \(S\) generates \(H\).
\(\lambda (H,S)=\lambda (C(H,S))\) and \(g(H,S)=1-\lambda _2(H,S)\).
A graph is vertex transitive if its automorphism group acts transitively on vertices.
Every Cayley graph is vertex transitive.
\(x\mapsto hg^{-1}x\) is an automorphism of \(C(H,S)\) sending \(g\) to \(h\).
If \(H\) is abelian and \(\lambda (H,S)\le 1/2\) then \(|S|\ge \tfrac 13\log |H|\).
By Theorem 39 the diameter is \({\lt}3\log n\), so each element is a product of \(\le 3\log n\) generators. In an abelian group the number of length-\(l\) products of \(m=|S|\) generators is \(\binom {l+m-1}l\); requiring \(\sum _{j\le 3\log n}\binom {j+m-1}j\ge n\) forces \(m=\Omega (\log n)\) (via \(\binom kl\le (ke/l)^l\)).
A random \(S\subseteq H\) of size \(100\log |H|\) has \(\lambda (C(H,S)){\lt}1/2\) with probability \(\ge 0.5\).
A representation of \(H\) is a homomorphism \(\rho :H\to U(V)\) to the unitary group of a Hermitian space \(V\).
On \(V=\mathbb {C}^H\), \([r(h)f](x)=f(xh)\).
A representation with no nontrivial invariant subspace.
Every unitary representation decomposes orthogonally into irreducibles, uniquely up to isomorphism.
Every irreducible representation of \(H\) appears in the regular representation.
\(A_\rho =\tfrac 1{|S|}\sum _{s\in S}\rho (s)\).
For abelian \(H\), \((\chi (h))_{h}\) is an eigenvector of the normalized adjacency matrix of \(C(H,S)\) with eigenvalue \(\tfrac 1{|S|}\sum _{s\in S}\chi (s)\).
\((M\chi )(x)=\tfrac 1{|S|}\sum _s\chi (xs)=\tfrac 1{|S|}(\sum _s\chi (s))\chi (x)\) by the homomorphism property.
The normalized adjacency matrix of \(C(H,S)\) is \(A_r\); its eigenvalues are the union, over irreducibles \(\rho \), of the eigenvalues of \(A_\rho \), and conversely.
An action of \(H\) on \(X\) is a homomorphism \(\pi :H\to \mathrm{Sym}(X)\); \(\mathrm{Sch}(H,X,S)\) has vertex set \(X\) and edges \((x,\pi (s)x)\). Cayley graphs are the special case \(X=H\).
Every connected component \(Z\) of \(\mathrm{Sch}(H,X,S)\) has \(\lambda (Z)\le \lambda (H,S)\).
The permutation representation’s \(A_\rho \) has eigenvalues among those of \(A_r\) by Lemma 200; restricting to a component only removes eigenvalues.
Every finite \(2d\)-regular graph is a Schreier graph of some group action.
\(g(H,S)=\min _{v\perp \mathbf1}\tfrac 1{2|S|}\sum _{h\in S}\tfrac {\| r(h)v-v\| ^2}{\| v\| ^2}\).
Variational form of \(\lambda _2\) via \(A_r\), with the unitary identity \(\| r(h)v-v\| ^2=2(\| v\| ^2-v^\top r(h)v)\).
\(K(H,S)=\min _{v\perp \mathbf1}\max _{h\in S}\tfrac {\| r(h)v-v\| ^2}{\| v\| ^2}\), equivalently the minimum over nontrivial irreducibles.
\(K(H,S)/(2|S|){\lt}g(H,S){\lt}K(H,S)/2\).
In Lemma 204 the max over \(S\) both lower- and upper-bounds the average (within a factor \(|S|\)).
If each element of \(\tilde S\) is a product of \(\le m\) elements of \(S\), then \(K(H,S)\ge K(H,\tilde S)/m\).
An action of \(B\) on \(A\) is a homomorphism \(B\to \mathrm{Aut}(A)\); the semidirect product \(A\rtimes B\) has multiplication \((a_1,b_1)(a_2,b_2)=(a_1\phi _{b_1}(a_2),b_1b_2)\).
If \(B\) acts on \(A\) so that the generating set \(S_A\) is a single \(B\)-orbit of \(x\), then \(S=\{ (1,s):s\in S_B\} \cup \{ (x,1)\} \) generates \(A\rtimes B\) and \(C(A\rtimes B,S)\) is the replacement product of \(C(A,S_A)\) and \(C(B,S_B)\).
Each \((a,b)=(a,1)(1,b)\), and \((1,s_b)(x,1)(1,s_b^{-1})=(\phi _{s_b}(x),1)\) ranges over \((S_A,1)\), so \(S\) generates. Within-cloud edges come from \((1,S_B)\) and between-cloud edges \((a,b)(x,1)=(a\phi _b(x),b)\) realize the \(C(A,S_A)\) edges, matching the replacement product.
\(F_p[H]\) is the group ring of \(H\) over \(F_p\); the construction sets \(H_{i+1}=F_{p_i}[H_i]\rtimes H_i\).
If the number of irreducibles of \(H\) of dimension \({\lt}r\) is \({\lt}c^r\), then a constant number of orbits makes \(F_p[H]\) an expander.
There are groups \(H_i=F_{p_{i-1}}[H_{i-1}]\rtimes H_{i-1}\) and generating sets \(U_i\) with \(\lambda (H_n,U_n)\le 1/2\) and \(|U_n|\le \log ^{(n/2)}|H_n|\) (iterated log).
\(H\wr S_d=H^d\rtimes S_d\) with \(S_d\) permuting coordinates; the construction sets \(H_1=A_d\), \(H_{i+1}=H_i^d\rtimes A_d\).
If every \(h\in H\) is a commutator, \(U\) is expanding with second eigenvalue \(\le 1/4\), and \(|U|{\lt}d/10^6\), then \(\lambda (H^d,U^{(d)}){\lt}1/2\) for the single \(S_d\)-orbit \(U^{(d)}\).
\(A_d\) has an explicit generating set \(U\) of \(d\)-independent size with \(\lambda (A_d,U){\lt}1/100\).
For large \(d\), the groups \(H_1=A_d\), \(H_{i+1}=H_i^d\rtimes A_d\) admit generating sets \(U_i\) with \(\lambda (H_i,U_i)\le 1/2\) and \(|U_i|\) independent of \(i\).
There is a group with two bounded generating sets, one giving an expanding Cayley family and the other not.
For \(F_2^{p+1}\rtimes SL_2(p)\), one generating set (two random orbits plus \(SL_2(p)\) generators) is a replacement product of expanders, hence expanding; the other (standard basis orbit) is a replacement product with the non-expanding cube \(C(F_2^{p+1},\{ e_i\} )\), and a replacement product never beats a constituent’s second eigenvalue. Alternatively \(S_d\) expands via Theorem 215 but not via \(\{ (12),(12\ldots d)^{\pm 1}\} \).
For a cut \(E(T,V\setminus T)\) of \(C(H,S)\), \(\epsilon _{s,T}\) counts cut edges using generator \(s^{\pm 1}\).
For \(T\subseteq \{ 0,1\} ^n\) with \(|T|=2^{n-1}\), some coordinate \(j\) has \(\epsilon _{j,T}\ge \Omega (\tfrac {\log n}n2^n)\), and this is tight.