Erdős Problem 993
For every finite tree , define and let be the maximum cardinality of an independent set in . Prove that there exists such that for every and for every . Equivalently, the sequence is unimodal.
References
- Unimodality of Forest Independence Polynomials — arXiv — Wei Li, Kevin Vallier, Tong Zhang
Source: arXiv
Progress summary
A new preprint claims to settle the tree case, but the claim has not been independently checked and earlier computational work explicitly said the problem was open.
Erdős Problem 993 asks whether, for every tree , the independent-set sequence 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 , totaling 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.
October 2026 claimed resolution
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.
Sources
Solutions 0
No solutions have been posted yet.