Levit–Mandrescu Unimodality Conjecture

A graph on $n$ vertices is very well-covered if every maximal independent set has size $n/2$ . Levit and Mandrescu conjectured that the independence polynomial $i(G,x)$ of every very well-covered graph is unimodal, i.e. its coefficient sequence is nondecreasing and then nonincreasing.

Result: Disproved
Field: Graph Theory, Independence Polynomials
Posed by: Vadim E. Levit, Eugen Mandrescu
Year posed: 2006
Years open: 20y
Solved: 2026-07-22
Model: GPT-5.6 Sol, Claude Fable 5
Vendor: —
Collaborators: Lucas B.
Verification: Announced (unreviewed)
Notability: No dedicated article

What the AI did

The models produced an explicit counterexample: the whiskering of $E_{588} \vee (39K_{11} \sqcup 85K_{12})$ , a very well-covered graph on 4,074 vertices, whose independence polynomial $(1+x)^{1449}(1+2x)^{588} + (1+x)^{1913}(1+12x)^{39}(1+13x)^{85} - (1+x)^{2037}$ has a strict local valley at $a_{1095}$ . Per the announcement, the search took a few hours once the question was posed.

Verification

Announced on LinkedIn by Lucas B. (Head of AI Research, Jump Trading); no preprint yet, and the reviewers credited are internal to the team rather than independent. The stated polynomial was recomputed with exact integer arithmetic: $a_{1094} > a_{1095} < a_{1096}$ holds, so the polynomial given is genuinely not unimodal, and its low-order coefficients ( $a_0 = 1$ , $a_1 = 4074$ ) are consistent with a graph on 4,074 vertices. What remains unchecked is that the whiskered graph's independence polynomial equals the polynomial stated.

Source

Lucas B. (Jump Trading), LinkedIn announcement

Submitted by Rasmus Lindahl

Spotted something wrong? Corrections are welcome and recorded.

Changelog2 changes

Rasmus Lindahlapproved this entry28 Jul 2026
Rasmus Lindahlsubmitted this entry28 Jul 2026

Levit–Mandrescu Unimodality Conjecture

What the AI did

Verification

Source

Discussion