Premium
Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
Author(s) -
Christofides Demetres,
Markström Klas
Publication year - 2008
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20177
Subject(s) - cayley graph , mathematics , combinatorics , random graph , discrete mathematics , expander graph , coset , random matrix , vertex (graph theory) , eigenvalues and eigenvectors , transitive relation , generalization , graph , physics , quantum mechanics , mathematical analysis
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