Alon–Boppana bound
E621145
The Alon–Boppana bound is a fundamental result in spectral graph theory that gives an asymptotic lower bound on the second-largest eigenvalue of large regular graphs, showing inherent limitations on how well such graphs can approximate expanders.
Statements (44)
| Predicate | Object |
|---|---|
| instanceOf |
result in spectral graph theory
ⓘ
theorem ⓘ |
| appearsIn | research on high-dimensional expanders by analogy ⓘ |
| appliesTo |
d-regular graphs
ⓘ
regular graphs ⓘ |
| assumes | fixed degree d≥3 ⓘ |
| category |
results about expander graphs
ⓘ
spectral bounds in graph theory ⓘ |
| characterizes | Ramanujan graphs as optimal expanders with respect to the bound ⓘ |
| comparedTo | eigenvalues of the infinite d-regular tree ⓘ |
| concerns |
eigenvalues of adjacency matrices of graphs
ⓘ
second-largest eigenvalue of regular graphs ⓘ spectral gap of regular graphs ⓘ |
| field |
combinatorics
ⓘ
graph theory ⓘ spectral graph theory NERFINISHED ⓘ |
| gives | asymptotic lower bound on the second-largest eigenvalue ⓘ |
| hasConsequence |
families of d-regular graphs with smaller second-largest eigenvalue cannot exist for arbitrarily large n
ⓘ
optimal expanders must have second-largest eigenvalue close to 2√(d−1) ⓘ |
| hasStrongerForm | Serre’s refinement of the Alon–Boppana bound ⓘ |
| holdsFor | families of finite d-regular graphs with growing number of vertices ⓘ |
| implies | no infinite family of d-regular graphs can have second-largest eigenvalue strictly less than 2√(d−1)−ε for fixed ε>0 ⓘ |
| influences |
construction of error-correcting codes using expanders
ⓘ
design of expander-based algorithms ⓘ pseudorandom graph theory ⓘ |
| involves |
adjacency matrix spectrum
ⓘ
second-largest absolute value of eigenvalues ⓘ |
| isLowerBoundOn | spectral gap between d and the second-largest eigenvalue ⓘ |
| lowerBounds | lim inf of the second-largest eigenvalue of d-regular graphs by 2√(d−1) ⓘ |
| motivates | definition of Ramanujan graphs ⓘ |
| namedAfter |
Noga Alon
NERFINISHED
ⓘ
Ravindra B. Boppana NERFINISHED ⓘ |
| quantifies | best possible spectral expansion of large regular graphs ⓘ |
| relatedConcept | spectral radius of infinite d-regular tree ⓘ |
| relatesTo |
Ramanujan graphs
NERFINISHED
ⓘ
expander graphs ⓘ |
| shows | limitations on how well large regular graphs can approximate expanders ⓘ |
| standardReference |
Noga Alon’s work on eigenvalues and expanders
ⓘ
R. B. Boppana’s paper on eigenvalues and graph bisection ⓘ |
| typeOf | asymptotic bound ⓘ |
| usedFor |
analyzing spectral expansion
ⓘ
bounding the spectral gap from above ⓘ proving limitations of explicit expander constructions ⓘ |
| yearProved | 1980s ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.