← All problems

Barrier log-concavity for forests

For every finite forest FF, let α(F)\alpha(F) be its independence number and write its independence polynomial as I(F;x)=∑k=0α(F)ikxkI(F;x)=\sum_{k=0}^{\alpha(F)} i_k x^k, where iki_k is the number of independent vertex sets of size kk. Then, for every integer kk with 1≤k<α(F)1\le k<\alpha(F), if ik+1>iki_{k+1}>i_k, one has ik2>ik−1ik+1i_k^2>i_{k-1}i_{k+1}; equivalently, the independence sequence of every finite forest is barrier log-concave.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 2525 vertices.
  • Kadrawi, Levit, Yosef, and Mizrachi (2023) exhibited non-log-concave trees on 2626 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.

Sources

Solutions 0

No solutions have been posted yet.