Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem

Zeph Landau ; Alexander Russell

The electronic journal of combinatorics, Tome 11 (2004) no. 1

Résumé

We give a simple proof of the Alon–Roichman theorem, which asserts that the Cayley graph obtained by selecting $c_\varepsilon \log |G|$ elements, independently and uniformly at random, from a finite group $G$ has expected second eigenvalue no more than $\varepsilon$; here $c_\varepsilon$ is a constant that depends only on $\varepsilon$. In particular, such a graph is an expander with constant probability. Our new proof has three advantages over the original proof: (i.) it is extremely simple, relying only on the decomposition of the group algebra and tail bounds for operator-valued random variables, (ii.) it shows that the $\log |G|$ term may be replaced with $\log D$, where $D \leq |G|$ is the sum of the dimensions of the irreducible representations of $G$, and (iii.) it establishes the result above with a smaller constant $c_\varepsilon$.

Détail

DOI : 10.37236/1815

Classification : 05C25, 05C80, 20C15, 20F69
Mots-clés : Alon-Roichman theorem, Cayley graph, eigenvalue, expander, irreducible representations