For every finite tree T, define i_k(T)=|I⊆ V(T): I is independent and |I|=k| and let alpha(T) be the maximum cardinality of an independent set in T. Prove that there exists m∈0,1,…,alpha(T) such that i_k(T)≤ i_k+1(T) for every 0≤ k<m and i_k(T)≥ i_k+1(T) for every m≤ k<alpha(T). Equivalently, the sequence (i_0(T),i_1(T),…,i_alpha(T)(T)) is unimodal.

Erdős Problem 993

Erdős Problem 993 asks whether, for every tree $T$ , the independent-set sequence $\left(i_0(T),\ldots,i_{\alpha(T)}(T)\right)$ is unimodal. The available evidence records substantial computation and partial cases, but no previously verified proof for unrestricted trees.

Known results

Exhaustive computation found no counterexample among all trees with $n \le 29$ , totaling $8{,}691{,}747{,}673$ trees.
Log-concavity is reported for double brooms and for trees with at most two vertices of degree at least three.
The repository explicitly states that the unrestricted tree case remains open and that its Lean work has not been peer reviewed.

October 2026 claimed resolution

Wei Li, Kevin Vallier, and Tong Zhang's arXiv preprint Unimodality of Forest Independence Polynomials reports an analytic and computer-assisted proof, together with a Lean 4 encoding, which would resolve the problem. The retrieved evidence does not include independent mathematical assessment, so this remains an unverified claim.

Current status (as of October 2026): The conjecture remains open in the evidence available here; an arXiv preprint claims a proof, but that claim is unverified.

Erdős Problem 993

Primary source

Additional references

Progress summary

Solutions 0