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. https://resolver.caltech.edu/CaltechAUTHORS:20200518-134456297
![]() |
PDF
- Published Version
See Usage Policy. 68kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200518-134456297
Abstract
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: |
| ||||||||||
ORCID: |
| ||||||||||
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. | ||||||||||
Funders: |
| ||||||||||
Subject Keywords: | expander graphs, Cayley graphs, second eigenvalue, logarithmic generators | ||||||||||
Issue or Number: | 2 | ||||||||||
Record Number: | CaltechAUTHORS:20200518-134456297 | ||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20200518-134456297 | ||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||
ID Code: | 103285 | ||||||||||
Collection: | CaltechAUTHORS | ||||||||||
Deposited By: | Tony Diaz | ||||||||||
Deposited On: | 18 May 2020 20:57 | ||||||||||
Last Modified: | 18 May 2020 20:57 |
Repository Staff Only: item control page