Ramanujan graphs

A. Lubotzky, R. Phillips, Peter Clive Sarnak

Research output: Contribution to journalArticle

859 Scopus citations

Abstract

A large family of explicit k-regular Cayley graphs X is presented. These graphs satisfy a number of extremal combinatorial properties. (i) For eigenvalues λ of X either λ=±k or |λ|≦2 √k-1. This property is optimal and leads to the best known explicit expander graphs. (ii) The girth of X is asymptotically ≧4/3 logk-1 |X| which gives larger girth than was previously known by explicit or non-explicit constructions.

Original languageEnglish (US)
Pages (from-to)261-277
Number of pages17
JournalCombinatorica
Volume8
Issue number3
DOIs
StatePublished - Sep 1 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Ramanujan graphs'. Together they form a unique fingerprint.

  • Cite this

    Lubotzky, A., Phillips, R., & Sarnak, P. C. (1988). Ramanujan graphs. Combinatorica, 8(3), 261-277. https://doi.org/10.1007/BF02126799