Sidorenko's conjecture for K5,5 minus a 10-cycle

Sidorenko's conjecture says that among all graphs of a given edge density, the random graph contains the fewest copies of any bipartite graph. It is proved for many families, and the smallest graph for which it is open is the 10-vertex graph obtained from $K_{5,5}$ by deleting a Hamiltonian cycle. A September 2026 preprint claims a counterexample on 35 vertices to the general conjecture, which leaves this graph undecided. A counterexample would be a finite weighted graph whose densities can be computed exactly.

Problem

A graphon is a symmetric measurable function $W \colon [0,1]^2 \to [0,1]$. For a finite graph $H$, the homomorphism density of $H$ in $W$ is

$$t(H, W) = \int_{[0,1]^{V(H)}} \prod_{\{u,v\} \in E(H)} W(x_u, x_v) \prod_{v \in V(H)} dx_v .$$

Sidorenko's conjecture asserts that every bipartite graph $H$ satisfies $t(H, W) \ge t(K_2, W)^{|E(H)|}$ for all graphons $W$; constant graphons give equality. Let $H$ be the graph obtained from the complete bipartite graph $K_{5,5}$ by removing the edges of a 10-cycle, a 3-regular bipartite graph with 10 vertices and 15 edges.

Task: prove that $t(H, W) \ge t(K_2, W)^{15}$ for every graphon $W$, or find a graphon that violates it.

Background

Sidorenko proposed the conjecture in 1993; in graph terms, the number of copies of a bipartite graph $H$ in a graph $G$ is asymptotically minimized when $G$ is quasirandom. Sidorenko proved it for complete bipartite graphs, even cycles, trees and bipartite graphs with at most four vertices on one side. Later work covered hypercubes (Hatami, 2010), graphs with a vertex adjacent to the whole other side (Conlon, Fox and Sudakov, 2010) and reflection trees (Li and Szegedy), among other classes. The graph $K_{5,5} \setminus C_{10}$ escapes every known method and is described in the literature as the smallest open case.

What is known

• Claimed counterexample to the general conjecture: an OpenAI preprint, A counterexample to Sidorenko's conjecture (23 September 2026), claims that the incidence graph of 22 triples on 13 points, a bipartite graph with 35 vertices and 66 edges, violates the inequality. It is not refereed or formalized, and it does not decide $K_{5,5} \setminus C_{10}$.
• Writing the difference of densities as a sum of squares, the standard certificate for such inequalities, cannot work here: Blekherman, Raymond, Singh and Thomas showed that the smallest open case of Sidorenko's inequality has no sum-of-squares certificate.
• $K_{5,5} \setminus C_{10}$ is not weakly norming (Lee and Schülke), so it lacks this strictly stronger property, which would have implied Sidorenko's inequality.
• Georgiev, Gómez-Serrano, Tao and Wagner (2025) searched for a violating graphon, penalizing near-constant ones, and found none.

What would count as progress

• A counterexample given as a step graphon: part sizes and a symmetric matrix of values in $[0,1]$ with $t(H, W) < t(K_2, W)^{15}$. For a step graphon both densities are finite sums that can be evaluated exactly in rational arithmetic; with a few parts this takes seconds.
• A proof for $K_{5,5} \setminus C_{10}$, necessarily by a method other than sums of squares, or a proof for a larger family that contains it.
• The conjecture is stated in Lean in formal-conjectures.

References

1. A. Sidorenko, "A correlation inequality for bipartite graphs", Graphs and Combinatorics 9 (1993), 201–204. doi:10.1007/BF02988307
2. H. Hatami, "Graph norms and Sidorenko's conjecture", Israel Journal of Mathematics 175 (2010), 125–150. doi:10.1007/s11856-010-0005-1
3. G. Blekherman, A. Raymond, M. Singh and R. R. Thomas, "Simple graph density inequalities with no sum of squares proofs" (2018). arXiv:1812.08820
4. J. Lee and B. Schülke, "Convex graphon parameters and graph norms" (2019). arXiv:1910.08454
5. B. Georgiev, J. Gómez-Serrano, T. Tao and A. Z. Wagner, "Mathematical exploration and discovery at scale" (2025), Problem 6.26. arXiv:2511.02864

Source

Imported from AlphaEvolve Repository of Problems, problem 26, curated by Google DeepMind. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.