Graph-theory open problems

Sidorenko's Conjecture

OPG_sidorenko_bipartite_homomorphism_density

Source: Open Problem Garden: sidorenkos_conjecture

High ★★★ Graph Theory
Author: Sidorenko, A.— posted by Jon Noel on 2019-10-10

Status ai-disproved high confidence

OpenAI's manuscript exhibits a connected bipartite graph $H$ with 35 vertices and 66 edges (the incidence graph of 22 triples on 13 points) and a finite simple graph $G$ with $t(H,G) < t(K_2,G)^{66}$.

Cited literature (5)

  • partial Sidorenko's conjecture for blow-ups (2021)
    David Conlon, Joonkyung Lee · Discrete Analysis · arXiv:1809.01259 · doi:10.19086/da.21472

    For every bipartite graph H there exists a positive integer p such that the p-blow-up of H satisfies Sidorenko's conjecture; also proves the conjecture for all bipartite graphs whose degree sequence satisfies a certain divisibility condition.

  • partial Sidorenko's conjecture for subdivisions and theta substitutions (2024)
    Seonghyuk Im, Ruonan Li, Hong Liu · arXiv preprint · arXiv:2408.03491

    Proves Sidorenko's conjecture for bipartite graphs obtained by replacing each edge of a complete graph with a generalized theta graph (with divisibility conditions), extending earlier subdivision results by Conlon, Kim, Lee, and Lee.

  • reduction Extremal numbers and Sidorenko's conjecture (2023)
    David Conlon, Joonkyung Lee, Alexander Sidorenko · arXiv preprint · arXiv:2307.04588

    Shows that failures of Sidorenko's conjecture for uniform hypergraphs yield improved lower bounds on extremal numbers; identifies new hypergraph counterexamples to the conjecture.

  • partial Variations on Sidorenko's conjecture in tournaments (2024)
    Jacob Fox, Zoe Himwich, Nitya Mani, Yunkun Zhou · arXiv preprint · arXiv:2402.08418

    Develops tournament analogues of Sidorenko's conjecture: proves asymptotically tight bounds on the maximum number of edges in a tournament anti-Sidorenko digraph, gives novel constructions of tournament Sidorenko digraphs, and fully characterises which orientations of stars are tournament Sidorenko or tournament anti-Sidorenko.

  • partial A note on directed analogues of the Sidorenko and forcing conjectures (2022)
    Jacob Fox, Zoe Himwich, Nitya Mani, Yunkun Zhou · arXiv preprint · arXiv:2210.16971

    Proves two necessary conditions for the directed forcing property (Theorem 1.6) and shows that an oriented graph $B$ with a homomorphism $B \to \vec{K}_2$ has the directed forcing property if and only if its underlying undirected bipartite graph has the asymmetric forcing property (Theorem 1.8).

Reviewer notes. Literature status before this model-generated claim: partial. Sidorenko's conjecture remains open in full generality for all bipartite graphs. Since the OPG posting, the key referenced paper by Conlon and Lee was formally published in *Discrete Analysis* (2021), proving that every bipartite graph $H$ has some blow-up satisfying the conjecture. Im, Li, and Liu (2024) further extended known cases to graphs obtained by replacing edges of a complete graph with generalized theta graphs. The conjecture is still open for many specific bipartite graphs, including $K_{5,5}$ minus a perfect matching.

Auto-reviewed 2026-10-07 with claude-opus-5-5 (manual match against the OpenAI catalogue; TeX sources read).

OpenAI manuscript collection ai-disproved

Family 161: Counterexamples to Sidorenko’s conjecture and the forcing conjecture · Lean formalization scope

These manuscripts were produced by an unreleased OpenAI model and released on 2026-10-06 in github.com/openai/math. They have not been peer reviewed. Lean formalizations are OpenAI's own and cover only the scope stated on their scope page; this project has not run or reviewed them. The status above records the claim; before it, the literature review rated this entry partial. Its confidence rates whether the manuscript's theorem settles this entry, not whether the manuscript is correct.

Conjecture. For any bipartite graph $ H $ and graph $ G $ , the number of homomorphisms from $ H $ to $ G $ is at least $ \left(\frac{2|E(G)|}{|V(G)|^2}\right)^{|E(H)|}|V(G)|^{|V(H)|} $ .
Keywords: density problems · extremal combinatorics · homomorphism

Discussion

A homomorphism from a graph $ H $ to a graph $ G $ is a mapping $ f:V(H)\to V(G) $ which preserves edges. Given graphs $ H $ and $ G $ , the homomorphism density of $ H $ in $ G $ , denoted $ t(H,G) $ , is the probability that a random function $ f:V(H)\to V(G) $ is a homomorphism. That is, $$t(H,G)=\frac{\left|\left\{f: V(H)\to V(G): f\text{ is a homomorphism from }H\text{ to }G\right\}\right|}{|V(G)|^{|V(H)|}}.$$ In this language, Sidorenko's Conjecture says that, if $ H $ is bipartite, then every graph $ G $ satisfies $$t(H,G)\geq t(K_2,G)^{|E(H)|}.$$ There are lots of results on Sidorenko's Conjecture; rather than listing them all here, we encourage the reader to see the references of the recent paper [CL].

Bibliography