Ramanujan graphs

A. Lubotzky; R. Phillips; P. Sarnak

doi:10.1007/BF02126799

Ramanujan graphs

A. Lubotzky, R. Phillips, P. Sarnak

Research output: Contribution to journal › Article › peer-review

1069 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 log_k-1 |X| which gives larger girth than was previously known by explicit or non-explicit constructions.

Original language	English (US)
Pages (from-to)	261-277
Number of pages	17
Journal	Combinatorica
Volume	8
Issue number	3
DOIs	https://doi.org/10.1007/BF02126799
State	Published - Sep 1988
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computational Mathematics
Discrete Mathematics and Combinatorics

Keywords

AMS subject classification (1980): 05C35

Access to Document

10.1007/BF02126799

Cite this

@article{2997086857434affbe93fb6e8a8a0f1a,

title = "Ramanujan graphs",

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.",

keywords = "AMS subject classification (1980): 05C35",

author = "A. Lubotzky and R. Phillips and P. Sarnak",

year = "1988",

month = sep,

doi = "10.1007/BF02126799",

language = "English (US)",

volume = "8",

pages = "261--277",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "3",

}

TY - JOUR

T1 - Ramanujan graphs

AU - Lubotzky, A.

AU - Phillips, R.

AU - Sarnak, P.

PY - 1988/9

Y1 - 1988/9

N2 - 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.

AB - 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.

KW - AMS subject classification (1980): 05C35

UR - http://www.scopus.com/inward/record.url?scp=0000848816&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0000848816&partnerID=8YFLogxK

U2 - 10.1007/BF02126799

DO - 10.1007/BF02126799

M3 - Article

AN - SCOPUS:0000848816

SN - 0209-9683

VL - 8

SP - 261

EP - 277

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -

Ramanujan graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this