Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees

Introduction

Ramanujan graphs have been the focus of substantial study in Theoretical Computer Science and Mathematics. They are graphs whose non-trivial adjacency matrix eigenvalues are as small as possible. Previous constructions of Ramanujan graphs have been sporadic, only producing Ramanujan graphs of particular degrees. In this paper, we prove a variant of a conjecture of Bilu and Linial , and use it to realize an approach they suggested for constructing bipartite Ramanujan graphs of every degree.

Our main technical contribution is a novel existence argument. The conjecture of Bilu and Linial requires us to prove that every graph has a signed adjacency matrix with all of its eigenvalues in a small range. We do this by proving that the roots of the expected characteristic polynomial of a randomly signed adjacency matrix lie in this range. In general, a statement like this is useless, as the roots of a sum of polynomials do not necessarily have anything to do with the roots of the polynomials in the sum. However, there seem to be many sums of combinatorial polynomials for which this intuition is wrong. With this in mind, we identify certain special collections of polynomials which we call “interlacing families”, and prove that such families always contain a polynomial whose largest root is at most the largest root of the sum. We show that the polynomials arising from signings of a graph form such a family. To finish the proof, we then bound the largest root of the sum of the characteristic polynomials of the signed adjacency matrices of a graph by observing that this sum is the well-studied matching polynomial of the graph.

This paper is the first one in a series which develops the method of interlacing polynomials. In the next paper , we use the method to give a positive resolution to the Kadison–Singer problem.

Technical Introduction and Preliminaries

Ramanujan graphs are defined in terms of the eigenvalues of their adjacency matrices. If $G$ is a $d$-regular graph and $A$ is its adjacency matrix, then $d$ is always an eigenvalue of $A$. The matrix $A$ has an eigenvalue of $-d$ if and only if $G$ is bipartite. The eigenvalues of $d$, and $-d$ when $G$ is bipartite, are called the trivial eigenvalues of $A$. Following Lubotzky, Phillips and Sarnak , we say that a $d$-regular graph is Ramanujan if all of its non-trivial eigenvalues lie between $-2\sqrt{d-1}$ and $2\sqrt{d-1}$. It is easy to construct Ramanujan graphs with a small number of vertices: $d$-regular complete graphs and complete bipartite graphs are Ramanujan. The challenge is to construct an infinite family of $d$-regular graphs that are all Ramanujan. One cannot construct infinite families of $d$-regular graphs whose eigenvalues lie in a smaller range: the Alon–Boppana bound (see ) tells us that for every constant $\epsilon>0$, every sufficiently large $d$-regular graph has a non-trivial eigenvalue with absolute value at least $2\sqrt{d-1}-\epsilon$.

Lubotzky, Phillips and Sarnak and Margulis were the first to construct infinite families of Ramanujan graphs of constant degree. They built both bipartite and non-bipartite Ramanujan graphs from Cayley graphs. All of their graphs are regular and have degrees $p+1$ where $p$ is a prime. There have been very few other constructions of Ramanujan graphs . To the best of our knowledge, the only degrees for which infinite families of Ramanujan graphs were previously known to exist were those of the form $q+1$ where $q$ is a prime power. Lubotzky [29, Problem 10.7.3] asked whether there exist infinite families of Ramanujan graphs of every degree greater than 2. We resolve this conjecture in the affirmative in the bipartite case.

2 2-Lifts

Bilu and Linial suggested constructing Ramanujan graphs through a sequence of 2-lifts of a base graph. Given a graph $G=(V,E)$, a 2-lift of $G$ is a graph that has two vertices for each vertex in $V$. This pair of vertices is called the fibre of the original vertex. Every edge in $E$ corresponds to two edges in the 2-lift. If $(u,v)$ is an edge in $E$, $\left\{u_{0},u_{1}\right\}$ is the fibre of $u$, and $\left\{v_{0},v_{1}\right\}$ is the fibre of $v$, then the 2-lift can either contain the pair of edges

If only edge pairs of the first type appear, then the 2-lift is just two disjoint copies of the original graph. If only edge pairs of the second type appear, then we obtain the double-cover of $G$.

To analyze the eigenvalues of a 2-lift, Bilu and Linial study signings $s:E\rightarrow\left\{\pm 1\right\}$ of the edges of $G$. They place signings in one-to-one correspondence with 2-lifts by setting $s(u,v)=1$ if edges of type (1) appear in the 2-lift, and $s(u,v)=-1$ if edges of type (2) appear. They then define the signed adjacency matrix $A_{s}$ to be the same as the adjacency matrix of $G$, except that the entries corresponding to an edge $(u,v)$ are $s(u,v)$. They prove [5, Lemma 3.1] that the eigenvalues of the 2-lift are the union, taken with multiplicity, of the eigenvalues of the adjacency matrix $A$ and those of the signed adjacency matrix $A_{s}$. Following Friedman , they refer to the eigenvalues of $A$ as the old eigenvalues and the eigenvalues of $A_{s}$ as the new eigenvalues. The main result of their paper is that every graph of maximal degree $d$ has a signing in which all of the new eigenvalues have absolute value at most $O(\sqrt{d\log^{3}d})$. They then build arbitrarily large $d$-regular expander graphs by repeatedly taking 2-lifts of a complete graph on $d+1$ vertices.

Bilu and Linial conjectured that every $d$-regular graph has a signing in which all of the new eigenvalues have absolute value at most $2\sqrt{d-1}$. If one repleatedly applied the corresponding 2-lifts to the $d$-regular complete graph, one would obtain an infinite sequence of $d$-regular Ramanujan graphs. We prove a weak version of Bilu and Linial’s conjecture: every $d$-regular graph has a signing in which all of the new eigenvalues are at most $2\sqrt{d-1}$. The difference between our result and the original conjecture is that we do not control the smallest new eigenvalue. This is why we consider bipartite graphs. The eigenvalues of the adjacency matrices of bipartite graphs are symmetric about zero (see, for example, [16, Theorem 2.4.2]). So, a bound on the smallest non-trivial eigenvalue follows from a bound on the largest. We also use the fact that a 2-lift of a bipartite graph is also bipartite. By repeatedly applying the corresponding 2-lifts to the $d$-regular complete bipartite graph, we obtain an infinite sequence of $d$-regular bipartite Ramanujan graphs.

3 Irregular Ramanujan Graphs and Universal Covers

We say that a bipartite graph is $(c,d)$-biregular if all vertices on one side of the bipartition have degree $c$ and all vertices on the other side have degree $d$. The adjacency matrix of a $(c,d)$-biregular graph always has eigenvalues $\pm\sqrt{cd}$; these are its trivial eigenvalues. Feng and Li (see also ) prove a generalization of the Alon–Boppana bound that applies to $(c,d)$-biregular graphs: for all $\epsilon>0$, all sufficiently large $(c,d)$-biregular graphs have a non-trivial eigenvalue that is at least $\sqrt{c-1}+\sqrt{d-1}-\epsilon$. Thus, we say that a $(c,d)$-biregular graph is Ramanujan if all of its non-trivial eigenvalues have absolute value at most $\sqrt{c-1}+\sqrt{d-1}.$ We prove the existence of infinite families of $(c,d)$-biregular Ramanujan graphs for all $c,d\geq 3$.

The adjacency matrix $A_{T}$ of the universal cover $T$ is an infinite-dimensional symmetric matrix. We will be interested in the spectral radius $\rho(T)$ of $T$, which may be definedIn functional analysis, the spectral radius of an infinite-dimensional operator $A$ is traditionally defined to be the largest $\lambda$ for which $(A-\lambda I)$ is unbounded. However, in the case of self-adjoint operators, this definition is equivalent to the one presented here (see, for example, Theorem VI.6 in ). as:

where $\|x\|_{2}^{2}:=\sum_{i=1}^{\infty}x(i)^{2}$ whenever the series converges. Naturally, the spectral radius of a finite tree is defined to be the norm of its adjacency matrix.

With these notions in hand, we can state the definition of an irregular Ramanujan graph. As before, the largest (and smallest, in the bipartite case) eigenvalues of finite adjacency matrices are considered trivial. Greenberg (see also ) showed that for every $\epsilon>0$ and every infinite family of graphs that have the same universal cover $T$, all sufficiently large graphs in the family have a non-trivial eigenvalue that is at least $\rho(T)-\epsilon$. Following Hoory, Linial, and Wigderson [23, Definition 6.7], we therefore define an arbitrary graph to be Ramanujan if all of its non-trivial eigenvalues are smaller in absolute value than the spectral radius of its universal cover.

The universal cover of every $d$-regular graph is the infinite $d$-ary tree, whereas the universal cover of every $(c,d)$-biregular graph is the infinite $(c,d)-$biregular tree in which the degrees alternate between $c$ and $d$ on every other level . The former tree is known to have spectral radius $2\sqrt{d-1}$ while the latter has a spectral radius of $\sqrt{c-1}+\sqrt{d-1}$ (see ). Thus, a definition based on universal covers generalizes both the regular and biregular definitions of Ramanujan graphs, and the bound of Greenberg generalizes both the Alon-Boppana and Feng-Li bounds.

In this general setting, we show that every graph $G$ has a 2-lift in which all of the new eigenvalues are less than the spectral radius of its universal cover. Applying these 2-lifts inductively to any finite irregular bipartite Ramanujan graph yields an infinite family of irregular bipartite Ramanujan graphs whose degree distribution matches that of the initial graph (since taking a 2-lift simply doubles the number of vertices of each degree). In particular, applying them to the $(c,d)$-biregular complete bipartite graph yields an infinite family of $(c,d)$-biregular Ramanujan graphs. As far as we know, infinite families of irregular Ramanujan graphs were not known to exist prior to this work.

4 Related Work

There have been numerous studies of random lifts of graphs. For some results on the spectra of random lifts, we point the reader to . Friedman has proved that almost every $d$-regular graph almost meets the Ramanujan bound: he shows that for every $\epsilon>0$ the absolute value of all the non-trivial eigenvalues of almost every sufficiently large $d$-regular graph are at most $2\sqrt{d-1}+\epsilon$. In the irregular case, Puder has shown that with high probability a high-order lift of a graph $G$ has new eigenvalues that are bounded in absolute value by $\sqrt{3}\rho$, where $\rho$ is the spectral radius of the universal cover of $G$.

We remark that constructing bipartite Ramanujan graphs is at least as easy as constructing non-bipartite ones: the double-cover of a $d$-regular non-bipartite Ramanujan graph is a $d$-regular bipartite Ramanujan graph. For many applications of expander graphs, we refer the reader to . For those applications of expanders that just require upper bounds on the second eigenvalue, one can use bipartite Ramanujan graphs. Some applications actually require bipartite expanders, while others require the non-bipartite ones. For example, the explicit constructions of error correcting codes of Sipser and Spielman require non-bipartite expanders, while the improvements of their construction require bipartite Ramanujan expanders.

2-Lifts and The Matching Polynomial

For a graph $G$, let $m_{i}$ denote the number of matchings in $G$ with $i$ edges. Set $m_{0}=1$. Heilmann and Lieb defined the matching polynomial of $G$ to be the polynomial

where $n$ is the number of vertices in the graph. They proved two remarkable theorems about the matching polynomial that we will exploit in this paper. It is worth mentioning that the proofs of these theorems are elementary and short, relying only on simple recurrence formulas for the matching polynomial.

For every graph $G$, $\mu_{G}(x)$ has only real roots.

For every graph $G$ of maximum degree $d$, all of the roots of $\mu_{G}(x)$ have absolute value at most $2\sqrt{d-1}$.

The preceding theorems will allow us to prove the existence of infinite families of $d$-regular bipartite Ramanujan graphs. To handle the irregular case, we will require a refinement of these results due to Godsil. This refinement uses the concept of a path tree, which was also introduced by Godsil (see or [16, Section 6]). Recall that a path in $G$ is a walk that does not visit any vertex twice.

The path tree provides a natural relationship between the roots of the matching polynomial of a graph and the spectral radius of its universal cover:

Let $P(G,u)$ be a path tree of $G$. Then the matching polynomial of $G$ divides the characteristic polynomial of the adjacency matrix of $P(G,u)$. In particular, all of the roots of $\mu_{G}(x)$ are real and have absolute value at most $\rho(P(G,u))$.

Let $G$ be a graph and let $T$ be its universal cover. Then the roots of $\mu_{G}(x)$ are bounded in absolute value by $\rho(T)$.

Let $u$ be any vertex of $G$ and let $P$ be the path tree rooted at $u$. Since the paths that correspond to the vertices of $P$ are themselves non-backtracking walks (as defined in Section 2.3), $P$ is a finite induced subgraph of the universal cover $T$, and $A_{P}$ is a finite submatrix of $A_{T}$. By Theorem 3.4, the roots of $\mu_{G}$ are bounded by

We remark that one can directly prove an upper bound of $2\sqrt{d-1}$ on the spectral radius of a path tree of a $d$-regular graph and an upper bound of $\sqrt{c-1}+\sqrt{d-1}$ on the spectral radius of a path tree of a $(c,d)$-regular bipartite graph without considering infinite trees. We point the reader to Section 5.6 of Godsil’s book for an elementary argument.

We now recall an identity of Godsil and Gutman: the expected characteristic polynomial of a random signing of the adjacency matrix of a graph is equal to its matching polynomial. To associate a signing of the edges of $G$ with a vector in $\left\{\pm 1\right\}^{m}$, we choose an arbitrary ordering of the $m$ edges of $G$, denote the edges by $e_{1},\dotsc,e_{m}$, and denote a signing of these edges by $s\in\left\{\pm 1\right\}^{m}$. We then let $A_{s}$ denote the signed adjacency matrix corresponding to $s$, and define $f_{s}(x)=\det\left(xI-A_{s}\right)$ to be characteristic polynomial of $A_{s}$.

For the convenience of the reader, we present a simple proof of this theorem in Appendix A.

Interlacing Families

We say that a polynomial $g(x)=\prod_{i=1}^{n-1}(x-\alpha_{i})$ interlaces a polynomial $f(x)=\prod_{i=1}^{n}(x-\beta_{i})$ if

We say that polynomials $f_{1},\dotsc,f_{k}$ have a common interlacing if there is a polynomial $g$ so that $g$ interlaces $f_{i}$ for each $i$.

Let $\beta_{i,j}$ be the $j$th smallest root of $f_{i}$. The polynomials $f_{1},\dotsc,f_{k}$ have a common interlacing if and only if there are numbers $\alpha_{0}\leq\alpha_{1}\leq\dotsb\leq\alpha_{n}$ so that $\beta_{i,j}\in[\alpha_{j-1},\alpha_{j}]$ for all $i$ and $j$. The numbers $\alpha_{1},\dotsc,\alpha_{n-1}$ come from the roots of the polynomial $g$, and $\alpha_{0}$ ($\alpha_{n}$) can be chosen to be any number that is smaller (larger) than all of the roots of all of the $f_{i}$.

Let $f_{1},\dotsc,f_{k}$ be polynomials of the same degree that are real-rooted and have positive leading coefficients. Define

If $f_{1},\dotsc,f_{k}$ have a common interlacing, then there exists an $i$ so that the largest root of $f_{i}$ is at most the largest root of $f_{\emptyset}$.

Let the polynomials be of degree $n$. Let $g$ be a polynomial that interlaces all of the $f_{i}$, and let $\alpha_{n-1}$ be the largest root of $g$. As each $f_{i}$ has a positive leading coefficient, it is positive for sufficiently large $x$. As each $f_{i}$ has exactly one root that is at least $\alpha_{n-1}$, each $f_{i}$ is non-positive at $\alpha_{n-1}$. So, $f_{\emptyset}$ is also non-positive at $\alpha_{n-1}$, and eventually becomes positive. This tells us that $f_{\emptyset}$ has a root that is at least $\alpha_{n-1}$, and so its largest root is at least $\alpha_{n-1}$. Let $\beta_{n}$ be this root.

As $f_{\emptyset}$ is the sum of the $f_{i}$, there must be some $i$ for which $f_{i}(\beta_{n})\geq 0$. As $f_{i}$ has at most one root that is at least $\alpha_{n-1}$, and $f_{i}(\alpha_{n-1})\leq 0$, the largest root of $f_{i}$ is it at least $\alpha_{n-1}$ and at most $\beta_{n}$. ∎

One can show that the assumptions of the lemma imply that $f_{\emptyset}$ is itself a real-rooted polynomial. The conclusion of the lemma also holds for the $k$th largest root by a similar argument. However, we will not require these facts here.

If the polynomials do not have a common interlacing, the sum may fail to be real rooted: consider $(x+1)(x+2)+(x-1)(x-2)$. Even if the sum of two polynomials is real rooted, the conclusion of Lemma 4.2 may fail to hold if the interval containing the largest roots of each polynomial overlaps the interval containing their second-largest roots. For example, consider the sum of the polynomials $(x+5)(x-9)(x-10)$ and $(x+6)(x-1)(x-8)$. It has roots at approximately $-5.3$, $6.4$, and $7.4$, so its largest root is smaller than the largest root of both polynomials of which it is the sum.

Let $S_{1},\dots,S_{m}$ be finite sets and for every assignment $s_{1},\dots,s_{m}\in S_{1}\times\dots\times S_{m}$ let $f_{s_{1},\dots,s_{m}}(x)$ be a real-rooted degree $n$ polynomial with positive leading coefficient. For a partial assignment $s_{1},\dots,s_{k}\in S_{1}\times\ldots\times S_{k}$ with $k<m$, define

We say that the polynomials $\{f_{s_{1},\dots,s_{m}}\}_{s_{1},\dots,s_{m}}$ form an interlacing family if for all $k=0,\ldots,m-1$, and all $s_{1},\dots,s_{k}\in S_{1}\times\dots\times S_{k}$, the polynomials

Let $S_{1},\dots,S_{m}$ be finite sets and let $\left\{f_{s_{1},\dots,s_{m}}\right\}$ be an interlacing family of polynomials. Then, there exists some $s_{1},\dots,s_{m}\in S_{1}\times\dots\times S_{m}$ so that the largest root of $f_{s_{1},\dots,s_{m}}$ is less than the largest root of $f_{\emptyset}$.

From the definition of an interlacing family, we know that the polynomials $\{f_{t}\}$ for ${t\in S_{1}}$ have a common interlacing and that their sum is $f_{\emptyset}$. So, Lemma 4.2 tells us that one of the polynomials has largest root at most the largest root of $f_{\emptyset}$. We now proceed inductively. For any $s_{1},\dots,s_{k}$, we know that the polynomials $\{f_{s_{1},\dots,s_{k},t}\}$ for $t\in S_{k+1}$ have a common interlacing and that their sum is $f_{s_{1},\dots,s_{k}}$. So, for some choice of $t$ (say $s_{k+1}$) the largest root of the polynomial $f_{s_{1},\dots,s_{k+1}}$ is at most the largest root of $f_{s_{1},\dots,s_{k}}$. ∎

We will prove that the polynomials $\left\{f_{s}\right\}_{s\in\left\{\pm 1\right\}^{m}}$ defined in Section 3 are an interlacing family. According to definition 4.3, this requires establishing the existence of certain common interlacings. There is a systematic way to do this based on the fact that common interlacings are equivalent to real-rootedness statements. In particular the following result seems to have been discovered a number of times. It appears as Theorem $2.1$ of Dedieu , (essentially) as Theorem $2^{\prime}$ of Fell , and as (a special case of) Theorem 3.6 of Chudnovsky and Seymour .

Let $f_{1},\ldots,f_{k}$ be (univariate) polynomials of the same degree with positive leading coefficients. Then $f_{1},\ldots,f_{k}$ have a common interlacing if and only if $\sum_{i=1}^{k}\lambda_{i}f_{i}$ is real rooted for all convex combinations $\lambda_{i}\geq 0,\sum_{i=1}^{k}\lambda_{i}=1$.

The main result

Our proof that the polynomials $\left\{f_{s}\right\}_{s\in\left\{\pm 1\right\}^{m}}$ form an interlacing family relies on the following generalization of the fact that the matching polynomial is real-rooted. It amounts to saying that if we pick each sign independently with any probabilities, then the resulting polynomial is still real-rooted.

Let $p_{1},\dotsc,p_{m}$ be numbers in $$. Then, the following polynomial is real-rooted

We will prove this theorem using machinery that we develop in Section 6. It immediately implies our main technical result as follows.

The polynomials $\left\{f_{s}\right\}_{s\in\left\{\pm 1\right\}^{m}}$ are an interlacing family.

We will show that for every $0\leq k\leq m-1$, every partial assignment $s_{1}\in\pm 1,\dotsc,s_{k}\in\pm 1$, and every $\lambda\in$, the polynomial

is real-rooted. The theorem will then follow from Lemma 4.5.

To show that the above polynomial is real-rooted, we apply Theorem 5.1 with $p_{k+1}=\lambda$, $p_{k+2},\dotsc,p_{m}=1/2$, and $p_{i}=(1+s_{i})/2$ for $1\leq i\leq k$. ∎

Let $G$ be a graph with adjacency matrix $A$ and universal cover $T$. Then there is a signing $s$ of $A$ so that all of the eigenvalues of $A_{s}$ are at most $\rho(T)$. In particular, if $G$ is $d$-regular, there is a signing $s$ so that the eigenvalues of $A_{s}$ are at most $2\sqrt{d-1}$.

The first statement follows immediately from Theorems 4.4 and 5.2 and Lemma 3.5. The second statement follows by noting that the universal cover of a $d$-regular graph is the infinite $d$-regular tree, which has spectral radius at most $2\sqrt{d-1}$, or by directly appealing to Theorem 3.2. ∎

Every non-trivial eigenvalue of a complete $(c,d)$-biregular graph is zero.

The adjacency matrix of this graph has rank $2$, so all its eigenvalues other than $\pm\sqrt{cd}$ must be zero. ∎

For every $d\geq 3$ there is an infinite sequence of $d$-regular bipartite Ramanujan graphs.

We know from Lemma 5.4 that the complete bipartite graph of degree $d$ is Ramanujan. By Lemma 3.1 of and Theorem 5.3, for every $d$-regular bipartite Ramanujan graph $G$, there is a 2-lift in which every non-trivial eigenvalue is at most $2\sqrt{d-1}$. As the 2-lift of a bipartite graph is bipartite, and the eigenvalues of a bipartite graph are symmetric about , this 2-lift is also a regular bipartite Ramanujan graph.

Thus, for every $d$-regular bipartite Ramanujan graph $G$, there is another $d$-regular bipartite Ramanujan graph with twice as many vertices. ∎

For every $c,d\geq 3$, there is an infinite sequence of $(c,d)$-biregular bipartite Ramanujan graphs.

We know from Lemma 5.4 that the complete $(c,d)$-biregular is Ramanujan. We will use this as a base for a construction of an infinite sequence of $(c,d)$-biregular bipartite Ramanujan graphs. Let $G$ be any $(c,d)$-biregular bipartite Ramanujan graph. As mentioned in Section 2.3, the universal cover of $G$ is the infinite $(c,d)$-biregular tree, which has spectral radius $\sqrt{c-1}+\sqrt{d-1}$. Thus, Theorem 5.3 tells us that there is a 2-lift of $G$ with all new eigenvalues at most $\sqrt{c-1}+\sqrt{d-1}$. As this graph is bipartite, all of its non-trivial eigenvalues have absolute value at most $\sqrt{c-1}+\sqrt{d-1}$. So, the resulting $2$-lift is a larger $(c,d)$-biregular bipartite Ramanujan graph. ∎

To conclude the section, we remark that repeated application of Theorem 5.3 can be used to generate an infinite sequence of irregular Ramanujan graphs from any finite irregular bipartite Ramanujan graph, since all of the lifts produced will have the same universal cover. In contrast, Lubotzky and Nagnibeda have shown that there exist infinite trees that cover infinitely many finite graphs but such that none of the finite graphs are Ramanujan.

Real stable polynomials

In this section we will establish the real-rootedness of a class of polynomials which includes the polynomials of Theorem 5.1. We will do this by considering a multivariate generalization of real-rootedness called real stability (see, e.g., the surveys ). In particular, we will show that the univariate polynomials we are interested in are the images, under a well-behaved linear transformation, of a multivariate real stable polynomial.

whenever the imaginary part of every $z_{i}$ is strictly positive.

Note that a real stable polynomial has real coefficients, but may be evaluated on complex inputs.

We begin by considering certain determinantal polynomials whose real stability is guaranteed by the following lemma, which may be found in Borcea and Brändén [6, Proposition 2.4].

Let $A_{1},\dots,A_{m}$ be positive semidefinite matrices. Then

Then $T$ preserves real stability if and only if $F_{T}(z,-w)$ is real stable.

We will use a special case of this result.

For non-negative real numbers $p$ and $q$ and variables $u$ and $v$, the operator $T=1+p\partial_{u}+q\partial_{v}$ preserves real stability.

We just need to show that the polynomial $1-pu-qv$ is real stable. To see this, consider $u$ and $v$ with positive imaginary parts. The imaginary part of $1-pu-qv$ will then be negative, and so cannot be zero. ∎

We now show how operators of the preceding kind can be used to generate the expected characteristic polynomials that appears in Theorem 5.1.

For an invertible matrix $A$, vectors $a$ and $b$, and a number $p\in$,

The matrix determinant lemma (see, e.g., ) states that for every nonsingular matrix $A$ and every real number $t$,

One consequence of this is Jacobi’s formula for the derivative of the determinant:

By the matrix determinant lemma, this equals

Using these tools, we prove our main technical result on real-rootedness.

Let $u_{1},\dots,u_{m}$ and $v_{1},\dots,v_{m}$ be formal variables and define

Lemma 6.2 implies that $Q$ is real stable.

where $T_{i}=1+p_{i}\partial_{u_{i}}+(1-p_{i})\partial_{v_{i}}$. To see this, we prove by induction on $k$ that

The base case ($k=0$) is trivially true, as it is the definition of $Q$. The inductive step follows from Lemma 6.5. The case $k=m$ is exactly the claimed identity.

Starting with $Q$ (a real stable polynomial) we can then apply Corollary 6.4 and the closure of real stable polynomials under the restrictions of variables to real constants to see that each of the polynomials above, including $P(x)$, is also real stable. As $P(x)$ is real stable and has one variable, it is real-rooted. ∎

Alternatively, one can prove Theorem 6.6 by observing that $P$ is a mixed characteristic polynomial and then applying results of the second paper in this series .

For each vertex $u$, let $d_{u}$ be its degree, and let $d=\max_{u}d_{u}$. We need to prove that the polynomial

is real-rooted. This is equivalent to proving that the the following polynomial is real-rooted

We now observe that the matrix $dI-A_{s}$ is a signed Laplacian matrix of $G$ plus a nonnegative diagonal matrix. For each edge $(u,v)$, define the rank $1$-matrices

where $e_{u}$ is the elementary unit vector in direction $u$. Consider a signing $s$ and let $s_{u,v}$ denote the sign it assigns to edge $(u,v)$. Since the original graph had maximum degree $d$, we have

where $D$ is the diagonal matrix whose $u$th diagonal entry equals $d-d_{u}$. As the diagonal entries of $D$ are non-negative, it is positive semidefinite. If we now set $a_{u,v}=(e_{u}-e_{v})$ and $b_{u,v}=(e_{u}+e_{v})$, we can express the polynomial in (4) as

The fact that this polynomial is real-rooted now follows from Theorem 6.6. ∎

Conclusion

Like many applications of the probabilistic method, our proof does not yield a polynomial-time algorithm. In the particular case of random lifts, the polynomial $f_{\emptyset}$ is itself a matching polynomial, which is $\#P$-hard to compute in general. It would certainly be interesting to find computationally efficient analogues of our method.

Acknowledgment

This research was partially supported by NSF grants CCF-0915487 and CCF-1111257, an NSF Mathematical Sciences Postdoctoral Research Fellowship, Grant No. DMS-0902962, a Simons Investigator Award, and a MacArthur Fellowship.

We thank James Lee for suggesting Lemma 6.5 and the simpler proof of Theorem 6.6 that appears here. We thank Mirkó Visontai for bringing references , , , and to our attention.

References

Appendix A Proof of Theorem 3.6