The Simonovits Product Conjecture

Simonovits conjectured that if a forbidden family $\mathcal{F}$ with $p(\mathcal{F}) > 1$ has extremal number exceeding the Turan bound by a superlinear surplus, then its extremal graphs are joins of $p$ graphs, each extremal for a family of chromatic number two. Disproved by a fixed finite family $\mathcal{L}$ with $p(\mathcal{L}) = 2$ and $\mathrm{ex}(n,\mathcal{L}) > t_2(n) + cn^{3/2}$ that nevertheless has, at every large order, an extremal graph with connected complement and hence no nontrivial join decomposition. The same construction disproves the Weak Product Conjecture of Furedi and Simonovits.

Result: Disproved(see note)
Status: Resolved
AI contribution: AI-discovered
Method: Construction
Field: Extremal graph theory
Posed by: Miklos Simonovits
Year posed: —
Years open: —
Solved: 2026-08-03
Model: GPT-5.6 Sol
Vendor: OpenAI
Collaborators: Chuandong Xu
Verification: Unreviewed
Publication: Preprint
Significance: 18 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

one construction disproves both the product conjecture and its weak form

What the AI did

The paper's comment credits the counterexample to GPT-5.6 Sol, found during a Codex project devoted to the Product Conjecture. The exact extremal-number and equality-case analysis around it is the author's.

Verification

Single-author arXiv preprint; not yet peer-reviewed.

Source

arXiv:2608.02115 - A finite forbidden family with superlinear surplus and non-join extremal graphs

Submitted by Curator34

The Simonovits Product Conjecture

What was actually shown

What the AI did

Verification

Source

Discussion