Browse › Combinatorics › 161 Counterexamples to Sidorenko’s conjecture and the forcing conjecture
A counterexample to Sidorenko's conjecture
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We disprove Sidorenko's conjecture with a bipartite graph on 35 vertices and 66 edges: its homomorphism density in some finite simple graph is smaller than the conjectured lower bound. The same connected graph also disproves the forcing conjecture: at one fixed density, asymptotically matching the edge and pattern densities does not imply quasirandomness.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-23) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Rohan Arun (GitHub: rohanarun), sidorenko-template-refinements (GitHub repository, October 2026). Reports a computer-assisted 35-vertex minimum within a specified finite construction template and lowers the nondirect residual constant from the paper's 1641 to 189; the README says it does not claim a smaller general counterexample or formal verification. [AI-generated per source]
- rohanarun/van-der-waerden-refinement, Conditional refinements of OpenAI's October 2026 math release (GitHub research repository, accessed 2026-10-21). Its Sidorenko component reports reconstruction and computational checks of the paper's finite combinatorial certificate and unsuccessful nonexhaustive searches for a smaller one, explicitly excluding verification of the full analytic proof. [AI-generated per source]
- Erebos Labs, sidorenko-sharp-coercivity (GitHub repository, 2026). Proves sharp coercivity constants for the real relaxation of the construction and, under the paper's analytic inputs, specializes the host parameters from D=7296 to D=600 without instantiating a host graph. [AI-generated per source]
- acprk, A Sidorenko counterexample with 17 vertices and 30 edges (remark R6 in openai-math-remarks) (GitHub repository, October 2026). Proposes the point–face incidence graph of a 7-point triangulated sphere as a smaller counterexample, conditional on the paper's rank-layer lemma (Lemma 3.1, Sections 4–7) carrying over to the new complex; the remark states this was not re-derived. [AI-generated per source]
- Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář and Adrián Zámečník, A six-spin obstruction to antiferromagnetic biclique maximization (hexagon:2610.00241v1, 2026-10-14). Cites this paper and distinguishes it from its own counterexample to a conjecture of Sah, Sawhney, Stoner and Zhao on a degree-dependent biclique bound for antiferromagnetic spin models, a different problem. [AI-generated per source]
Comments and discussion
- Pico (AI agent), openai-math-counterexamples (GitHub repository, October 2026). An independent computational check that confirms the 35-vertex, 66-edge graph H and the clauses of the paper's proposition on the triple system; it classifies the host graph G as "not explicit" and does not attempt to construct it. [AI-generated per source]
- Hamed Hatami (@HamedHa26534517), post on X (2026-10-06). Calls the result "not surprising" but notes the counterexample "seems complicated and not just a numerical solution to some optimization problem," suggesting there may be something interesting in it.
Formalization
- OpenAI math release, Counterexamples to Sidorenko's conjecture and the forcing conjecture — Lean scope note (mirrored at mathcommunity/oai-math-revised) (lean/docs/161.md, 2026-10-06). The release's Lean development proves the existence of a nonempty finite simple host G with t(H,G) < t(K_2,G)^66 for the paper's fixed 35-vertex, 66-edge H and links its Comparator statement; the forcing-conjecture consequence is outside its scope. [family-level]
- Google DeepMind formal-conjectures, FormalConjectures/Wikipedia/SidorenkoConjecture.lean (formal-conjectures, October 2026). States Sidorenko's conjecture in negated form, marks it solved and links a formal proof to OpenAI's repository; the graphon form is also marked solved, but its proof is
sorry. - mo271, feat: mark problems solved in the OpenAI math release and link formal proofs (PR #6898) (formal-conjectures PR, merged 2026-10-11). Marks the finite form refuted; it notes the graphon form has no
formal_prooflink "because the step-graphon reduction is not formalized."
Possibly relevant literature (found by the agent, not checked)
- Yuqi Zhao, Tensor Amplification and Spectral Transfer for Sidorenko-Type Inequalities (arXiv:2607.02260, 2026-07-02). Builds a tensor-power amplification framework for Sidorenko-type inequalities in graphon classes, which relates to the tensor-power step in Corollary 1.3(i); the paper's bibliography cites only Zhao's arXiv:2606.15368, not this one.
- Jacob Fox, Zoe Himwich, Nitya Mani and Yunkun Zhou, A note on directed analogues of the Sidorenko and forcing conjectures (arXiv:2210.16971, 2022-10-30). Its equivalences between directed variants and asymmetric undirected variants provide potentially relevant context for the paper's Sidorenko counterexample and forcing corollary; their application to this construction has not been checked.
Digests and expositions
- Latent Seminar, Homomorphism densities and Sidorenko counterexamples (2026-10-07). This exposition outlines the sign cancellation, dilution, symmetrization, finite sampling and forcing arguments, and states that it does not independently verify the complete proof. [family-level]
- AI Proved What?, Sidorenko disproved? (Episode 161, October 2026). The video and accompanying transcript explain the incidence pattern and proof strategy, distinguishing the finite-host existence claim, the forcing consequence at one density and the stated Lean coverage. [AI-generated per source] [family-level]
News and blogs
- Carlos Toledo, OpenAI's math release: what it claims beyond what it checks (audit report, 2026-10-10). The report's Sidorenko discussion distinguishes the formal existence proof from the absence of a published explicit host graph that could be inspected as a finite witness.
- Rohan Arun (@RohanArun), post on X (2026-10-10). Following an earlier post reporting a reduction from 978 to 189, announces cutting the paper's Sidorenko residual constant further "from 189 to 28," work the posts attribute to AI agents. [AI-generated per source]
Elsewhere
- Hexagon: A six-spin obstruction to antiferromagnetic biclique maximization (AI-generated; human understanding: some)
- VibeMathed: Problem record
- VibeMathed: Problem record
- Emergent Mind: family 161
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:A-counterexample-to-Sidorenkos-conjecture-September-23-2026,
author = {{OpenAI}},
title = {{A counterexample to Sidorenko's conjecture}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-counterexample-to-Sidorenkos-conjecture-September-23-2026/paper.pdf}{OAI:A-counterexample-to-Sidorenkos-conjecture-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/161.md. The Lean statements have not been checked by people against the paper's claims.
Family 161: Counterexamples to Sidorenko’s conjecture and the forcing conjecture
Disproves Sidorenko's conjecture with a connected bipartite pattern on 35 vertices and 66 edges that occurs less frequently than in a random graph of the same edge density. The same pattern disproves the forcing conjecture of Skokan and Thoma: matching its density and the edge density of a constant graphon need not force quasirandomness.
This is the only paper in this family.