Metraipolis › archive › dc_b11073995388

Unimodality of Forest Independence Polynomials — arXiv:2610.07943

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.07943
License (as archived)
CC0-1.0
Archived
2026-10-07T11:53:14.041Z
SHA-256 of the archived text
67b0a4c7cce49821559877f1601d16a50dd62aec9b5346a8cc676041e690ef1e
Stable URL of this page
https://metraipolis.com/documento/dc_b11073995388

How to cite

Unimodality of Forest Independence Polynomials — arXiv:2610.07943 — arXiv (en), https://arxiv.org/abs/2610.07943 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b11073995388 (Metraipolis archive dc_b11073995388, sha256 67b0a4c7cce49821559877f1601d16a50dd62aec9b5346a8cc676041e690ef1e)
BibTeX
@misc{dcb11073995388,
  title = {Unimodality of Forest Independence Polynomials — arXiv:2610.07943},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.07943},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b11073995388; sha256 67b0a4c7cce49821559877f1601d16a50dd62aec9b5346a8cc676041e690ef1e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.07943. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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_{\alpha(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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.07943 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:22:09.555Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).