PaperlayerView exact revision on arXiv

Source-linked AI summary

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

Adam W. Marcus, Nikhil Srivastava, Daniel A. Spielman

arXiv:1505.08010v1math.CO

TL;DR

The paper addresses the open question of whether bipartite Ramanujan graphs exist at every degree and every number of vertices. It analyzes expected characteristic polynomials of random matching unions, proving their real-rootedness and interlacing properties and bounding their roots to establish the existence result.

  • Problem

    Although infinite families of bipartite Ramanujan graphs were known for every degree m ≥3, existence for every number of vertices was unknown.

    Source: §1 · p. 2

  • Method

    The paper analyzes expected characteristic polynomials of random perfect-matching unions using interlacing families, a formula for random permutations, and finite free convolution root bounds.

    Source: §1 · p. 2, §1.3 · p. 4, §3 · p. 10

  • Results

    A union of m random perfect matchings across a bipartition is Ramanujan with nonzero probability, yielding bipartite Ramanujan graphs of every degree and size.

    Source: §1.1 · p. 2, §1 · p. 2

  • Takeaways & Limitations

    The result establishes existence of optimal spectral expander graphs across all degrees and sizes.

    Source: §1 · p. 2

    The graphs may have multiple edges, and the paper establishes existence but does not give a polynomial-time construction.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices. The proof is based on analyzing the expected characteristic polynomial of a union of random perfect matchings, and involves three ingredients: (1) a formula for the expected characteristic polynomial of the sum of a regular graph with a random permutation of another regular graph, (2) a proof that this expected polynomial is real rooted and that the family of polynomials considered in this sum is an interlacing family, and (3) strong bounds on the roots of the expected characteristic polynomial of a union of random perfect matchings, established using the framework of finite free convolutions we recently introduced.

1 Introduction

The paper proves that bipartite Ramanujan graphs exist at every degree and size by analyzing expected characteristic polynomials of unions of random perfect matchings. It establishes the needed polynomial properties and root bounds, while also identifying scope limits for its non-bipartite result and constructions.

1 Introduction

  • The work develops a real-rooted class of expected characteristic polynomials with interlacing properties and root bounds stronger than the cited barrier-method argument.These polynomials are computable in polynomial time, unlike most other known expected characteristic polynomials; the contribution is shared with [MSS15a].Source: §1 · p. 2

1.1 Summary of Results

  • A union of m independent random perfect matchings across a bipartition is Ramanujan with nonzero probability, establishing existence for every degree and size.The theorem considers m ≥3.Source: §1.1 · p. 2, §1 · p. 2
  • The non-bipartite theorem does not itself produce Ramanujan graphs because it gives no control of the least eigenvalue λ_d.The constructed graphs may have multiple edges, and the paper proves existence rather than providing a polynomial-time construction.Source: §1.1 · p. 3

1.2 Related Work

  • Although infinite families were known for every degree m ≥3, existence for every number of vertices remained open.Earlier constructions covered degrees m = p + 1 for prime p [Mar88, LPS88], while random regular graphs were shown to be almost Ramanujan.Source: §1.2 · p. 3

1.3 Outline of the Paper

  • Random permutations are decomposed into two-vertex swaps to prove real-rootedness and interlacing for expected characteristic polynomials.The swap transformations preserve real-rootedness properties of certain multivariate polynomials; the argument is elementary and self-contained.Source: §1.3 · p. 3
  • A closed-form formula for expected characteristic polynomials of randomly permuted regular graphs follows from replacing permutation averages with orthogonal-matrix averages.The paper relates this replacement to determinants' multilinearity and low-degree Fourier coefficients.Source: §1.3 · p. 4
  • Finite free additive convolution expresses the expected polynomial of a union of m random matchings as the m-wise convolution of a single matching's characteristic polynomial.Root bounds from [MSS15a] yield the desired Ramanujan bound.Source: §1.3 · p. 4

2 Preliminaries

The preliminaries introduce interlacing families as a route from expected-polynomial roots to existence results, then set out finite free convolutions and Cauchy transforms as tools for analyzing those roots.

2.1 Interlacing Families

  • Interlacing-family results provide an existence guarantee from a family of real-rooted polynomials and their expected polynomial under product distributions.The section recalls the theorem for families indexed by {0,1}^m and product distributions.Source: §2.1 · p. 4

2.2 Finite Free Convolutions of Polynomials

  • Finite free additive convolution expresses expected characteristic polynomials for randomly orthogonally conjugated matrix sums as an operation on the input characteristic polynomials.The expected polynomial is well-defined from the input polynomials because the eigenvalue distribution of A + QBQ^T depends only on the eigenvalues of A and B.Source: §2.2 · p. 5

2.3 Cauchy Transforms

  • The Cauchy transform and its inverse provide a way to bound the largest root of a real-rooted polynomial.The inverse transform is the unique value above all roots at which the Cauchy transform equals its argument, and approaches the largest root as that argument tends to infinity.Source: §2.3 · pp. 6–7
  • The cited convolution bounds strengthen the univariate barrier-function argument introduced in.The section identifies the barrier-function case by taking q(x) = x^(d−1)(x − d), for which p(x) + q(x) = p(x) − p′(x).Source: §2.3 · p. 7

3 Interlacing for Permutations

This section establishes real-rootedness and interlacing for expected characteristic polynomials generated by products of independent random swaps. Since uniform random permutations can be realized by swaps, the result supplies an existence guarantee for suitable permutation choices.

3 Interlacing for Permutations

  • A random swap is either a fixed transposition or the identity, and products of independent swaps can realize uniformly random permutation matrices.The paper gives an inductive construction for uniform permutations and separately realizes direct sums of permutations.Source: §3 · pp. 7–8
  • Expected characteristic polynomials generated by independent random swaps are real-rooted, yielding an interlacing-family existence guarantee for suitable permutation choices.The permutation result applies when the independent random permutations are realizable by swaps.Source: §3 · p. 8
  • Random swaps preserve determinant-likeness, the structural property used to establish real-rootedness of the resulting expected characteristic polynomials.The proof characterizes determinant-like polynomials through hyperbolicity and rank-1 linearity; the determinant of a sum of matrices is an example.Source: §3 · p. 9
  • The interlacing argument uses the fact that a transposition changes a symmetric matrix by a rank-2, trace-zero update.Rank-1 updates interlace for determinant-like polynomials, allowing the two polynomials in a swap’s convex combination to have a common interlacing.Source: §3 · pp. 10–11

4 Quadrature

The section develops quadrature identities for expected characteristic polynomials, expressing them through free convolutions and relating permutation averages in expected determinants to orthogonal-matrix averages. It treats the symmetric and bipartite cases, including bipartite block matrices and extensions to multiple matrices with independent uniformly random permutations, and derives explicit formulas and a way to bound roots.

4 Quadrature

  • After removing the trivial all-ones eigenvalue, the expected polynomials are free convolutions of perfect-matching characteristic polynomials, enabling explicit formulas and root bounds.The symmetric case contains the main ideas, and the bipartite result follows from it.Source: §4 · p. 11

4.2 Quadrature for Bipartite Matrices

  • The bipartite case extends the quadrature argument to nonsymmetric matrices with shared all-ones left and right eigenvectors, using independent uniform permutations.The section isolates the common all-ones eigenvector and presents the bipartite result as a corollary of the symmetric case.Source: §4 · p. 11, §4.2 · p. 17

4.1 Quadrature for Symmetric Matrices

  • Theorem 4.1 gives the expected characteristic polynomial for a randomly permuted sum of symmetric constant-row-sum matrices in terms of their reduced characteristic polynomials and the trivial eigenvalue factor.For regular graphs, this computes the expected characteristic polynomial of the adjacency matrix of their sum when one graph is randomly permuted.Source: §4.1 · p. 12
  • The Quadrature Theorem equates the determinant averaged over permutation conjugations with its average over Haar-random orthogonal conjugations.The proof uses invariance under elementary transformations on three simplex vertices; determinants have degree at most two in rotations on the associated two-dimensional subspace.Source: §4.1 · p. 13

4.2 Quadrature for Bipartite Matrices

  • For bipartite block matrices, the expected determinant with a random permutation block P⊕I equals the expectation with an orthogonal block Q⊕I.The proof applies the preceding argument with P⊕I and Q⊕I in place of P and Q.Source: §4.2 · p. 18
  • Theorem 4.11 converts the expected determinant with independent permutation matrices P and S into successive averages over independent orthogonal matrices Q and R.The proof uses independence of P and S and applies Corollary 4.12 to replace each permutation average.Source: §4.2 · p. 18
  • Theorem 4.10 extends the quadrature identity to many matrices, with independent uniformly random permutation matrices.The extension follows from Theorem 4.11 and the preceding identities; the proof of Corollary 4.13 is omitted as identical to that of Corollary 4.9.Source: §4.2 · p. 19

5 Ramanujan Graphs

The proof bounds the roots of the expected characteristic polynomial using finite free convolution and inverse Cauchy transforms. For bipartite unions of random perfect matchings, these bounds yield the Ramanujan eigenvalue threshold with nonzero probability.

5 Ramanujan Graphs

  • A union of m random perfect matchings across a bipartition has the required eigenvalue bounds with nonzero probability.The proof uses swaps to establish the probability statement for the random matchings.Source: §5 · pp. 19–20
  • After removing the trivial root at 1, the polynomial whose largest root is bounded is the m-wise additive convolution of a single matching's characteristic polynomial.Its largest root is the second-largest root of the original expected polynomial.Source: §5 · p. 19
  • The expected-polynomial formula also applies to arbitrary regular adjacency matrices.Source: §5 · p. 19
  • The proof bounds the inverse Cauchy transform of the convolution using the convolution inequality applied m−1 times.The resulting calculation yields the root bound 2√(m−1).Source: §5 · pp. 20–21
  • The second-largest root is at most 2√(m−1), and bipartite spectral symmetry gives the corresponding lower bound −2√(m−1).Source: §5 · pp. 20–21
  • The bipartite adjacency matrix is formed from independent random permutation matrices acting on the matchings across the same bipartition.The distribution of these permutations is realizable by swaps, allowing the interlacing result to give a nonzero-probability conclusion.Source: §5 · p. 20
Loading 1505.08010v1…