Ramanujan graphs

A. Lubotzky, R. Phillips, Peter Clive Sarnak

Research output: Contribution to journalArticlepeer-review

877 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