The forests a graph can hold

Log-concave with nothing to make it so followed the coefficients of a graph’s chromatic polynomial and found them rising to one peak and falling, each squared at least the product of its neighbours, on every graph tested — although the polynomial’s roots are usually not all real, which is the easy reason such inequalities hold. June Huh proved it for every graph in 2012, and that essay ended by pointing at sharper inequalities of the same kind, conjectured for a different count and proved only in 2018.

The count is the simplest one a graph has after its edges. A forest is a set of edges containing no cycle, and $f_k$ is the number of forests with $k$ edges. A graph with $m$ edges and $n$ points has $f_0 = 1$, $f_1 = m$, and at the top, if it is connected, $f_{n-1}$ is the number of its spanning trees. In between, the counts rise and fall, and John Mason conjectured in 1972 that they do so in a particularly orderly way.

Three inequalities, in order of strength #

The complete graph on four points has six edges. It has one forest with no edges, 6 with one, 15 with two — any two edges, since two edges never make a cycle — and 16 with three, which are its spanning trees, as Cayley’s formula says. Mason’s three conjectures are three demands on such a sequence.

The weakest is log-concavity: $f_k^2 \ge f_{k-1} f_{k+1}$ at every $k$. It says the sequence has no dips and no plateaus followed by rises — that the ratio $f_k/f_{k-1}$ only falls. The middle one asks for a margin, $f_k^2 \ge (1 + \tfrac1k) f_{k-1} f_{k+1}$. The strongest asks for the margin that the binomial coefficients have:

$$f_k^2 \ \ge\ \Big(1 + \frac1k\Big)\Big(1 + \frac{1}{m - k}\Big)\, f_{k-1}\, f_{k+1}.$$

Written another way, $f_k / \binom{m}{k}$ is itself log-concave — the property called ultra-log-concavity. For the complete graph on four points the ratio at $k = 2$ is $15^2/(6 \times 16) = 2.34$ against a threshold of $(1 + \tfrac12)(1 + \tfrac14) = 1.875$, and at $k = 1$ it is $6^2/(1 \times 15) = 2.4$, exactly the threshold.

That equality at $k = 1$ is not special to this graph. In a graph without repeated edges any two edges form a forest, so $f_0 = 1$, $f_1 = m$ and $f_2 = \binom{m}{2}$ are binomial coefficients, and the strongest inequality holds with equality at $k = 1$ for every graph. The interesting cases start at $k = 2$, and the census below looks only there.

Why binomial coefficients are the yardstick #

The threshold in the strongest inequality looks arbitrary until it is read as a comparison. Take $m$ edges with no relations among them at all — every subset independent — and the counts are $\binom{m}{k}$. For those, $\binom{m}{k}^2 / \big(\binom{m}{k-1}\binom{m}{k+1}\big)$ works out to exactly $(1 + \tfrac1k)(1 + \tfrac{1}{m-k})$. So the conjecture says that adding constraints — declaring some sets of edges dependent because they contain cycles — can only make the counts more log-concave than the unconstrained ones. Every structure of this kind is at least as peaked as the structure with no structure.

There is a probabilistic way to say the same thing. Choose a forest uniformly at random from all the forests of a graph and let $K$ be its number of edges. Ultra-log-concavity of $f_k$ is equivalent to the distribution of $K$ being, in a precise sense, more concentrated than a binomial distribution with the same mean — at least as concentrated as the number of heads in independent coin tosses. That is the natural guess for a random object assembled from many weakly interacting choices, and it is the same instinct as the negative correlation of edges in a random spanning tree: in a structure where including one element makes others less available, the totals cannot spread more than independence allows.

The weakest inequality has an older and more elementary reading. A positive sequence is log-concave exactly when the ratios $f_{k+1}/f_k$ never increase, so a log-concave count has a single peak and no internal dips, and its successive ratios fall steadily. For forests those ratios are, roughly, the average number of ways to extend a forest of size $k$ by one edge, divided by $k + 1$; that they fall is the statement that as a forest grows the edges still available to it become relatively scarcer, which is easy to believe and, without the methods of 2018, impossible to prove in general.

Every small graph #

The computation behind the figures lists every graph on two to six points up to relabelling — 202 of them with at least one edge, 155 on six points alone — by trying every set of edges and keeping one representative of each shape. For each graph it then tries every set of edges again, at most $2^{15} = 32{,}768$ of them, keeps those with no cycle, and counts them by size. Nothing is estimated.

Every one of the 461 points lies on or above the line. The weakest inequality is satisfied with room to spare — the smallest ratio of all is 1.67, far above the 1 that log-concavity asks — and the middle one with a margin of at least 12%. The strongest is where the action is: 73 of the points sit exactly on the threshold, and many of the rest lie close above it. On small graphs, as on the chromatic polynomials, nothing comes near failing; what the census shows is that the strongest conjecture is close to being an exact description rather than a loose bound.

Where the bound is exact #

Equality has a clean explanation. The threshold is exactly the ratio that binomial coefficients achieve, so the inequality is an equality at $k$ precisely when $f_{k-1}$, $f_k$ and $f_{k+1}$ are all binomial — when every set of $k + 1$ edges is a forest, so no cycle has $k + 1$ or fewer edges. At $k = 2$ that means no triangle, and the computation confirms it on every graph: the bound is exact at $k = 2$ exactly when the graph is triangle-free. At $k = 3$ it needs no cycle of length three or four, and so on. Trees satisfy it at every $k$, since none of their edge sets contains a cycle.

So the inequality has a reading in words: cycles can only make the forest counts more sharply peaked than binomial ones. A graph with no short cycles is binomial up to the length of its shortest cycle, and each cycle removes edge sets from the top of the count faster than from the middle, which steepens the peak. That reading is easy to believe and is not a proof, because cycles overlap and interact, and the inequality has to hold at every $k$ at once.

How much room the forests leave #

The 388 ratios that are not exactly on the threshold sit between 1.8% and about 150% above it, with half of them within 16%. Small graphs rarely have a lot of room. That matters for proofs: a crude argument that loses a constant factor somewhere cannot establish an inequality that is nearly tight on many graphs, and the classical tools — injections between forests of neighbouring sizes, or exchange arguments that swap edges — tend to lose exactly such factors.

On larger graphs the bound gets closer still. Twenty-four random graphs on nine points, with up to $2^{18}$ edge sets counted each, all satisfy the strongest inequality, and all with very little to spare: their smallest margins run from 0.6% to 3.1% above the threshold. A typical graph is nearly binomial in its forest counts, in the sense the inequality measures, and the inequality is a statement about very small departures from binomial behaviour.

The easy route is closed #

The easiest way to prove inequalities like these is through roots. If the polynomial $\sum f_k x^k$, with positive coefficients, has only real roots, then it is a product of linear factors and its coefficients satisfy Newton’s inequalities, which are exactly ultra-log-concavity — the mechanism that hides coins in the roots of the descent polynomial and that keeps every matching polynomial’s roots real. For forest polynomials it is almost never available. Of the 154 graphs on six points with at least two edges, only 2 have forest polynomials with only real roots; on five points, 2 of 32. The roots of the rest scatter into the complex plane in the figure’s cloud, and the inequalities hold anyway.

This is the same situation as the chromatic polynomials, and for the same reason it took a new idea. The real-rootedness that would make the inequalities automatic is a property of a single polynomial in one variable. What turned out to hold for every graph is a property of a polynomial in many variables — one for each edge — called Lorentzian, a weakening of real-rootedness that survives where real-rootedness fails.

The top of the sequence is a determinant #

The last count in the sequence is special. For a connected graph on $n$ points, $f_{n-1}$ counts spanning trees, and that number has a formula no other $f_k$ has: Kirchhoff’s theorem, a determinant that counts trees, gives it as any cofactor of the graph’s Laplacian. The complete graph on four points has 16 spanning trees by that determinant and by Cayley’s formula. The intermediate counts have no such formula; they are coefficients of the Tutte polynomial evaluated along a line, and computing them for a general graph is as hard as counting colourings. So the inequalities relate one easy number, the spanning trees, to a sequence of hard ones, and their proof had to find structure in the hard ones rather than formulas.

That is also why the problem looked so different from the chromatic one at first and turned out so similar in the end. The chromatic polynomial and the forest counts are both specialisations of the same Tutte polynomial, which records, for every set of edges, how many components and how many independent cycles it has. Huh’s proof for the chromatic coefficients and the 2018 proofs for forests both work by finding, inside that two-variable polynomial, an object with the positivity properties of algebraic geometry, and reading the inequalities off it.

The proof, and what it is about #

Mason’s conjectures are not really about graphs. The forests of a graph are the independent sets of its cycle matroid, the structure that records which sets of edges contain a cycle and nothing else, and the conjectures were stated for every matroid: for any family of independent sets satisfying the exchange property that makes greedy algorithms work, the numbers of independent sets of each size should satisfy the three inequalities.

The weakest was proved by Karim Adiprasito, June Huh and Eric Katz in 2018, by building, for every matroid, an algebra that behaves like the cohomology of a smooth projective variety — even when no variety exists — and proving for it the Hodge–Riemann relations of algebraic geometry. Log-concavity falls out of those relations as it would for an actual variety. The strongest was proved later the same year, by two groups independently and with a much shorter argument: Nima Anari, Kuikui Liu, Shayan Oveis Gharan and Cynthia Vinzant, and Petter Brändén and June Huh. Both showed that the generating polynomial of the independent sets, homogenised and written with one variable per element, is Lorentzian — its Hessian has exactly one positive eigenvalue at every point of the positive orthant, in the right sense — and that this property passes to the coefficient sequence as ultra-log-concavity.

The Lorentzian property also had consequences that nobody had connected to Mason’s question. It gives a fast randomised algorithm for counting the bases of any matroid approximately, settling a problem of Mihail and Vazirani from 1989, and it implies that the uniformly random base of a matroid has negative dependence properties of the kind edges that crowd each other out describes for spanning trees. A conjecture about the shape of a sequence of counts turned out to be the same fact as an efficient sampling algorithm.

Why a count becomes a polynomial #

Every tool in this story works on a polynomial rather than on a sequence, and the step from one to the other is the oldest move in enumeration. Writing the forest counts as $F(x) = \sum f_k x^k$ is packaging a count as a polynomial, and once packaged the count can be multiplied, differentiated and evaluated: $F(1)$ is the total number of forests, $F'(1)/F(1)$ the average size of a random one, and the shape of the coefficients is governed by where the roots lie. The descent counts and matching counts of the earlier essays were tamed that way, because their roots are real.

The forests needed a polynomial with more variables. Give each edge $e$ its own variable $x_e$ and let the polynomial be the sum, over forests, of the product of their edges’ variables; setting every $x_e = x$ recovers $F$. In many variables there is room for structure that collapses in one: the Lorentzian property is a statement about the many-variable polynomial’s second derivatives, and it is preserved by the operations — setting variables equal, differentiating — that lead back to the one-variable sequence. It is the strategy of adding a variable to track more than the count, pushed to its limit — a variable for every edge, kept until the last moment — and the information the final count throws away is exactly what makes the inequality provable.

What the computations show and assume #

Every forest count here is exact, obtained by trying every set of edges, and every graph on up to six points is included, each once. Within that range the figures prove the inequalities by exhaustion — a finite statement — and illustrate the theorem beyond it; nothing in them would be a proof for graphs on seven points or more. The random graphs on nine points are a sample, chosen with edge densities between about a third and a half and between 10 and 18 edges; they say what typical graphs of that size do and nothing about atypical ones.

The roots are found numerically, by a simultaneous iteration that converges for polynomials of these small degrees, and a root counts as real when its imaginary part is below a millionth. A polynomial with a pair of nearly real complex roots could be miscounted; for degree five that would need coefficients far more delicately balanced than forest counts are.

Still open: beyond matroids #

Which other sequences in combinatorics are ultra-log-concave, and is there a single reason? The Lorentzian property explains Mason’s conjectures for every matroid and has since explained several other inequalities, but it does not reach every count one would like it to. For the chromatic polynomial — the subject of the essay before this one — whether anything as strong as Mason’s third inequality holds is open. For the independent sets of a graph’s points, rather than of its cycle matroid, even unimodality fails for some graphs; it was conjectured for trees in 1987 and is still open there, while the stronger log-concavity, long believed for trees too, was found to fail in 2023. The general picture, that the inequalities which hold have a geometric reason and the ones that fail lack one, is suggestive rather than precise, and which counts of combinatorial objects carry the Lorentzian structure is being worked out family by family.

A peak sharper than the binomial #

The forests of a graph, counted by size, rise and fall in a peak at least as sharp as the binomial coefficients’, and exactly as sharp only where the graph has no short cycles. On every graph with up to six points the strongest of Mason’s inequalities holds, with equality at $k = 2$ precisely for the triangle-free graphs, and on random graphs with nine points it holds with a margin of one to three per cent — nearly tight, with almost no forest polynomial having real roots to make it easy. Its proof for every matroid in 2018 came from a many-variable relative of real-rootedness, and the same property turned out to count bases quickly.