Sidorenko's conjecture
For finite simple graphs and , let be the probability that a uniformly random map is a homomorphism, and the edge density. Sidorenko conjectured that every bipartite graph with at least one edge satisfies for every : a random graph of the same density minimises the number of copies of . It was known for trees, even cycles, complete bipartite graphs, hypercubes, graphs with a vertex complete to the other side (Conlon-Fox-Sudakov), weakly norming graphs, tree-arrangeable graphs and many other classes. Does every bipartite graph satisfy Sidorenko's inequality?
- Result
- Disproved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Extremal graph theory, homomorphism densities
- Posed by
- Alexander Sidorenko, Inequalities for functionals generated by bipartite graphs (Diskret. Mat., 1991) and A correlation inequality for bipartite graphs (Graphs Combin., 1993)
- Year posed
- 1991
- Years open
- 35y
- Solved
- 2026-09-23
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 52 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1: for the explicit bipartite incidence graph of 22 triples on 13 points ( vertices, edges, connected, degrees 4 to 6 on one side and 3 on the other) there is a finite simple graph with an edge and . Corollaries: tensor powers make arbitrarily small, and blow-ups give a fixed deficit for injective copies at a positive limiting density. Not given: an explicit host graph, the smallest counterexample, or which other bipartite graphs fail.
What the AI did
Produced by an unreleased internal OpenAI model as part of an OpenAI evaluation on open research problems. The release README says the vast majority of results used one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result; this family is not among the README's stated exceptions (the Riemann zeta zero-free region work and the Hodge conjecture for CM abelian varieties). The manuscripts are authored as OpenAI with no human author named. The README also cautions that unformalized results could have issues. The counterexample pattern is explicit (the incidence graph of 22 triples on 13 points, 35 vertices, 66 edges); the host graph is shown to exist by a random-matrix kernel construction over finite fields and sampling, not written down. A Lean formalization of the headline is in the release.
Verification
No independent mathematician has checked this yet. Checked here: the abstract and Theorem 1.1 of 'A counterexample to Sidorenko's conjecture', read against the conjecture in its homomorphism-density form. The proof (symmetric-matrix kernels over F_q, a sign model, Lagrangian intersection estimates) was not refereed. Lean: lean/ComparatorChallenges/SidorenkoCounterexample.json exists with solution_module OAI.Combinatorics.Sidorenko.RandomHost, present at the pinned commit; the challenge is not in the formalization catalogue. Its statement was read: H is defined explicitly as the incidence graph of the 22 listed triples on Fin 13 (bipartite by construction, 66 edges), and the theorem asserts a finite simple graph on Fin n with an edge and homDensity H G < edgeDensity G ^ 66, homomorphisms counted with repetitions. That is the headline. Permitted axioms propext, Quot.sound, Classical.choice. Not rebuilt here. The host is existential, so no finite certificate can be re-run.