Random Cayley graphs and expanders

Noga Alon, Yuval Roichman

Research output: Contribution to journalArticle

119 Scopus citations

Abstract

For every 1 > δ > 0 there exists a c = c(δ) > 0 such that for every group G of order n, and for a set S of c(δ) log n random elements in the group, the expected value of the second largest eigenvalue of the normalized adjacency matrix of the Cayley graph X(G, S) is at most (1 ‐ δ). This implies that almost every such a graph is an ϵ(δ)‐expander. For Abelian groups this is essentially tight, and explicit constructions can be given in some cases. © 1994 John Wiley & Sons, Inc.

Original languageEnglish (US)
Pages (from-to)271-284
Number of pages14
JournalRandom Structures & Algorithms
Volume5
Issue number2
DOIs
StatePublished - Apr 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Random Cayley graphs and expanders'. Together they form a unique fingerprint.

  • Cite this