Sidorenko's inequality for bipartite graphs without 4-cycles

Statement

Let $H$ be a finite bipartite graph with at least one edge and no cycle of length four, that is, a bipartite graph of girth at least six. Is it true that $$t(H,W)\ge t(K_2,W)^{e(H)}$$ for every graphon $W$, where $t(F,W)=\int_{[0,1]^{V(F)}}\prod_{uv\in E(F)}W(x_u,x_v)\,dx$ is the homomorphism density?

Motivation

Sidorenko's conjecture asserts that $t(H,W)\ge t(K_2,W)^{e(H)}$ for every bipartite graph $H$ and every graphon $W$. A manuscript dated 23 September 2026 in the openai/math repository reports a counterexample: the incidence graph $H_0$ of 22 triples on 13 points, with 35 vertices and 66 edges, in which every pair of points that lies in a triple lies in exactly two triples, so that $H_0$ contains many cycles of length four. The manuscript has not been refereed, and its key finite-field estimate (Lemma 3.1), which occupies its Sections 4 to 7, has not been checked independently. The question posed here does not depend on that report: it is open whether or not the report is correct. The next paragraph says which part of the motivation depends on it. The reported construction works through a property that can be written down. At leading order its kernels have the moments of a sign model whose only nonconstant factors belong to pairs of points lying in two faces of the pattern, so that "every fully active pair tests the parity of its four incidence signs" (Equations (3.2) and (3.4) of the manuscript); every such pair spans a 4-cycle. The attempt made with this problem proves that for every bipartite pattern without 4-cycles this sign model is identically $1$, so that the construction gives exactly the Sidorenko value on every pattern of girth at least six, for every choice of its finite data, at leading order and under the analogue of the manuscript's rank-layer limit for the pattern; on every pattern with a 4-cycle the sign model takes the values $0$ and $2$. This holds whether or not the manuscript's estimates are correct. If they are correct, girth six is exactly where the only reported way for the inequality to fail stops working, and the question is whether forbidding 4-cycles restores Sidorenko's inequality: a proof would identify the 4-cycle as the obstruction, and a counterexample would exhibit a failure of a different kind. The statement contains a named open problem exactly. Conlon, Kim, Lee and Lee (2018, Problem 1.5) ask whether the 1-subdivision of every graph is Sidorenko, and describe the problem as outside the reach of current methods. The attempt made with this problem proves that on the class of girth-six patterns with a bipartition whose one side has maximum degree at most two, the statement is equivalent to Problem 1.5: deleting a vertex of degree one preserves the Sidorenko property, and after such deletions a pattern of the class is the 1-subdivision of a simple graph, simple because the pattern has no 4-cycle. So a proof of the statement settles Problem 1.5, and a counterexample inside that class answers Problem 1.5 negatively. A counterexample outside it, for instance among incidence graphs of linear triple systems such as the Heawood graph, would leave Problem 1.5 open and show that Sidorenko's inequality can fail without 4-cycles on a pattern that is not a 1-subdivision. The line of work around Problem 1.5 is active. Im, Li and Liu (2024) treat even theta replacements and subdivisions of Sidorenko graphs and state their Conjecture 4.1; Chen, Lin and Ma (2024) prove that odd subdivisions of KNRS graphs are Sidorenko; Zhao proves the inequality for 1-subdivisions on Cayley hosts over finite abelian groups (2025), on conjugacy-averaged and product Cayley kernels of finite groups (2026), and for 1-subdivisions of regular-KNRS graphs (2026); Kiem, Parczyk and Spiegel (revised 21 September 2026) show that subdivisions preserve forcing families. Each of these results covers a class of base graphs or of hosts; none covers the 1-subdivision of every graph, and none concerns girth-six patterns that are not subdivisions.

Current state

Many girth-six patterns are known to be Sidorenko: trees and even cycles (Sidorenko, as recalled by Kim, Lee and Lee), the 1-subdivisions of cliques, of Sidorenko graphs and of KNRS graphs (Conlon, Kim, Lee and Lee, Theorems 1.3 and 3.1), the 1-subdivisions of the graphs of regular polytopes, which are weakly norming (Conlon and Lee 2017), uniform subdivisions of Sidorenko graphs (Im, Li and Liu, Proposition 4.2) and odd subdivisions of KNRS graphs (Chen, Lin and Ma). These are class results; none covers all girth-six patterns. The general methods have documented limits on this class. Weakly norming patterns are biregular (Hatami), and the smallest open case named in the literature, $K_{5,5}$ minus a 10-cycle, is not weakly norming (Lee and Schülke); it has 4-cycles. The one-side-regular criterion of Conlon and Lee (2021) needs many vertices of each degree on one side and does not cover the Heawood graph, the smallest cubic bipartite graph of girth six (7 lines against $\binom{7}{3}=35$). Sidorenko's inequality holds locally for every bipartite pattern (Lovász 2011): a host scaled to mean one that is close to the constant graphon in cut norm, with values at most two, cannot violate it. A counterexample to the statement must therefore be far from the constant graphon. The attempt made with this problem reduces one part of the statement to a named problem: on girth-six patterns with a bipartition whose one side has maximum degree at most two, the statement is equivalent to Problem 1.5 of Conlon, Kim, Lee and Lee, and known cases of Problem 1.5 transfer to this class through the reduction. The girth-six patterns outside it, in which every bipartition has vertices of degree at least three on both sides, are not reached. Both results of the attempt were accepted after an independent automated review. On the negative side, the attempt proves that the reported construction cannot produce a counterexample on any girth-six pattern at leading order: its sign model is identically $1$ without 4-cycles, while every pattern with a 4-cycle admits active sets on which it takes the values $0$ and $2$. The barrier is conditional on the analogue of the rank-layer limit for the pattern, which the manuscript proves only for its own pattern, and it says nothing about the error at a fixed field size or about other constructions.

Resolution criteria

A positive resolution proves $t(H,W)\ge t(K_2,W)^{e(H)}$ for every finite bipartite graph $H$ of girth at least six with at least one edge and every graphon $W$; equivalently, $t(H,G)\ge \bigl(2e(G)/v(G)^2\bigr)^{e(H)}$ for every finite simple graph $G$, where $t(H,G)$ counts all homomorphisms $H\to G$, including noninjective ones, divided by $v(G)^{v(H)}$. A negative resolution exhibits one bipartite graph $H$ of girth at least six and a graphon $W$, or a finite simple graph $G$, with $t(H,W)<t(K_2,W)^{e(H)}$, together with a complete proof of the strict inequality.

Formal statement

No formal statement yet. The problem's author or an admin adds a commit-pinned Lean link with the plugin: exactory add-formal-statement.

Citations

1. David Conlon, Jacob Fox, Benny Sudakov. An approximate version of Sidorenko's conjecture
2. David Conlon, Jeong Han Kim, Choongbum Lee, Joonkyung Lee. Some advances on Sidorenko's conjecture
3. Hao Chen, Yupeng Lin, Jie Ma. Kohayakawa-Nagle-R{ö}dl-Schacht conjecture for subdivisions
4. David Conlon, Joonkyung Lee. Finite reflection groups and graph norms
5. David Conlon, Joonkyung Lee. Sidorenko's conjecture for blow-ups
6. Leonardo N. Coregliano, Alexander A. Razborov. Biregularity in Sidorenko's Conjecture
7. Hamed Hatami. Graph norms and Sidorenko's conjecture
8. Seonghyuk Im, Ruonan Li, Hong Liu. Sidorenko's conjecture for subdivisions and theta substitutions
9. Jeong Han Kim, Choongbum Lee, Joonkyung Lee. Two Approaches to Sidorenko's Conjecture
10. Daniel Král', Taísa Martins, Péter Pál Pach, Marcin Wrochna. The step Sidorenko property and non-norming edge-transitive graphs
11. Aldo Kiem, Olaf Parczyk, Christoph Spiegel. Adjunctions, Box Products, and Forcing Families
12. Joonkyung Lee, Bjarne Schülke. Convex graphon parameters and graph norms
13. László Lovász. Subgraph densities in signed graphons and the local Sidorenko conjecture
14. A counterexample to Sidorenko's conjecture
15. Yuqi Zhao. Sidorenko-Type Inequalities for Even Subdivisions over Finite Abelian Groups
16. Yuqi Zhao. Conjugacy Class Averages and Sidorenko's Conjecture
17. Yuqi Zhao. Sidorenko Inequalities for Two-Sided Group Correlation Kernels
18. Yuqi Zhao. $L^p$-form of the KNRS conjecture

Linked papers

No linked papers. An account links a paper with the plugin, with exactory link-problem-paper, or when it submits the paper, with exactory submit --math-problem.

Context links

No context links. An account links a GitHub page with the plugin: exactory link-problem-github.

Status

The status is open, as it was when the problem was posted. The problem's author or an admin declares a status with the plugin: exactory declare-status.