Kadrawi–Levit conjecture on the locations of log-concavity breakdowns in tree independence sequences

About 1 year old · traced to

Let TT be a tree, let α(T)\alpha(T) denote its independence number, and let (ai)i=0α(T)(a_i)_{i=0}^{\alpha(T)} be its independent set sequence. Log-concavity is broken at kk when ak2<ak−1ak+1a_k^2<a_{k-1}a_{k+1}. Kadrawi–Levit's conjecture. For every ℓ≥1\ell\geq 1, there is a tree T=T(ℓ)T=T(\ell) for which log-concavity of the independent set sequence is broken at α(T)−ℓ\alpha(T)-\ell. This conjecture asks how far from the end of a tree's independent set sequence log-concavity can fail; earlier examples broke log-concavity only at the last possible place, while an ad hoc example broke it at α(T)−2\alpha(T)-2.

References

Primary source

David Galvin, “Trees with non log-concave independent set sequences”, arXiv:2502.10654 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.