Alon–Boppana bound
In spectral graph theory, the Alon–Boppana bound provides a lower bound on the second-largest eigenvalue of the adjacency matrix of a formula_1-regular graph, meaning a graph in which every vertex has degree formula_1. The reason for the interest in the second-largest eigenvalue is that the largest eigenvalue is guaranteed to be formula_1 due to formula_1-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. Theorem statement. Let formula_5 be a formula_1-regular graph on formula_7 vertices with diameter formula_8, and let formula_9 be its adjacency matrix. Let formula_10 be its eigenvalues. Then 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. The intuition for the number formula_12 comes from considering the infinite formula_1-regular tree. This graph is a universal cover of formula_1-regular graphs, and it has spectral radius formula_15 Saturation. A graph that essentially saturates  the Alon–Boppana bound is called a Ramanujan graph. More precisely, a Ramanujan graph is a formula_1-regular graph such that formula_17 A theorem by Friedman shows that, for every formula_1 and formula_19 and for sufficiently large formula_7, a random formula_1-regular graph formula_5 on formula_7 vertices satisfies formula_24 as follows. Each component will be indexed by a vertex formula_25 in the graph. For each formula_26 if the distance between formula_25 and formula_28 is formula_29 then the formula_25-component of formula_31 is formula_32 if formula_33 and formula_34 if formula_35 We claim that any such vector formula_36 satisfies To prove this , let formula_38 denote the set of all vertices that have a distance of exactly formula_39 from formula_40 First, note that Second, note that where the last term on the right comes from a possible overcounting of terms in the initial expression. The above then implies which, when combined with the fact that formula_44 for any formula_29 yields The combination of the above results proves the desired inequality. For convenience, define the formula_47-ball of a vertex formula_28 to be the set of vertices with a distance of at most formula_49 from formula_40 Notice that the entry of formula_31 corresponding to  a vertex formula_25 is nonzero if and only if formula_25 lies in the formula_47-ball of formula_55 The number of vertices within distance formula_39 of a given vertex is at most formula_57 Therefore, if formula_58 then there exist vertices formula_59 with distance at least formula_60 Let formula_36 and formula_62 It then follows that formula_63 because there is no vertex that lies in the formula_47-balls of both formula_65 and formula_66 It is also true that formula_67 because no vertex in the formula_47-ball of formula_65 can be adjacent to a vertex in the formula_47-ball of formula_66 Now, there exists  some constant formula_72 such that formula_73 satisfies formula_74 Then, since formula_75 Finally, letting formula_77 grow without bound while ensuring that formula_78 (this can be done by letting formula_77 grow sublogarithmically as a function of formula_7) makes the error term formula_81 in formula_82 Second proof (slightly modified statement). This proof will demonstrate a slightly modified result, but it provides better intuition for the source of the number formula_15 Rather than showing that formula_84 we will show that formula_85 First, pick some value formula_86 Notice that the number of closed walks of length formula_87 is However, it is also true that the  number of closed walks of length formula_87 starting at a fixed vertex formula_28 in a formula_1-regular graph is at least the number of such walks in an infinite formula_1-regular tree, because an infinite formula_1-regular tree can be used to cover the graph. By the definition of the Catalan numbers, this number is at least formula_94 where formula_95 is the formula_96 Catalan number. It follows that Letting formula_7 grow without bound and letting formula_39 grow without bound but sublogarithmically in formula_7 yields formula_102