The March 2026 issue of the Annals of Mathematics contains a paper by Chen, Garza-Vargas, Tropp, and van Handel (Chen et al. 2026) that develops a deep theory of so-called strong convergence. This theory has many striking consequences whose statements are quite elementary. One notable application is an extremely precise description of the second eigenvalue of random regular graphs. This eigenvalue plays a central role because it governs the expansion properties of the graph.
Informally, expander graphs are graphs that are simultaneously sparse and highly connected. These seemingly contradictory properties make expanders extremely useful in numerous applications in mathematics, computer science, and physics; see this previous blog post for further discussion.
We briefly recall the definition. Let be a graph with vertex set . For , let denote the number of edges with exactly one endpoint in . The edge expansion ratio of , denoted , is A sequence of -regular graphs of increasing size is called a family of expanders if there exists such that for all .
This definition admits an equivalent spectral formulation in terms of the eigenvalues of the adjacency matrix. The adjacency matrix of an -vertex graph , whose vertices are labeled , is the matrix with entries if vertices and are connected by an edge and otherwise. The matrix has real eigenvalues, which we order as If is -regular, then and . In 1984, Dodziuk proved that for any -regular graph , In particular, a sequence of -regular graphs is a family of expanders if and only if there exists such that for all . Thus, the smaller is, the better an expander becomes.
A fundamental limitation on how small can be is given by the Alon–Boppana inequality, which states that for any -regular -vertex graph , where denotes a quantity that tends to when is fixed and . In 1986, Alon conjectured that for any , “almost all” -regular -vertex graphs satisfy the opposite inequality In other words, Alon’s conjecture asserts that almost all -regular graphs are essentially optimal expanders.
This conjecture was proved by Friedman in 2008 (Friedman 2008). For an even integer , a random -regular graph on vertices is defined as a graph obtained from independent uniform permutations of .
In their recent Annals paper, Chen, Garza-Vargas, Tropp, and van Handel (Chen et al. 2026) compute the precise large-deviation behavior of in the permutation model of random regular graphs. This result can be viewed as a far-reaching strengthening of Theorem 1.
For every even , Theorem 2 allows one to compute the limit as an explicit piecewise constant function of . This provides remarkably precise information about the entire distribution of , far beyond what was previously accessible.
Theorem 2 is a consequence of the new methodology introduced in (Chen et al. 2026), based on the concept of strong convergence for random matrices. We will not discuss the technical details here, but it is worth emphasizing that this framework has many further applications. For instance, it yields a significantly shorter and simpler proof of Theorem 1, together with an explicit bound on the rate of convergence.
Another application concerns alternative models of random -regular graphs that require dramatically less randomness. Using the same ideas, the authors establish the optimal spectral gap for a model that requires only bits of randomness to generate a random graph. In later work, Cassidy (Cassidy 2024), combining the methods of (Chen et al. 2026) with new representation-theoretic techniques, proved an analogous result for a model that uses only bits of randomness for some polynomial . For comparison, the permutation model used in Theorems 1 and 2 requires roughly bits of randomness to generate .
Constructing random expander graphs with as few random bits as possible can be viewed as a step toward the goal of constructing expander graphs explicitly, without any randomness at all. The latter is an important and well-studied research direction, see this previous blog post.