The Simonovits Product Conjecture
Simonovits conjectured that if a forbidden family with has extremal number exceeding the Turan bound by a superlinear surplus, then its extremal graphs are joins of graphs, each extremal for a family of chromatic number two. Disproved by a fixed finite family with and 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, Zoltán Füredi
- Year posed
- 2013
- Years open
- 13y
- Solved
- 2026-08-03
- Model
- GPT-5.6 Sol
- Vendor
- OpenAI
- Collaborators
- Chuandong Xu
- Verification
- Lean-checked, statement unaudited
- Publication
- Preprint
- Significance
- 18 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
One construction disproves both the product conjecture and its no-forst form, but not the weak form of the conjecture.
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. Lean formalization released but not audited by any third party.
Sources
Submitted by Curator34 on