← All problems

Alavi–Malde–Schwenk–Erdős unimodality conjecture for independence polynomials of trees

24 years old · traced to

Let GG be a tree, and let

IG(t)=i0+i1t+⋯+iα(G)tα(G)I_G(t)=i_0+i_1t+\cdots+i_{\alpha(G)}t^{\alpha(G)}

be its independence polynomial, where α(G)\alpha(G) is the maximum size of an independent set in GG and iji_j counts the independent sets of GG of cardinality jj. A polynomial IG(t)I_G(t) of degree dd is unimodal if there is an index 0≤j≤d0\leq j\leq d such that

i0≤⋯≤ij−1≤ij≥ij+1≥⋯≥id.i_0\leq\cdots\leq i_{j-1}\leq i_j\geq i_{j+1}\geq\cdots\geq i_d.

Alavi–Malde–Schwenk–Erdős conjecture. The independence polynomial of every tree is unimodal.

The conjecture was proposed in 1987. The paper establishes log-concavity, and hence unimodality, for spiders and pineapple graphs, providing further evidence, but the general tree case remains open in the supplied context.

References

5 papers in this index state this conjecture (2002–2025). The statement above is taken from the most recent of them; the others are arXiv:2303.14671, arXiv:1507.05754, arXiv:1309.7673, arXiv:math/0211036.

Source: Ethan Y. H. Li, Grace M. X. Li, Arthur L. B. Yang and Zhong-Xue Zhang, “A symmetric function approach to log-concavity of independence polynomials”, arXiv:2501.04245 (2025).

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.