The roots every matching polynomial keeps real

Coins hidden in the roots found that the polynomial counting permutations by descents has only real roots, and that this one fact makes the descent count a sum of independent coins nobody can point to. It closed by listing the families of counting polynomials where the same thing is known or conjectured, and the first on the list was the oldest theorem of its kind outside the permutations. Ole Heilmann and Elliott Lieb proved in 1972 that the polynomial counting a graph’s matchings by size has only real roots, for every graph.

A matching is a set of edges with no two sharing a vertex, the objects Hall’s theorem and Kasteleyn’s signs count when they cover every vertex. Write $m_k$ for the number of matchings with $k$ edges. The matching generating polynomial is $\sum_k m_k x^k$. There is no reason visible in the definition for its roots to be real, and the corresponding polynomial for independent sets — sets of vertices with no edge between them, counted by size — often has roots that are not. This essay tests both on every small graph, exactly, and finds the boundary between them where a 2007 theorem says it should be.

Testing real roots without finding them #

Finding roots numerically and checking that their imaginary parts are small is not a test. A root with imaginary part $10^{-9}$ and a pair of nearly equal real roots look the same to floating-point arithmetic. The figures here use Sturm’s theorem instead, which counts real roots exactly. From a polynomial $p$ and its derivative, build a sequence of polynomials by repeated division, each the negated remainder of the two before it. The number of sign changes in the sequence at $-\infty$, minus the number at $+\infty$, is exactly the number of distinct real roots of $p$.

With integer coefficients the whole computation can be kept in whole numbers, scaling by positive factors only so that no sign is disturbed, and the sequence ends at the greatest common divisor of $p$ and $p'$. A polynomial of degree $d$ has only real roots exactly when its number of distinct real roots equals its number of distinct roots, which is $d$ minus the degree of that common divisor. That handles repeated roots, which matter here: the spider’s matching polynomial $1 + 9x + 27x^2 + 32x^3 + 12x^4$ has a double root at $-\tfrac12$. The test is exact, and it was itself checked on polynomials whose roots are known, real and not.

Every small graph #

Run the test on every labelled graph with three to six vertices — 33,864 of them — and on 600 random graphs with eight, ten and twelve vertices.

All 35,664 matching polynomials are real-rooted. The independence polynomials are real-rooted on every graph with three vertices, on 60 of the 64 with four, on 86.8% with five and 86.3% with six, and on 70%, 60% and 49% of the random graphs with eight, ten and twelve. So the matching polynomial has a property the independence polynomial lacks, and lacks increasingly often as graphs grow.

On four vertices the four failures are the four labelled copies of the claw, $K_{1,3}$: one vertex joined to three others that are not joined to each other. Its independence polynomial is $1 + 4x + 3x^2 + x^3$, and a cubic of that shape has one real root and two complex ones.

The claw is the only obstruction #

That first failure is a hint. Split the graphs by whether they contain a claw as an induced subgraph — four vertices, one joined to the other three, the three not joined among themselves.

Every one of the 16,235 claw-free graphs has a real-rooted independence polynomial. Every failure is a graph with a claw. Maria Chudnovsky and Paul Seymour proved in 2007 that this is a theorem: the independence polynomial of every claw-free graph has only real roots.

A claw permits failure without forcing it. Half the five-vertex graphs with a claw pass, and the Petersen graph, which has claws at every vertex, has a real-rooted independence polynomial all the same. What the claw removes is the guarantee.

Heilmann and Lieb’s theorem is a special case. A matching of a graph $G$ is a set of edges no two of which share a vertex. Build the line graph of $G$, with one vertex for each edge of $G$ and two vertices joined when the edges meet. Then matchings of $G$ are exactly the independent sets of its line graph, and the matching polynomial of $G$ is the independence polynomial of the line graph. A line graph can never contain a claw. If one edge met three others, two of those three would meet it at the same endpoint and so meet each other. So every matching polynomial is the independence polynomial of a claw-free graph, and Chudnovsky and Seymour’s theorem contains Heilmann and Lieb’s.

Why the roots are real: interlacing #

Heilmann and Lieb’s own proof works one vertex at a time, and the mechanism can be seen in a single picture. It is cleanest for the signed version of the polynomial, $\mu(G, x) = \sum_k (-1)^k m_k x^{n - 2k}$, whose roots are those of the matching polynomial transformed and reflected, and which satisfies a simple recurrence when a vertex is deleted.

The recurrence is $\mu(G) = x\,\mu(G - v) - \sum_{u \sim v} \mu(G - v - u)$. Every matching either leaves $v$ uncovered or pairs it with one neighbour $u$. Suppose by induction that the roots of $\mu(G - v)$ interlace those of each $\mu(G - v - u)$. Then at each root of $\mu(G - v)$ the right-hand side has a sign fixed by the interlacing. The signs alternate from one root to the next, so $\mu(G)$ changes sign between consecutive roots of $\mu(G - v)$, and also beyond the outermost ones. That accounts for all its roots, and they are real and interlace those of $G - v$.

Starting from the empty graph, whose polynomial $x^n$ has all its roots at nought, the argument builds up any graph one vertex at a time, keeping every root real at every step. The Petersen graph’s roots are $\pm 2.631$, $\pm 2.093$, $\pm 1.619$, $\pm 1$ and $\pm 0.275$. With a vertex removed they are $\pm 2.472$, $\pm 1.906$, $\pm 1.345$, $\pm 0.670$ and $0$, one in each gap.

Chris Godsil found a second proof in 1981 that explains the reality differently. The matching polynomial of $G$ divides the characteristic polynomial of a certain tree built from $G$ — the tree of paths in $G$ from a fixed vertex — and a tree’s adjacency matrix is symmetric, so its eigenvalues are real. The matching polynomial’s roots are among them.

The path, where every root can be written down #

One family shows the whole theorem in closed form. On a path of $n$ vertices a matching is a choice of non-adjacent edges, and the number of matchings of each size is a binomial coefficient: $m_k = \binom{n - k}{k}$, since choosing $k$ non-touching edges among $n - 1$ in a row is choosing $k$ positions with gaps. Their total is a Fibonacci number, the same count a polynomial that counts found for tilings of a strip by squares and dominoes. A matching of the path is such a tiling, with an edge for each domino.

The signed polynomial $\mu(P_n, x)$ satisfies the recurrence $\mu(P_n) = x\,\mu(P_{n-1}) - \mu(P_{n-2})$, the interlacing recurrence with a single neighbour. That is the recurrence of the Chebyshev polynomials of the second kind, so $\mu(P_n, x) = U_n(x/2)$, and its roots are

$$2\cos\frac{\pi j}{n + 1}, \qquad j = 1, \ldots, n,$$

real, distinct, and inside $(-2, 2)$, which is the bound $2\sqrt{\Delta - 1}$ with $\Delta = 2$. The interlacing is visible too: the roots for $n$ and $n - 1$ are the cosines of the multiples of $\pi/(n + 1)$ and $\pi/n$, which alternate around the circle. The same polynomials give the eigenvalues of a vibrating string of $n$ beads, which is no accident. The path is its own tree of paths, so Godsil’s theorem says its matching polynomial is its characteristic polynomial, and those eigenvalues are close relatives of the Chebyshev nodes that the best nodes for interpolation are measured against.

For the coin picture the path gives explicit coins. The roots of the generating polynomial $\sum m_k x^k$ are $-1/(4\cos^2(\pi j/(n + 1)))$ for the $j$ up to $n/2$, so the coin chances are $4\cos^2/(1 + 4\cos^2)$. A random tiling of a strip by squares and dominoes has a number of dominoes distributed exactly as heads among these coins, and that is why the count of dominoes in a random Fibonacci tiling is bell-shaped with an explicit variance.

A bound that built expanders #

The same proof gives a bound. Heilmann and Lieb showed that every root of $\mu(G, x)$ lies within $2\sqrt{\Delta - 1}$ of nought, where $\Delta$ is the largest number of neighbours of any vertex. For the Petersen graph, with three neighbours everywhere, that is $2\sqrt2 \approx 2.828$, and the largest root, $2.631$, is inside it.

The number $2\sqrt{d - 1}$ is not arbitrary. It is the spectral radius of the infinite tree in which every vertex has $d$ neighbours — the rate at which a walk on that tree comes home — and it is the smallest second eigenvalue a large $d$-regular graph can have. Graphs that achieve it are Ramanujan graphs, the best possible expanders, and for decades they were known to exist only for special degrees, by number-theoretic constructions.

In 2013 Adam Marcus, Daniel Spielman and Nikhil Srivastava proved that bipartite Ramanujan graphs exist for every degree. The proof averaged the characteristic polynomials of all signed versions of a graph, and the average turns out to be exactly the matching polynomial. Heilmann and Lieb’s bound then says its roots are small. A new interlacing argument, generalising the one in the figure, shows that some individual signing has roots no larger than the average’s. A theorem from the statistical physics of 1972 was the key estimate in a 2013 theorem about networks, and the same interlacing idea later settled the Kadison–Singer problem.

Real roots make coins #

The physics was the original motivation. Heilmann and Lieb were studying the monomer–dimer model, in which molecules occupy pairs of adjacent sites of a lattice: a matching. Real roots, all negative, mean the model’s partition function never vanishes for positive weights, and so the model has no phase transition. For a combinatorialist the same fact has the consequence coins hidden in the roots drew for descents.

A polynomial with positive coefficients and only real roots factors as a constant times $\prod (x - r_i)$ with every $r_i$ negative, and dividing by its value at $x = 1$ turns each factor into $(1 - p_i) + p_i x$ with $p_i = 1/(1 - r_i)$, a coin. So the size of a matching chosen uniformly at random is distributed exactly as the number of heads in independent tosses of these coins. The twelve-vertex graph’s coins have chances between $0.108$ and $0.876$, and the distribution they give matches the matching counts to nine decimal places.

The consequences follow at once. The matching counts of every graph are log-concave, $m_k^2 \ge m_{k-1} m_{k+1}$, and in fact satisfy Newton’s stronger inequalities. They are unimodal, rising to a single peak and falling. And on large graphs they are close to a bell curve, since a sum of many independent coins is. None of this can be seen from the definition of a matching, and all of it follows from one fact about roots.

Monomers allowed, and monomers forbidden #

The physical meaning of the theorem is sharpest by contrast with the case it excludes. In the monomer–dimer model a weight $x$ is attached to each dimer, and the partition function is the matching polynomial evaluated at $x$. Every matching counts, with any number of uncovered sites, the monomers. Heilmann and Lieb’s theorem says this polynomial has no zero on the positive real axis, nor near it, for any lattice of any size. By the argument C. N. Yang and T. D. Lee gave for magnets in 1952, zeros that stay away from the physical axis as the lattice grows mean the free energy is analytic there, and so there is no phase transition at any positive dimer weight.

Forbid the monomers and the picture changes completely. Matchings that cover every site — perfect matchings, or domino tilings on a square lattice — are what Kasteleyn’s signs count by a determinant. On a region shaped like the Aztec diamond they show a sharp boundary between frozen corners and a disordered middle, the arctic circle. That is phase coexistence, visible in a single random tiling. It is the limit of infinite dimer weight, the one point the theorem cannot reach, because the zeros of the matching polynomial accumulate towards it as the lattice grows.

So the matching polynomial’s real roots draw a precise line. With monomers allowed at any positive density the model is in one phase. At full packing, where monomers vanish, it can freeze. The line between the two is the same one that separates the matching polynomial, whose roots are real and negative, from its top coefficient alone, the number of perfect matchings, which carries no such guarantee.

What the census cannot settle #

The census is exact for the graphs it contains, and it contains every labelled graph up to six vertices, but beyond that it samples. Its confirmation of Heilmann and Lieb and of Chudnovsky and Seymour is a check, not a proof; the proofs are the interlacing argument for one and a much longer structural argument for the other.

The census also says nothing about where non-real roots sit when they occur. The spider’s independence roots are far from the axis, but whether non-real roots of independence polynomials are typically near the axis or far from it, and how many there are, are separate questions. The census records only whether the count of real roots is complete.

Still open: which graph polynomials keep their roots real #

Real-rootedness has been proved for matchings, for independent sets of claw-free graphs, and for several other polynomials attached to graphs, each by its own argument. A unifying framework exists — stable polynomials in several variables, developed by Julius Borcea and Petter Brändén, which turn interlacing into a property preserved by a known list of operations. But for many natural graph polynomials, which ones keep their roots real is still decided case by case.

One much-studied case shows how fragile the property is. The polynomial counting a graph’s forests by size was conjectured by John Mason in 1972 to have log-concave coefficients, and the conjecture was settled only after 2018, as a consequence of work by Karim Adiprasito, June Huh and Eric Katz and the methods that followed it. Its roots are not all real in general. The coefficients behave as if they came from coins although the roots say they cannot, which is the situation the next family, the chromatic polynomials, is in on almost every graph. Which counting sequences are log-concave without being real-rooted, and why, is the question that algebraic geometry rather than interlacing has begun to answer.

Two counts, one theorem #

The matching polynomial and the independence polynomial count two different things, and only the first keeps its roots real on every graph. Line graphs explain the difference. A graph’s matchings are the independent sets of a graph without claws, and Chudnovsky and Seymour proved that every claw-free graph keeps its independence roots real. Heilmann and Lieb’s interlacing, one vertex at a time, is the special case that came first, and it carries a bound, $2\sqrt{\Delta - 1}$, that became the key to the existence of Ramanujan graphs. Behind all of it are coins: a random matching’s size is a sum of independent tosses whose chances are read from the roots. That is why matching counts are bell-shaped and log-concave on every graph anyone will ever draw.