Po-Shen Loh ; Leonard J. Schulman - Improved Expansion of Random Cayley Graphs

dmtcs:316 - Discrete Mathematics & Theoretical Computer Science, January 1, 2004, Vol. 6 no. 2 - https://doi.org/10.46298/dmtcs.316
Improved Expansion of Random Cayley Graphs

Authors: Po-Shen Loh ORCID-iD1; Leonard J. Schulman 2

  • 1 Churchill College [Cambridge]
  • 2 Computing and Mathematical Sciences [Pasadena]]

In Random Cayley Graphs and Expanders, N. Alon and Y. Roichman proved that for every ε > 0 there is a finite c(ε ) 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(ε )log D(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), log D(G) is asymptotically (1/2)log|G|. As is well known, a small eigenvalue implies large graph expansion (and conversely); see Tanner84 and AlonMilman84-2,AlonMilman84-1. 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.


Volume: Vol. 6 no. 2
Published on: January 1, 2004
Imported on: March 26, 2015
Keywords: expander graphs,Cayley graphs,second eigenvalue,logarithmic generators,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • CAREER: Computation Methods; Funder: National Science Foundation; Code: 0049092

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1002/rsa.3240050203
  • 10.1002/rsa.3240050203
Random Cayley graphs and expanders

Consultation statistics

This page has been seen 218 times.
This article's PDF has been downloaded 337 times.