Forests have special log concavity property in independence sequences
Barrier Log-Concavity of Large Forests
Discrete Mathematics
Summary
This paper shows that in large forests (collections of trees), the sequences counting independent sets behave in a special way called barrier log-concavity, which means certain numbers in the sequence relate tightly in a curved way. This helps prove that related polynomials, which encode this count, have a smooth shape called strict log-concavity, important for understanding the structure of these graphs. The authors also demonstrate that this property holds under many different conditions and for various large forests and well-covered trees. Their proof involves detailed estimates that work even when the trees have complex structures.
What this means in practice
- •For graph algorithm developers: Design algorithms that exploit strict log-concavity of independence polynomials to improve counting and optimization in tree-like graphs.
- •For combinatorial optimization teams: Use barrier log-concavity properties to refine heuristics for problems involving independent sets and matchings in large forest structures.
A theory result. No direct application yet.
Authors
Vadim E. Levit
Abstract
We prove that the independence sequence of every sufficiently large forest is strictly barrier log-concave: whenever $i_{k+1}>i_k$, one has $i_k^2>i_{k-1}i_{k+1}$. Consequently, every common downward coefficient tilt is unimodal, with one order threshold valid simultaneously for all $0<t\le1$. As an application, we prove that every sufficiently large well-covered tree has a strictly log-concave independence polynomial. More generally, the latter conclusion holds for well-covered forests with sufficiently large matching number. Every sufficiently large forest with a palindromic independence polynomial is also strictly log-concave, with its modes at the central ranks. The proof establishes local coefficient-curvature estimates uniformly over forests of unbounded maximum degree and over activities tending to zero. Combined with the fixed-density theorem of Fang, Lu, Nevo, Yao, and Zheng, these estimates complete the strict log-concavity interval down to rank one through $\lfloor17α/25\rfloor$; the terminal fraction is inherited. The classical decreasing tail then yields the barrier property. A cumulative-coefficient corona theorem transfers barrier log-concavity of the base forest to full strict log-concavity of its leaf corona.