[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki19\/alon-boppana-bound-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki19\/alon-boppana-bound-wikipedia\/","headline":"Alon\u2013Boppana bound – Wikipedia","name":"Alon\u2013Boppana bound – Wikipedia","description":"before-content-x4 In spectral graph theory, the Alon\u2013Boppana bound provides a lower bound on the second-largest eigenvalue of the adjacency matrix","datePublished":"2014-09-17","dateModified":"2014-09-17","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki19\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki19\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/e85ff03cbe0c7341af6b982e47e9f90d235c66ab","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/e85ff03cbe0c7341af6b982e47e9f90d235c66ab","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki19\/alon-boppana-bound-wikipedia\/","wordCount":15122,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4In spectral graph theory, the Alon\u2013Boppana bound provides a lower bound on the second-largest eigenvalue of the adjacency matrix of a d{displaystyle d}       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4-regular graph,[1] meaning a graph in which every vertex has degree d{displaystyle d}. The reason for the interest in the second-largest eigenvalue is that the largest eigenvalue is guaranteed to be d{displaystyle d} due to        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4d{displaystyle 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.Table of Contents       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Theorem statement[edit]Intuition[edit]Saturation[edit]First proof (slightly weaker statement)[edit]Second proof (slightly modified statement)[edit]References[edit]Theorem statement[edit]Let G{displaystyle G} be a d{displaystyle d}-regular graph on n{displaystyle n} vertices with diameter m{displaystyle m}, and let A{displaystyle A} be its adjacency matrix. Let \u03bb1\u2265\u03bb2\u2265\u22ef\u2265\u03bbn{displaystyle lambda _{1}geq lambda _{2}geq cdots geq lambda _{n}} be its eigenvalues. Then\u03bb2\u22652d\u22121\u22122d\u22121\u22121\u230am\/2\u230b.{displaystyle lambda _{2}geq 2{sqrt {d-1}}-{frac {2{sqrt {d-1}}-1}{lfloor m\/2rfloor }}.}The above statement is the original one proved by Noga Alon. Some slightly weaker variants exist to improve the ease of proof or improve intuition. Two of these are shown in the proofs below.Intuition[edit]The intuition for the number 2d\u22121{displaystyle 2{sqrt {d-1}}} comes from considering the infinite d{displaystyle d}-regular tree.[2] This graph is a universal cover of d{displaystyle d}-regular graphs, and it has spectral radius 2d\u22121.{displaystyle 2{sqrt {d-1}}.}Saturation[edit]A graph that essentially saturates the Alon\u2013Boppana bound is called a Ramanujan graph. More precisely, a Ramanujan graph is a d{displaystyle d}-regular graph such that |\u03bb2|,|\u03bbn|\u22642d\u22121.{displaystyle |lambda _{2}|,|lambda _{n}|leq 2{sqrt {d-1}}.}A theorem by Friedman[3] shows that, for every d{displaystyle d} and "},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki19\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki19\/alon-boppana-bound-wikipedia\/#breadcrumbitem","name":"Alon\u2013Boppana bound – Wikipedia"}}]}]