Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales

The Alon–Roichman theorem states that for every ε> 0 there is a constant c (ε), such that the Cayley graph of a finite group G with respect to c (ε)log ∣ G ∣ elements of G , chosen independently and uniformly at random, has expected second largest eigenvalue less than ε. In particular, such a graph is an expander with high probability. Landau and Russell, and independently Loh and Schulman, improved the bounds of the theorem. Following Landau and Russell we give a new proof of the result, improving the bounds even further. When considered for a general group G , our bounds are in a sense best possible. We also give a generalization of the Alon–Roichman theorem to random coset graphs. Our proof uses a Hoeffding‐type result for operator valued random variables, which we believe can be of independent interest. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008