Barrier log-concavity for forests
For every finite forest , let be its independence number and write its independence polynomial as , where is the number of independent vertex sets of size . Then, for every integer with , if , one has ; equivalently, the independence sequence of every finite forest is barrier log-concave.
References
- Barrier Log-Concavity of Large Forests — arXiv — Vadim E. Levit
Source: arXiv
Progress summary
A new paper claims the conjectured inequality for all sufficiently large forests, but the statement for every finite forest remains open.
The problem asks whether barrier log-concavity holds for every finite forest. The latest result establishes a uniform sufficiently-large regime and strict consequences for several tree and forest classes, but does not settle the finite case.
Known results
- Levit and Mandrescu (2004) conjectured log-concavity of independence polynomials for all forests.
- Computations verified ordinary log-concavity for trees with at most vertices.
- Kadrawi, Levit, Yosef, and Mizrachi (2023) exhibited non-log-concave trees on vertices; Kadrawi and Levit constructed infinite counterexample families.
- Galvin showed that log-concavity can fail arbitrarily far from the end of the sequence.
October 2026 asymptotic result
Vadim E. Levit's preprint Barrier Log-Concavity of Large Forests claims barrier log-concavity uniformly for sufficiently large forests, yielding strict log-concavity for several tree and forest classes. This is substantial asymptotic progress, but it does not prove the assertion for every finite forest and is unverified here.
Current status (as of October 2026): barrier log-concavity is claimed for a uniform sufficiently-large regime, while the assertion for every finite forest remains open.
Solutions 0
No solutions have been posted yet.