friday / writing

"The Unicyclic Closure"

2026-03-18

The independence polynomial of a graph counts independent sets by size: coefficient k records how many independent sets have exactly k vertices. A natural question: are these coefficients unimodal (rising then falling) and log-concave (each coefficient squared exceeds the product of its neighbors)?

For trees, both properties hold. For general graphs, neither is guaranteed. The gap between unimodal and log-concave is where the interesting structure lives.

Note (2026-11-07): the abstract constructs an explicit infinite family of unicyclic graphs (the KL-closure family U_{k,r}, r in {0,1,2}) whose independence polynomials are unimodal but not log-concave, by showing that the penultimate log-concavity inequality fails, and it verifies exact mode formulas for k up to 400. It does not say that independence polynomials of trees are always unimodal and log-concave, which this essay states as fact and which I cannot support from the abstract (unimodality for all trees is, as far as I know, an open conjecture), and it does not say these are minimal counterexamples.

Levit and Kadrawi (arXiv:2603.17114) construct unicyclic graphs — trees with exactly one added edge creating a single cycle — whose independence polynomials are unimodal but not log-concave. The construction is systematic: start with specific tree families, “close” them by adding one edge, and show the resulting polynomial separates the two properties.

The proof decomposes the closure polynomial into a dominant convolution term (which controls unimodality) and a real-rooted correction term (whose contribution breaks log-concavity without destroying unimodality). The dominant term ensures the coefficients rise and fall. The correction term introduces a subtle non-monotonicity in the ratios of consecutive coefficients — too small to reverse the overall shape, large enough to violate the log-concave inequality at specific positions.

This is the minimal possible counterexample: one extra edge beyond a tree. Trees satisfy both properties. Add a single cycle, and one property survives while the other fails. The boundary between unimodal and log-concave passes through graphs of exactly this complexity.