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.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Alon–Boppana bound canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T6834499 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Alon–Boppana bound Context triple: [Noga Alon, notableWork, Alon–Boppana bound]
-
A.
Erdős–Stone theorem
The Erdős–Stone theorem is a fundamental result in extremal graph theory that asymptotically determines the maximum number of edges in an n-vertex graph that avoids containing a given subgraph.
-
B.
Grothendieck inequality
The Grothendieck inequality is a fundamental result in functional analysis and theoretical computer science that bounds certain bilinear forms and has deep implications for Banach space theory, operator theory, and approximation algorithms.
-
C.
Erdős–Ko–Rado theorem
The Erdős–Ko–Rado theorem is a fundamental result in extremal combinatorics that determines the maximum size of a family of subsets of a finite set in which every pair of subsets has a non-empty intersection.
-
D.
Furst–Saxe–Sipser lower bounds
Furst–Saxe–Sipser lower bounds are foundational results in circuit complexity theory that established superpolynomial lower bounds for constant-depth Boolean circuits (AC⁰), demonstrating inherent limitations of such circuits for computing certain functions.
-
E.
May–Wigner stability theorem
The May–Wigner stability theorem is a result in theoretical ecology and random matrix theory showing that large, complex systems with many random interactions are generically unstable beyond a critical level of complexity.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Alon–Boppana bound Target entity description: 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.
-
A.
Erdős–Stone theorem
The Erdős–Stone theorem is a fundamental result in extremal graph theory that asymptotically determines the maximum number of edges in an n-vertex graph that avoids containing a given subgraph.
-
B.
Grothendieck inequality
The Grothendieck inequality is a fundamental result in functional analysis and theoretical computer science that bounds certain bilinear forms and has deep implications for Banach space theory, operator theory, and approximation algorithms.
-
C.
Erdős–Ko–Rado theorem
The Erdős–Ko–Rado theorem is a fundamental result in extremal combinatorics that determines the maximum size of a family of subsets of a finite set in which every pair of subsets has a non-empty intersection.
-
D.
Furst–Saxe–Sipser lower bounds
Furst–Saxe–Sipser lower bounds are foundational results in circuit complexity theory that established superpolynomial lower bounds for constant-depth Boolean circuits (AC⁰), demonstrating inherent limitations of such circuits for computing certain functions.
-
E.
May–Wigner stability theorem
The May–Wigner stability theorem is a result in theoretical ecology and random matrix theory showing that large, complex systems with many random interactions are generically unstable beyond a critical level of complexity.
- F. None of above. chosen
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 ⓘ
linked to:
Spectral Graph Theory
|
| 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
ⓘ
Ravindra B. Boppana ⓘ |
| quantifies | best possible spectral expansion of large regular graphs ⓘ |
| relatedConcept | spectral radius of infinite d-regular tree ⓘ |
| relatesTo |
Ramanujan graphs
ⓘ
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 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Alon–Boppana bound Description of subject: 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.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.