Improved Expansion of Random Cayley Graphs

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2004, 6 (2), pp.523-528
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00959024
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 17:06:48
Dernière modification le : mercredi 29 novembre 2017 - 10:26:24
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:15:57

Fichier

dm060222.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00959024, version 1

Collections

Citation

Po-Shen Loh, Leonard J. Schulman. Improved Expansion of Random Cayley Graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2004, 6 (2), pp.523-528. 〈hal-00959024〉

Partager

Métriques

Consultations de la notice

81

Téléchargements de fichiers

184