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

Summary: 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\).