← All papers
First page of Unimodality of Forest Independence Polynomials

Unimodality of Forest Independence Polynomials

Wei Li, Kevin Vallier, Tong Zhang

math.CO Oct 6, 2026 · v1
The full unimodality theorem for forest independence polynomials (Erdős Problem 993) is formally proved in Lean 4 with Mathlib, using kernel and compiled evaluations of interval-arithmetic certificates.
For a finite forest $F$ let $i_k(F)$ be the number of independent sets of $F$ with $k$ vertices. Zhang and Li proved that the sequence $i_0(F),i_1(F),\dots,i_{α(F)}(F)$ is unimodal for every finite forest $F$, which answers Erdős Problem 993. We give a second proof. It starts from their decomposition relative to a fixed independent set and from the bounds of Zhang and Li and of Fang, Lu, Nevo, Yao and Zheng that confine a valley of the sequence to an explicit window of ranks. For a forest with at least $25$ vertices, one moment argument excludes a valley at every rank of the window: at the activity where the hard-core mean equals the rank, the size of a random independent set is a mixture of binomial laws over an independent set of maximum weight, a valley is a moment inequality for this mixture, and it is excluded by duality given three bounds that hold for every forest, on the variance of the number of free vertices and on its Laplace transforms, and on the variance ratio. The variance bound is proved by hand up to finitely many interval checks and the other two bounds are verified by computer on finite interval-arithmetic coverings; on the resulting parameter domain a valley is excluded by exact tests on finitely many rational boxes while the mean number of free vertices is below an explicit starting mean between $19$ and $50$, and above it by one inequality, with explicit constants, for the fibers of a weighted valley kernel, proved by hand up to a finite list of explicit checks and averaged over the mixture. Forests with at most $24$ vertices are treated by exact counting, by hand except for exact rational evaluations of two explicit formulas at $43$ parameter triples. No forest is enumerated. A formal proof of the theorem in Lean 4 accompanies the paper.

Zhang and Li proved that the independence sequence of every finite forest is unimodal, answering Erdős Problem 993. The paper gives a second, independent proof together with a formal verification.

Valleys are confined to an explicit window of ranks using known bounds. For forests with at least 25 vertices, a moment argument applies: at a suitable hard-core activity, the size of a random independent set is written as a mixture of binomials, and duality excludes valleys given variance, Laplace-transform and variance-ratio bounds. These bounds are verified by interval-arithmetic coverings and exact rational box tests. Forests with at most 24 vertices are handled by exact counting, and the whole proof is formalized in Lean 4 with Mathlib, with certificates checked by kernel and compiled evaluation.

Every finite forest has a unimodal independence sequence, proved formally as the premise-free Lean theorem erdos993_v22_final (Mathlib v4.28.0). The trusted base adds the compiler, and for some checkers the C toolchain, to the kernel and the standard axioms.