Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Christofides et al. (2007) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: