A Caltech Library Service

Improved Expansion of Random Cayley Graphs

Loh, Po-Shen and Schulman, Leonard J. (2004) Improved Expansion of Random Cayley Graphs. Discrete Mathematics and Theoretical Computer Science, 6 (2). pp. 523-528. ISSN 1462-7264.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
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.
Funding AgencyGrant Number
Marshall FamilyUNSPECIFIED
Caltech Summer Undergraduate Research Fellowship (SURF)UNSPECIFIED
Okawa FoundationUNSPECIFIED
Subject Keywords:expander graphs, Cayley graphs, second eigenvalue, logarithmic generators
Issue or Number:2
Record Number:CaltechAUTHORS:20200518-134456297
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:103285
Deposited By: Tony Diaz
Deposited On:18 May 2020 20:57
Last Modified:18 May 2020 20:57

Repository Staff Only: item control page