Sidorenko's Conjecture for Bipartite Graphons

Sidorenko's Conjecture for Bipartite Graphons

OpenAI's claim

Sidorenko and forcing counterexamples: A connected bipartite graph with 35 vertices and 66 edges is claimed to violate Sidorenko’s homomorphism-density lower bound in a finite host. The same pattern is also claimed not to force quasirandomness when the edge and pattern densities match their random values.

Mathematical statement of the claimed result

Mathematical claim 1.

Let $H$ be the incidence graph of the explicitly tabulated $22$ triples on $13$ points: it is connected and bipartite with $35$ vertices and $66$ edges. For $t(H,G)=\operatorname{hom}(H,G)/|V(G)|^{35}$ and $p(G)=2|E(G)|/|V(G)|^2$, a finite simple graph $G$ with $p(G)>0$ is claimed to satisfy $t(H,G)<p(G)^{66}$. Moreover, for every $c>0$ another graph $F$ has $0<t(K_2,F)$ and $t(H,F)<c\,p(F)^{66}$. The forcing corollary claims some $p\in(0,1)$ and a nonconstant symmetric measurable graphon $W:[0,1]^2\to[0,1]$ with \[t(K_2,W)=p,\qquad t(H,W)=p^{66},\qquad t(H,W)=\int_{[0,1]^{35}}\prod_{ij\in E(H)}W(x_i,x_j)\,dx.\] Thus equality at that density does not force this cyclic bipartite graph to be quasirandom.

Outline of the argument

Sidorenko and forcing counterexamples: The construction combines rank and discriminant relations for symmetric matrices with counts of symplectic intersections. Quadratic Gauss-sum estimates control joint signs, while type scores distinguish the desired vertex roles. Singular configurations are estimated separately so that the signed rank-layer correlations survive normalization and transfer to a finite host graph.

Formal verification

Family 161 describes Lean coverage for the fixed-pattern Sidorenko deficit; the forcing consequence is not selected.

Sidorenko and forcing counterexamples: The manuscript links SidorenkoCounterexample.lean.

The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

• OpenAI, A counterexample to Sidorenko's conjecture, 2026-09-23; citation key OAI:A-counterexample-to-Sidorenkos-conjecture-September-23-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main; Statement source: cor:amplification; Statement source: cor:forcing.
• Family 161: Lean scope.
• Comparator SidorenkoCounterexample.json.
• Comparator SidorenkoCounterexample.lean.
• OpenAI catalogue entry.

Sidorenko's Conjecture for Bipartite Graphons

Definitions and mathematical statement

A graphon is a symmetric measurable function $W:[0,1]^2\to[0,1]$. For a finite simple graph $H=(V,E)$, define its homomorphism density by \[ t(H,W)=\int_{[0,1]^{V}}\prod_{\{u,v\}\in E}W(x_u,x_v)\prod_{u\in V}{\,\mathrm{d}} x_u. \] Sidorenko's assertion is $t(H,W)\ge t(K_2,W)^{|E(H)|}$ for every bipartite $H$ and every graphon. For the constant graphon $W\equiv p$ there is equality, explaining the quasirandom comparison. Homomorphisms may identify vertices; replacing their density by the density of induced copies or injective embeddings changes the finite-object statement.

Formulation and concept references: [S1].

Short English statement

Among graph limits with a fixed edge density, does the constant graphon minimize the homomorphism density of every bipartite graph?

Research attempt

Scope and primary-source check.

This attempt was developed by GPT-6 Astra Ultra on 27 September 2026. The source [S1] treats reductions involving biregularity; it does not license replacing an arbitrary bipartite graph by a complete bipartite graph without a proof. Here all densities are homomorphism densities with independent uniform vertex variables. The work proves the desired inequality for complete bipartite graphs, trees, even cycles, and rank-one graphons, and examines the obstruction to combining those arguments. These established special mechanisms are not presented as a new general solution.

Put $p=\int_{[0,1]^2}W$ and $d(x)=\int_0^1W(x,y)\,dy$. If $p=0$, then $W=0$ almost everywhere, so every graph with an edge has density zero and the assertion holds. Edgeless graphs have density one; the convention $p^0=1$ is used. Isolated vertices can be removed from $H$ without changing either side. Hence nontrivial proofs below may assume $p>0$ and no isolated vertices.

Complete bipartite graphs: two exact Jensen steps.

Let $H=K_{s,t}$ with $s,t\ge1$. Integrate first over its $t$ vertices on one side and define \[ A(x_1,\ldots,x_s)=\int_0^1\prod_{i=1}^sW(x_i,y)\,dy. \] Fubini's theorem and two uses of Jensen's inequality give \[ \begin{split} t(K_{s,t},W)&=\int A(x_1,\ldots,x_s)^t\,dx_1\cdots dx_s\\ &\ge\left(\int A\right)^t =\left(\int_0^1d(y)^s\,dy\right)^t \ge p^{st}. \end{split} \tag{1} \] All functions are bounded and nonnegative, so the changes of order and powers are justified without integrability qualifications. The argument uses the identical neighborhoods of vertices on one side. General bipartite graphs do not have that factorization.

For $C_4=K_{2,2}$, keeping the intermediate term yields a stability calculation. If $v=\int(d-p)^2$, then $\int d^2=p^2+v$ and \[ t(C_4,W)-p^4\ge2p^2v+v^2. \tag{2} \] Small four-cycle excess thus controls degree variation. Conversely, small degree variation alone does not bound the four-cycle excess. For example take two equal blocks and $W=a$ across the blocks and zero within them, with $0<a\le1$. Every degree is $a/2$, but \[ p=a/2,\qquad t(C_4,W)=a^4/8=2p^4. \] This is a direct test against the inference that regularity alone makes a graphon constant.

Trees: a stationary Markov construction.

Let $T$ be a tree with $v\ge2$ vertices. Initially assume $W\ge\epsilon>0$; the general case will follow by approximation. Define the probability density $\pi(x)=d(x)/p$ and transition density \[ P(x,y)=\frac{W(x,y)}{d(x)}. \] Symmetry of $W$ gives stationarity: $\int\pi(x)P(x,y)\,dx=\pi(y)$. Root the tree anywhere, draw the root from $\pi$, and draw each child from the transition law of its parent, independently given the parents. The resulting density on all vertex variables is \[ f((x_u)_{u\in V(T)})= \frac1p\prod_{uv\in E(T)}W(x_u,x_v) \prod_{u\in V(T)}d(x_u)^{1-\deg_T(u)}.\tag{3} \] This follows by counting denominators at each vertex; the root has one extra factor $d/p$ from its initial density. Every marginal is $\pi$.

Rearranging $3$, and applying Jensen to the exponential, gives \[ \begin{split} t(T,W) &=p\,\mathbb E_f\prod_ud(X_u)^{\deg_T(u)-1}\\ &\ge p\exp\left(\sum_u(\deg_T(u)-1) \int\pi(x)\log d(x)\,dx\right). \end{split} \tag{4} \] The sum of coefficients is $2(v-1)-v=v-2$. Convexity of $z\log z$ implies \[ \int\pi\log d=\frac1p\int d\log d\ge\log p. \] Thus $t(T,W)\ge p^{v-1}$, as required. The use of natural logarithms inside this entropy calculation has no effect on the power-law conclusion.

For a general graphon, set $W_\epsilon=(1-\epsilon)W+\epsilon$. It is bounded below by $\epsilon$ and converges uniformly to $W$. For a graph with $e$ edges, telescoping the product of its edge factors shows $|t(H,W_\epsilon)-t(H,W)|\le e\|W_\epsilon-W\|_\infty$. Also $p_\epsilon\to p$. Letting $\epsilon\downarrow0$ proves the tree inequality without taking logarithms of zero. Disjoint components factor under the defining integral, so the result extends to forests.

This proof specifies the joint distribution rather than assuming that edge variables are independent. Tree structure is used to construct it. Trying the same root-and-child procedure around a cycle creates a compatibility constraint not present in $3$.

Even cycles: the operator argument.

Let $T_W$ be the self-adjoint integral operator on real $L^2[0,1]$, $(T_Wf)(x)=\int W(x,y)f(y)\,dy$. It is Hilbert--Schmidt because $W\in L^2$, and hence compact. For $k\ge2$, its eigenvalues $(\lambda_j)$ satisfy \[ t(C_{2k},W)=\operatorname{tr}(T_W^{2k}) =\sum_j\lambda_j^{2k}. \tag{5} \] One can obtain the first equality by writing the kernel of $T_W^k$ and taking its squared Hilbert--Schmidt norm; Fubini joins two length-$k$ paths into the $2k$-cycle. Absolute convergence follows from $\sum_j\lambda_j^2<\infty$ and boundedness of the eigenvalues. The constant function $1$ has $L^2$ norm one and $\langle1,T_W1\rangle=p$, so $\|T_W\|\ge p$. Consequently \[ t(C_{2k},W)\ge p^{2k}. \tag{6} \] Even powers are essential: the operator need not be positive semidefinite merely because its kernel is pointwise nonnegative.

There is a useful equality check for $C_4$. If $t(C_4,W)=p^4$ with $p>0$, equality in $\sum\lambda_j^4\ge\|T_W\|^4\ge p^4$ forces a single nonzero eigenvalue and equality in the Rayleigh bound at $1$. That eigenvalue is $p$ and its eigenspace contains $1$, so $T_Wf=p\langle f,1\rangle1$. Equality of Hilbert--Schmidt kernels then gives $W=p$ almost everywhere. No injective-copy interpretation is used in this conclusion.

A broad test family: rank-one kernels.

If $W(x,y)=f(x)f(y)$ with $0\le f\le1$, then \[ t(H,W)=\prod_{u\in V(H)}\int f^{\deg_H(u)}. \] Jensen gives $\int f^d\ge(\int f)^d$ for every integer $d\ge1$, so this family satisfies $t(H,W)\ge p^{|E(H)|}$ for every graph $H$, even nonbipartite ones. It follows that restricting a search for a counterexample to rank-one graphons is too narrow. On the other hand, a balanced complete bipartite graphon has $p=1/2$ and triangle density zero. The bipartite hypothesis in the full conjecture is therefore essential; the rank-one calculation does not extend the conjecture to arbitrary graphs.

The failed gluing step.

Suppose two graphs are joined at a distinguished vertex. Integrating all other variables produces rooted densities $a(x),b(x)$, and the joined density is $\int a(x)b(x)\,dx$. Bounds on $\int a$ and $\int b$ alone do not give a bound by their product: two nonnegative functions supported on disjoint half intervals already violate that inference. This functional example is not claimed to realize arbitrary rooted graph densities for a common $W$. It identifies the missing correlation lemma that a gluing proof would need to establish from that structure. Replacing rooted profiles by their averages without such a lemma is not a valid extension of the tree proof.

Verification and remaining target.

The accompanying exact rational checks evaluate small step graphons, including zero degrees and the two-block example, and compare the special graph densities with their proved bounds. They also verify the factorization for rank-one kernels. All integrals in these checks are finite weighted sums. They do not reduce the general conjecture to any fixed partition size or bounded set of graphs.

Final status.

UNRESOLVED. Complete proofs have been given for the specified families, and the equality case for the four-cycle has been checked. The first general gap is a lower bound on the correlations among rooted profiles produced by a bipartite graph with overlapping, unequal neighborhoods. Possible next steps are a justified gluing inequality, a distributional replacement for the tree Markov construction, or a finite-step counterexample search retaining several distinct profile types. No result here covers every bipartite $H$ and every graphon.

Sources

• S1 D. Conlon, J. Lee, A. Sidorenko, 'Biregularity in Sidorenko's Conjecture', arXiv:2108.06599 $2021$. https://arxiv.org/pdf/2108.06599. Formulation source.