Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2004 | Published
Journal Article Open

Improved Expansion of Random Cayley Graphs


Alon and Roichman (1994) proved that for every ε > 0 there is a finite c(e) such that for any sufficiently large group G, the expected value of the second largest (in absolute value) eigenvalue of the normalized adjacency matrix of the Cayley graph with respect to c(ε) log |G| random elements is less than ε. We reduce the number of elements to c(ε) logD(G) (for the same c), where D(G) is the sum of the dimensions of the irreducible representations of G. In sufficiently non-abelian families of groups (as measured by these dimensions), logD(G) is asymptotically (1/2) log |G|. As is well known, a small eigenvalue implies large graph expansion (and conversely); see Tanner (1984) and Alon and Milman (1984, 1985). For any specified eigenvalue or expansion, therefore, random Cayley graphs (of sufficiently non-abelian groups) require only half as many edges as was previously known.

Additional Information

© 2004 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France. Received Sep 2004, revised Dec 2004, accepted Dec 15, 2004. Supported in part by the Marshall family, a Caltech Summer Undergraduate Research Fellowship, and an NSF REU supplement. Supported in part by NSF CAREER grant 0049092 and by a grant from the Okawa Foundation.

Attached Files

Published - dm060222.pdf


Files (68.8 kB)
Name Size Download all
68.8 kB Preview Download

Additional details

August 19, 2023
October 20, 2023