Metraipolis › archive › dc_be0f3d920004

Alon–Boppana bound — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Alon%E2%80%93Boppana_bound
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-08T17:00:31.558Z
SHA-256 of the archived text
31a6e20ba8ecbad57847faa8b28ce04fb6ccc9473d41dc3ae4afb80493e63e91
Stable URL of this page
https://metraipolis.com/documento/dc_be0f3d920004

How to cite

Alon–Boppana bound — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Alon%E2%80%93Boppana_bound (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_be0f3d920004 (Metraipolis archive dc_be0f3d920004, sha256 31a6e20ba8ecbad57847faa8b28ce04fb6ccc9473d41dc3ae4afb80493e63e91)
BibTeX
@misc{dcbe0f3d920004,
  title = {Alon–Boppana bound — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Alon%E2%80%93Boppana_bound},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_be0f3d920004; sha256 31a6e20ba8ecbad57847faa8b28ce04fb6ccc9473d41dc3ae4afb80493e63e91},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Alon%E2%80%93Boppana_bound. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In spectral graph theory, the Alon–Boppana bound provides a lower bound on the second-largest eigenvalue of the adjacency matrix of a d-regular graph, meaning a graph in which every vertex has degree d. The reason for the interest in the second-largest eigenvalue is that the largest eigenvalue is guaranteed to be d due to d-regularity, with the all-ones vector being the associated eigenvector. The graphs that come close to meeting this bound are Ramanujan graphs, which are examples of the best possible expander graphs. Its discoverers are Noga Alon and Ravi Boppana.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in inglese, in ordine alfabetico).
Fonte: Wikipedia in inglese, voce «Alon–Boppana bound» — https://en.wikipedia.org/wiki/Alon%E2%80%93Boppana_bound
Wikidata Q85741005: «second-largest eigenvalue lower bound» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q85741005
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Alon%E2%80%93Boppana_bound?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1283895692, consultata il 2026-11-08T16:56:31.441Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 22d073f75a157eba8c9d2c061c290491e9e8c07dbbc241ff230f75122a0dfa25