Unimodality of Forest Independence Polynomials
Abstract
For a finite forest F let ik(F) be the number of independent sets of F with k vertices. Zhang and Li proved that the sequence i0(F),i1(F),…,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.
Related
- Unimodality of Independence Polynomials for Sufficiently Large Forests
- Unimodality of Kazhdan--Lusztig polynomials of sparse paving matroids
- Proof of Almkvist's conjecture on the unimodality of partition polynomials
- Strict unimodality without log-concavity for partial Petrial polynomials
- Unbounded log-concavity breaks in independence polynomials of spherically symmetric trees
BibTeX
@misc{li2026unimodality,
title = {{Unimodality of Forest Independence Polynomials}},
author = {Wei Li and Kevin Vallier and Tong Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07943},
eprint = {2610.07943},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07943},
}
RIS
TY - UNPB
TI - Unimodality of Forest Independence Polynomials
AU - Wei Li
AU - Kevin Vallier
AU - Tong Zhang
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.07943
UR - https://arxiv.org/abs/2610.07943
AB - 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),…,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.
ER -