Log-concave with nothing to make it so

The roots every matching polynomial keeps real showed what real roots buy. A counting polynomial whose roots are all real and negative is a product of coins in disguise, and its coefficients must then be log-concave — each squared is at least the product of its neighbours — and satisfy Newton’s stronger inequalities besides. Coins hidden in the roots found the same for descents. Both essays suggest that log-concavity is a symptom, and real roots the cause.

The chromatic polynomial says otherwise. Counting the colourings built it: $P(G, x)$ is the number of ways to colour the vertices of a graph $G$ with $x$ colours so that no edge joins two vertices of the same colour, and it is a polynomial in $x$ with coefficients alternating in sign. In 1968 Ronald Read conjectured that the sizes of those coefficients always rise to a single peak and then fall. In 1974 Stuart Hoggar conjectured the stronger statement that they are log-concave. Neither follows from real roots, because chromatic polynomials very often do not have them. The conjectures stood for more than forty years, and June Huh proved them in 2012 by importing a theorem from algebraic geometry.

A wheel with two complex roots #

The wheel’s chromatic polynomial is

$$P(W_5, x) = x^6 - 10x^5 + 40x^4 - 80x^3 + 79x^2 - 30x.$$

It can be written down by hand. Colour the hub in $x$ ways; the ring must then avoid that colour, and a ring of five vertices can be properly coloured with $y$ colours in $(y-1)^5 - (y-1)$ ways. With $y = x - 1$ that gives $x\bigl[(x - 2)^5 - (x - 2)\bigr]$. Its roots are $0$, then $x - 2 = 0$, $x - 2 = \pm 1$, and $x - 2 = \pm i$, so two of them are complex. Nothing about this polynomial is a product of coins.

But the sizes of its coefficients, $30, 79, 80, 40, 10, 1$, are log-concave. $79^2 = 6{,}241$ exceeds $30 \times 80 = 2{,}400$; $80^2$ exceeds $79 \times 40$; $40^2$ exceeds $80 \times 10$; $10^2$ exceeds $40 \times 1$. The tightest of the four ratios is exactly $2$, at the last one. The sequence behaves as if it came from coins although its roots say it cannot.

What the coefficients count #

The coefficients are not only numbers attached to a polynomial; each one counts something. Hassler Whitney showed in 1932 how. Order the edges of the graph once and for all. Every cycle has a largest edge, and removing it leaves a path called a broken circuit. Then the size of the coefficient of $x^{n-k}$ is exactly the number of sets of $k$ edges that contain no broken circuit. For the wheel, $79$ is the number of four-edge sets avoiding every broken circuit, and $30$, the coefficient of $x$, is the number of five-edge sets — spanning trees with an extra condition.

That turns Read’s conjecture into a statement about families of edge sets. It says the number of broken-circuit-free sets of each size rises and falls with no dip, and Hoggar’s says the counts are log-concave. Families of sets closed under taking subsets — which these are — often have counts that rise and fall, but not always, and nothing general forces it. The edge sets here are the independent sets of a structure called the graph’s matroid, the same structure that the cycles and the cuts studied through ranks over the two-element field. The conjecture was eventually seen to be about that matroid rather than about colours at all.

The alternating signs come from the same count. Deletion and contraction, the recursion of counting the colourings, subtracts the contracted graph’s polynomial from the deleted graph’s. The broken-circuit description is what that recursion produces when it is unwound edge by edge in the fixed order, with each sign recording how many edges a set uses.

Every small graph, three ways #

To see how typical the wheel is, score every labelled graph with an edge on three to six vertices — 33,860 graphs — and 200 random graphs each on eight, nine and ten vertices, on three properties of the chromatic polynomial. All three are checked exactly: whether every root is real, by the Sturm sequences of the matching essay; whether the coefficients satisfy Newton’s inequalities, which every real-rooted polynomial must; and whether their sizes are log-concave.

The first two properties collapse. On three vertices every chromatic polynomial is real-rooted; on four, 60 of 63; on five, 80%; on six, 55%. Among the random graphs only 34 of 200 on eight vertices have only real roots, 7 of 200 on nine, and 3 of 200 on ten. Newton’s inequalities fail almost as often, since a polynomial that satisfies them is close to having real roots. On ten vertices 173 of the 200 graphs fail them.

The third property never fails. Every one of the 34,460 coefficient sequences is log-concave. As the graphs grow, the reason that usually explains log-concavity disappears almost entirely, and log-concavity itself does not move.

The cycle that passes one test and fails the other #

The gap between Newton’s inequalities and log-concavity is a gap in strength, and one small graph shows it plainly. Newton’s inequalities ask each ratio $c_k^2/(c_{k-1}c_{k+1})$ to exceed not one but a number set by binomial coefficients, $\binom{d}{k}^2/\bigl(\binom{d}{k-1}\binom{d}{k+1}\bigr)$. That is the ratio a polynomial with all its roots at a single point would have, and every real-rooted polynomial of degree $d$ must clear it.

The six-cycle’s chromatic polynomial is $(x - 1)^6 + (x - 1)$, whose roots besides $x = 1$ are $1$ plus the five fifth roots of $-1$, four of them complex. Its coefficient ratios are $2.25$, $1.78$, $1.88$ and $2.40$; Newton demands $2.5$, $2$, $2$ and $2.5$. Every ratio falls short of what real roots would require, and every ratio exceeds one. The cycle sits in the band between the two inequalities, where log-concave sequences without real roots live, and almost every chromatic polynomial of any size sits there too.

The graphs that do have real roots #

The census shows real roots fading, but some families keep them at every size, and the reason is instructive. A graph is chordal when every cycle of four or more vertices has a chord, an edge joining two of its non-consecutive vertices. Trees are chordal, complete graphs are chordal, and so is any graph built by repeatedly adding a vertex joined to a set of vertices that are all joined to each other.

For a chordal graph the colouring count factors completely. Add the vertices in that order — a perfect elimination ordering — and each new vertex sees a clique of $k_i$ already-coloured neighbours, all of different colours, so it has exactly $x - k_i$ choices whatever came before. The chromatic polynomial is therefore $\prod_i (x - k_i)$, with every root a whole number: $0$, $1$, $2$ and so on, as many times as cliques of each size appear in the ordering. The census’s real-rooted graphs are mostly of this kind, and the wheel misses by one chord: its five-sided ring has no chord, and that ring is what produces the roots $2 \pm i$.

So real roots, in the chromatic world, are a sign that the graph can be coloured greedily in an order where every choice is independent of the others, the same order-dependence that the order decides the colours explored for greedy colouring. A graph with a long chordless cycle cannot be coloured that way. Its count does not factor, its roots leave the axis, and its coefficients are log-concave for a reason that has nothing to do with factoring.

Seventy-two shapes, one peak each #

Read’s original conjecture was the weakest of the three: that the coefficient sizes rise to a single peak and fall, with no dips and no plateaus between. Log-concavity implies it, but it can also be seen directly.

Among the 32,767 labelled graphs with an edge on six vertices there are only 72 different chromatic polynomials. Many graphs share one; all the trees on six vertices, for instance, share $x(x - 1)^5$. Drawn together, the 72 coefficient sequences form a sheaf of single-peaked curves. The peaks sit at $x^2$, $x^3$ or $x^4$ according to how dense the graph is: sparse graphs peak low, near-complete graphs high. Each curve starts and ends small, and none ever turns back upward.

How close any graph comes #

Log-concavity holds everywhere in the census, but it could hold with a shrinking margin and fail somewhere beyond it. The tightest ratio over all graphs of each size measures that margin.

The margin falls with size — 4, 2.67, 2, 1.78 — and keeps falling among the random graphs, to $1.45$ at ten vertices. Extrapolated naively it would cross one somewhere, and a census could never tell whether it does. That is the reason a theorem was needed. The falling margin is consistent with log-concavity holding at every size with ratios tending to one, and it is equally consistent with a counterexample at fifty vertices. The binomial coefficients behave the same way: they are log-concave with ratios tending to one in the middle, and they never fail.

Huh’s theorem, and where it came from #

June Huh, then a graduate student, proved Read’s and Hoggar’s conjectures in 2012. The proof does not find hidden coins or real roots. It identifies the chromatic coefficients with a different kind of quantity. The coefficients turn out to be mixed multiplicities: the numbers that measure how two subvarieties of a projective space intersect, attached to a hypersurface built from the graph. For such numbers the Khovanskii–Teissier inequalities, a consequence of the Hodge index theorem of algebraic geometry, give log-concavity directly. The inequalities come from geometry, and the graph enters only through which variety is being measured.

The argument extended. Huh and Eric Katz carried it to matroids representable over a field. Then in 2018 Karim Adiprasito, Huh and Katz built a combinatorial version of Hodge theory for every matroid, with no variety at all, and proved log-concavity for the characteristic polynomials of all matroids. That settled the Rota–Heron–Welsh conjecture, of which Read’s and Hoggar’s are the graphic case. The methods have since settled several further log-concavity conjectures. In each case the inequality comes from an algebraic structure that looks like geometry, not from roots.

So the two families here are log-concave for different reasons, and the difference is not a matter of proof technique: one of them has roots that make the inequality automatic, and the other does not. The matching coefficients are log-concave because they are coins. The chromatic coefficients are log-concave because they are intersection numbers. The census cannot see the difference, since it sees only the inequality, and that is why Read’s conjecture was so hard: every computation pointed at a truth whose cause was invisible from where the computations were made.

Why the conjecture was believed for forty years #

Read stated the unimodality conjecture in his 1968 survey of chromatic polynomials, on the evidence of exactly this kind of table — every graph he could compute had coefficients that rose and fell. Gian-Carlo Rota made the matroid version in 1971, Heron and Welsh the log-concave version for matroids in the following years, and the conjectures were folded into the general belief that counting sequences that come from geometry should be log-concave. That belief had support from the Alexandrov–Fenchel inequalities of convex geometry, which make the mixed volumes of convex bodies log-concave, and from Richard Stanley’s use of them to prove log-concavity for several sequences in combinatorics.

What was missing was a geometric object whose mixed volumes or intersection numbers were the chromatic coefficients. For graphs that could be drawn in the plane, partial results came from the four-colour literature’s study of chromatic roots. For general graphs nothing reached the coefficients. Huh’s contribution was to find the object — a hypersurface whose singularities encode the graph — and then to see that a classical inequality about it was the conjecture in disguise.

Where chromatic roots fall #

Since the roots carry no guarantee of reality, it is natural to ask where they actually are.

The complex roots spread over a region several units wide, in conjugate pairs, mostly with real parts between 1 and 4. The real roots obey constraints that are theorems. None is negative, since the coefficients alternate in sign. None lies strictly between 0 and 1, by a classical argument. And Bill Jackson proved in 1993 that none lies in the interval from 1 to $32/27$, a strange constant that is sharp: Carsten Thomassen showed that real chromatic roots come arbitrarily close to every number above $32/27$. Every real root in the cloud respects all three gaps.

These are statements about where roots cannot be, and none implies log-concavity. The only constraint on a chromatic polynomial’s coefficients that implies log-concavity directly is real-rootedness, and the cloud shows how rarely that holds. Huh’s theorem had to find a reason somewhere else.

What the census does and does not show #

The census establishes that log-concavity holds on 34,460 chromatic polynomials, exactly. It shows the margin shrinking. It shows real roots and Newton’s inequalities failing at rising rates. It cannot establish the theorem, and before 2012 it could not have, however far it ran. The coefficient sequences of large graphs are far too numerous to check, and nothing in the falling margin rules out a failure.

Nor does the census explain anything about why the inequality holds. The figures show a property shared by a class of sequences and the absence of the usual cause. The actual cause is a structure — a Hodge-theoretic intersection pairing — that has no picture in the space where the coefficients live.

Still open: stronger inequalities, and the ones beyond graphs #

Log-concavity of chromatic coefficients is now a theorem, but several stronger statements are not. One asks for the chromatic coefficients to satisfy a version of Newton’s inequalities with the binomial normalisation replaced by something weaker but still stronger than plain log-concavity. Inequalities of that kind, ultra-log-concavity among them, have been proved for some related sequences — the counts of independent sets of a matroid, by Brändén and Huh and independently by Anari, Liu, Oveis Gharan and Vinzant in 2020. Which sharper inequalities hold for chromatic coefficients in general is less clear, and the six-cycle shows how far below Newton they can sit.

Beyond graphs and matroids, many sequences in combinatorics are conjectured log-concave with no real roots in sight. One is the number of linear extensions of a partial order by the position of a given element, Stanley’s inequality, which has an algebraic-geometric proof of the same family. Others have no proof at all. The pattern since 2012 is that log-concavity without real roots is often a shadow of a hidden geometry, but there is no general rule that says which sequences have one.

The cause behind the symptom #

Real roots are the simplest reason for log-concave coefficients, and for matchings and descents they are the right one. For colourings they are almost never present, and by ten vertices barely one graph in a hundred has them, while the coefficients stay log-concave on every graph. The wheel, with two complex roots, and the six-cycle, failing Newton at every step, are the small, typical cases.

What holds the inequality up is not visible in the roots or in the counts. It is the geometry of mixed multiplicities, where log-concavity is a theorem about how things intersect. Read conjectured the shape in 1968, from tables of coefficients like those in these figures, and was right for a reason that took forty-four years to find. The same tables now carry a different lesson. A pattern that holds on every case anyone can compute, and that the obvious mechanism cannot explain, is not thereby an accident. It may instead be the visible edge of a structure that has not yet been named, and in this case the structure turned out to be a piece of geometry that nobody had thought to attach to a graph.