Random Cayley graphs and expanders
- 1 April 1994
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 5 (2) , 271-284
- https://doi.org/10.1002/rsa.3240050203
Abstract
For every 1 > δ > 0 there exists ac=c(δ) > 0 such that for every groupGof ordern, and for a setSofc(δ) lognrandom elements in the group, the expected value of the second largest eigenvalue of the normalized adjacency matrix of the Cayley graphX(G, S)is at most (1 ‐ δ). This implies that almost every such a graph is an ϵ(δ)‐expander. For Abelian groups this is essentially tight, and explicit constructions can be given in some cases. © 1994 John Wiley & Sons, Inc.Keywords
This publication has 17 references indexed in Scilit:
- Some geometric aspects of graphs and their eigenfunctionsDuke Mathematical Journal, 1993
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphsIEEE Transactions on Information Theory, 1992
- Simple Constructions of Almost k‐wise Independent Random VariablesRandom Structures & Algorithms, 1992
- On the second eigenvalue and random walks in randomd-regular graphsCombinatorica, 1991
- On the second eigenvalue of a graphDiscrete Mathematics, 1991
- Construction of a Thin Set with small Fourier CoefficientsBulletin of the London Mathematical Society, 1990
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985
- Explicit Concentrators from Generalized N-GonsSIAM Journal on Algebraic Discrete Methods, 1984
- On the Distribution of the Roots of Certain Symmetric MatricesAnnals of Mathematics, 1958
- Characteristic Vectors of Bordered Matrices With Infinite DimensionsAnnals of Mathematics, 1955