Source-linked AI summary
Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
Adam Marcus, Daniel A. Spielman, Nikhil Srivastava
TL;DR
The paper asks whether infinite Ramanujan graph families can be constructed beyond previously known degrees. It proves a variant of the Bilu–Linial good-2-lift conjecture using interlacing polynomials, obtaining infinite regular bipartite families for every degree greater than 2 and irregular families bounded by universal-cover spectral radii.
Problem
Earlier Ramanujan graph constructions were sporadic, motivating the question of infinite families across all degrees and in irregular settings.
Method
The paper proves existence of a suitable signing by showing that graph-signing characteristic polynomials form an interlacing family and relating their sum to the matching polynomial.
Results
The paper establishes infinite sequences of d-regular bipartite Ramanujan graphs for every d ≥ 3 and (c, d)-biregular bipartite Ramanujan graphs for every c, d ≥ 3.
Takeaways & Limitations
Interlacing polynomials provide an existence technique for constructing regular and irregular Ramanujan graph families.
Takeaways & Limitations
The proof does not yield a polynomial-time algorithm because the relevant matching polynomial is #P-hard to compute in general.
Abstract
from arXiv · showhide
We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph. We also establish the existence of infinite families of `irregular Ramanujan' graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we prove the existence of infinite families of (c,d)-biregular bipartite graphs with all non-trivial eigenvalues bounded by sqrt{c-1}+sqrt{d-1}, for all c, d \geq 3. Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "method of interlacing polynomials'".
1 Introduction
The paper addresses the limited degree coverage of prior Ramanujan graph constructions by proving a variant of the Bilu–Linial conjecture. Its central technical contribution is the method of interlacing polynomials, which yields a suitable signing through an existence argument.
- Prior Ramanujan graph constructions were sporadic and covered only particular degrees.
- The paper proves a Bilu–Linial conjecture variant to realize their approach for constructing bipartite Ramanujan graphs of every degree.
- The method analyzes roots of expected characteristic polynomials of randomly signed adjacency matrices.
- Interlacing families guarantee a polynomial whose largest root is no greater than the largest root of the sum.
- The characteristic-polynomial sum is identified with the graph’s matching polynomial, completing the root bound.
- This paper begins a series developing interlacing polynomials, later applying the method to the Kadison–Singer problem.
2 Technical Introduction and Preliminaries
The preliminaries explain Ramanujan spectral bounds, Bilu–Linial’s 2-lift framework, and the extension to irregular graphs via universal covers. The paper’s weak signing result suffices for bipartite constructions and yields biregular families in all stated degrees.
- 2.1 Ramanujan Graphs: For d-regular graphs, Ramanujan status requires all non-trivial adjacency eigenvalues to lie within the optimal spectral range.
- 2.1 Ramanujan Graphs: Previously known infinite Ramanujan families mainly had degrees q + 1 for prime powers; this work resolves the every-degree question in the bipartite case.
- 2.2 2-Lifts: A 2-lift replaces each base vertex by a fibre of two vertices and each edge by one of two possible edge pairings.
- 2.2 2-Lifts: The 2-lift spectrum is the union of the base adjacency spectrum and the signed adjacency spectrum, called old and new eigenvalues respectively.
- 2.2 2-Lifts: The paper proves a weak Bilu–Linial conjecture controlling the largest new eigenvalue, then uses bipartite spectral symmetry to control the smallest one.
- 2.3 Irregular Ramanujan Graphs and Universal Covers: For every graph, a 2-lift exists whose new eigenvalues are below the spectral radius of its universal cover.
- 2.3 Irregular Ramanujan Graphs and Universal Covers: Iterating these lifts preserves degree distribution while doubling vertices, producing infinite irregular and (c, d)-biregular Ramanujan families.
- 2.3 Irregular Ramanujan Graphs and Universal Covers: Random-lift results provide related probabilistic spectral bounds, while the paper supplies deterministic existence results for the relevant lifts.
3 2-Lifts and The Matching Polynomial
This section connects matching polynomials to signed adjacency matrices and path trees, using their real-rootedness and spectral bounds to support good 2-lifts.
- The matching polynomial counts matchings by edge number and is defined from the sequence m_i, with m_0 = 1.
- The matching polynomial has only real roots for every graph.
- A path tree contains one vertex for each simple path from a root, with adjacency given by extending paths by one vertex.
- The matching polynomial divides the path tree's adjacency characteristic polynomial, so its roots are bounded by the path tree's spectral radius.
- The roots of the matching polynomial are bounded by the spectral radius of the graph's universal cover.
- The expected characteristic polynomial of a randomly signed adjacency matrix equals the graph's matching polynomial.
- A good lift follows by choosing a signing whose largest root is at most the largest root of the expected characteristic polynomial, using an interlacing-family argument.
4 Interlacing Families
This section defines common interlacing and interlacing families, then shows that these structures permit a polynomial choice with a controlled largest root.
- Polynomials have a common interlacing when one polynomial interlaces every member of the collection.
- If polynomials have a common interlacing, some member has largest root at most the largest root of their sum.
- The common-interlacing conclusion can fail when the polynomials lack common interlacing or their root intervals overlap improperly.
- An interlacing family requires common interlacings for every collection of polynomials obtained by fixing any proper partial assignment.
- Every interlacing family contains a full assignment whose largest root is no greater than that of the unassigned polynomial.
- For real-rooted polynomials with positive leading coefficients, common interlacing is characterized by the existence of a real-rooted sum.
5 The main result
The paper proves real-rootedness results that yield signed adjacency matrices with controlled eigenvalues, then iterates 2-lifts to construct infinite Ramanujan families.
- Real-rootedness and signing: Independent random sign choices preserve real-rootedness of the resulting characteristic-polynomial averages.This property is used to establish the interlacing-family argument.
- Signed adjacency matrices: Every graph has a signing whose signed adjacency eigenvalues are at most the spectral radius of its universal cover.For d-regular graphs, the bound is 2sqrt(d−1).
- Regular bipartite graphs: Every d-regular graph with d ≥3 has an infinite sequence of d-regular bipartite Ramanujan graphs.The construction starts from a complete bipartite graph and repeatedly applies suitable 2-lifts.
- Biregular graphs: For every c,d ≥3, there is an infinite sequence of (c,d)-biregular bipartite Ramanujan graphs.The universal cover is the infinite (c,d)-biregular tree, giving the relevant spectral-radius bound.
- Irregular graphs: Repeatedly applying the lifting theorem generates infinite irregular Ramanujan families from any finite irregular bipartite Ramanujan graph.All produced lifts retain the same universal cover.
6 Real stable polynomials
The paper proves real-rootedness through real stability, determinantal representations, and stability-preserving differential operators, obtaining the polynomial result needed for signed adjacency matrices.
- Real stability: Real stability is a multivariate generalization of real-rootedness used to analyze the relevant univariate polynomials.The target univariate polynomials arise as images of multivariate real stable polynomials under well-behaved linear transformations.
- Determinantal polynomials: Determinants of positive-semidefinite matrix combinations provide real stable multivariate polynomials.This determinantal starting point underlies the later characteristic-polynomial construction.
- Stability-preserving operators: The operator 1 + p∂u + q∂v preserves real stability for non-negative real p and q.Its stability follows by checking that 1−pu−qv cannot vanish when u and v have positive imaginary parts.
- Construction: Applying stability-preserving operators and restricting variables to real constants keeps the constructed polynomial real stable, hence real-rooted in one variable.The operators used are Ti = 1 + pi∂ui + (1−pi)∂vi.
- Application: The resulting polynomial framework proves the characteristic polynomial associated with signed adjacency matrices is real-rooted.The proof expresses the relevant matrix as a signed Laplacian plus a positive-semidefinite diagonal correction.
7 Conclusion
The conclusion frames interlacing families as a polynomial analogue of the probabilistic method while noting that the proof is not computationally efficient.
- Interlacing families: For suitable polynomial-valued random variables, some outcome has largest root no greater than the largest root of the expectation.This parallels the probabilistic-method guarantee that some outcome is no worse than the expectation.
- Interlacing families: In this paper, conditioning events correspond to fixing lift signs, and the resulting polynomial sequence forms a martingale.The martingale structure is noted but not used.
- Computational limitation: The proof does not yield a polynomial-time algorithm, and computing the matching polynomial is #P-hard in general.The authors identify efficient analogues as an open direction.
A Proof of Theorem 3.6
The matching-polynomial calculation arises by expanding a determinant and using independence of random signs to retain exactly the perfect-matching terms.
- Determinant expansion: Expanding the determinant as a sum over permutations reduces the expectation to products of signing variables.The determinant expansion is organized by permutation orbits.
- Matching-polynomial identification: Because the signs are independent with mean zero, only products containing even powers survive; these permutations consist solely of two-cycles, corresponding to perfect matchings.Odd-sized vertex sets therefore contribute no perfect matchings.