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

摘要

The Alon-Roichman theorem states that for every epsilon > 0 there is a constant c(epsilon), such that the Cayley graph of a finite group G with respect to c(epsilon) log vertical bar G vertical bar elements of G, chosen independently and uniformly at random, has expected second largest eigenvalue less than epsilon. 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. (c) 2007 Wiley Periodicals, Inc.