Homomorphism densities and Sidorenko counterexamples

Source and verification

This article explains family 161 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Homomorphism densities

A graph homomorphism from $H$ to a finite simple graph $G$ maps vertices to vertices and edges to edges. Distinct vertices of $H$ may have the same image. With $v(H)$ and $e(H)$ denoting the numbers of vertices and edges, define

$$t(H,G)=\frac{\mathrm{Hom}(H,G)}{|V(G){|}^{v(H)}}.$$

The edge density in this convention is $p=t(K_2,G)=2e(G)/|V(G){|}^2$. Sidorenko’s conjecture proposes $t(H,G)\ge p^{e(H)}$ for every bipartite $H$ and every finite host $G$.

For a simple example, let $H$ be a path with two edges. If $n=|V(G)|$ and $d_G(x)$ is the degree of $x$, then

$$t(H,G)=\frac{1}{n}\sum _x{\left(\frac{d_G(x)}{n}\right)}^2\ge p^2$$

by the nonnegativity of variance. This illustrates why the conjecture is plausible: averaging over shared endpoints can increase, rather than decrease, the expected number of copies.

Manuscript claim

There is a bipartite graph $H$ with 35 vertices and 66 edges, and a finite simple graph $G$ of positive edge density $p$, such that $t(H,G)<p^{66}$. The manuscript also derives a counterexample to the forcing conjecture. (OpenAI, 2026)

The count is a homomorphism count, not an injective-copy count. Replacing one by the other in a finite graph changes the assertion.

🏷️ The incidence graph and local cancellation

The graph $H$ is the incidence graph of a system of 22 triples on 13 points. One side of the bipartition consists of the points, the other of the triples, and incidence gives the edges. Thus there are $13+22=35$ vertices and $3\cdot 22=66$ edges. The underlying 33 point-pairs each occur in two triples.

The construction first uses weighted kernels. A symmetric measurable kernel $W:[0,1{]}^2\to [0,1]$, called a graphon, has density

$$\begin{array}{c}t(H,W)\\ ={\int }_{[0,1{]}^{V(H)}}\prod _{uv\in E(H)}W(x_u,x_v)dx.\end{array}$$

Finite weighted models have the same formula with normalized sums. Strict inequality for a suitable kernel can be transferred to a finite simple graph by sampling, because a positive gap survives sufficiently accurate approximation.

The local model uses signs and an auxiliary random sign shared by two incidences. Averaging over that auxiliary sign removes the terms that are linear in it but preserves a product of the two incidence signs. Schematically,

$${\mathbb{E}}_{\eta }[(1+a\eta )(1+b\eta )]=1+ab$$

when $\eta$ is uniformly distributed on $\{-1,1\}$. This elementary identity is the source of an interaction that is invisible in the individual edge averages. The triple system makes these surviving interactions fit together globally.

🏷️ Controlling all assignments

The source realizes the signs through finite-field matrix data. Nonsingular differences between point parameters make the required auxiliary signs asymptotically independent. A weighted refinement of vertex types then identifies the assignments giving the desired negative contribution.

Two difficulties need explicit treatment. First, homomorphisms include repeated vertices and repeated types, so the analysis cannot be restricted to generic injective assignments. Second, the exceptional singular matrix differences have small probability but can carry large weights. A small exceptional probability alone does not prove that their contribution is negligible. The manuscript controls them through a separate analysis of intersection profiles.

The two sides of the incidence graph have different sizes. Introducing a small parameter $\epsilon$ for an inactive point type makes the favorable term appear at order ${\epsilon }^{13}$, while a reversed contribution appears at order ${\epsilon }^{22}$. This separation lets the former dominate for small $\epsilon$. A transpose construction symmetrizes the initially asymmetric kernel, after which normalization and sampling produce the claimed simple host graph.

The proof mechanism is therefore not merely a random search for a sparse-copy graph. It engineers a signed interaction, controls every competing assignment, and preserves a strict deficit through symmetrization and discretization.

🏷️ Amplification and the forcing consequence

Tensor products multiply homomorphism densities. If a kernel has ratio

$$\rho =\frac{t(H,W)}{t(K_2,W{)}^{66}}<1,$$

then its $m$-fold tensor power has ratio ${\rho }^m\to 0$. The edge density also changes with $m$; this amplification should not be described as maintaining one fixed density.

The forcing conjecture asks whether equality with the random-graph prediction, for appropriate bipartite graphs containing a cycle, forces the host to be quasirandom. In graphon language the relevant conclusion is that $W$ is almost everywhere constant. The manuscript interpolates between examples to obtain a nonconstant $W$ with

$$t(H,W)=p^{66},t(K_2,W)=p,$$

while its four-cycle density exceeds $p^4$. This supplies an equality case that is still detectably nonrandom. The construction is at a suitable density; it does not assert such an example at every prescribed $p$.

The finite incidence system is explicit in the source, but the large host construction and all its analytic estimates have not been independently certified here.

🏷️ Key steps and proof outlines

Isolate one negative coefficient before taking limits

The kernel construction first obtains an oriented density with a negative nonconstant coefficient. Its finite set of competitors has scores $\mathcal{Q}(a,b)$, while the desired term has strictly larger score $Q_{\ast }$. If

$${\delta }_{\ast }=\underset{(a,b)\ne (\mathrm{id},\mathrm{id})}{\min }(Q_{\ast }-\mathcal{Q}(a,b))>0,$$

and $B_{\ast }$ is the sum of the absolute competitor coefficients, multiplying each term by $e^{\rho \mathcal{Q}(a,b)}$ makes their total, after division by $e^{\rho Q_{\ast }}$, at most $B_{\ast }{e}^{-\rho {\delta }_{\ast }}$. Choose a finite $\rho$ large enough that this is smaller than the magnitude of the designated negative term. The resulting coefficient $t_0$ is strictly negative. This is the output supplied to the final part of “Kernel construction”; the earlier rank-layer analysis is what justifies that coefficient expansion. (OpenAI, 2026)

Dilution prevents the opposite orientation from undoing the sign

The bipartition of $H$ has sizes $13$ and $22$. Add an inactive type to the first side, giving all active types total probability $\epsilon$. Every vertex has positive degree, so a nonempty term vanishes whenever any required active-type draw is inactive. The two orientations therefore have limits

$$\begin{array}{rl}{t}_{I,J}(W_{q,\epsilon })& =1+{\epsilon }^{13}{t}_0+o(1),\\ t_{I,J}(W_{q,\epsilon }^{\mathsf{T}})& =1+{\epsilon }^{22}{t}_1+o(1).\end{array}$$

Here $t_1$ is finite but need not have a known sign; the errors vanish as the auxiliary prime $q$ grows after $\epsilon$ is fixed. Their limiting product is

$$1+{\epsilon }^{13}(t_0+{\epsilon }^9{t}_1+{\epsilon }^{22}{t}_0{t}_1)<1$$

for sufficiently small positive $\epsilon$. The unequal bipartition sizes make the unwanted orientation higher order. Choosing $q$ only afterward preserves this strict gap.

Symmetrization with an exact density identity

On the product probability space, set $V((x,y),(x^{\prime },y^{\prime }))=W(x,y^{\prime })W(x^{\prime },y)$. The kernel is symmetric and has mean one. Independence of the two coordinate collections gives $t(H,V)=t_{I,J}(W)t_{I,J}(W^{\mathsf{T}})<1$.

Finally let $L=\max V$ and $U=V/L$. Then $0\le U\le 1$, its mean is $\mu =1/L>0$, and homogeneity in the $66$ edges gives $t(H,U)<{\mu }^{66}$. This turns the oriented analytic construction into an ordinary symmetric graph kernel without losing the normalized deficit.

A strict kernel gap survives finite sampling

Write $\tau =t(H,U)$ and $\Delta ={\mu }^{66}-\tau >0$. Sample $n$ independent kernel labels and draw each unordered edge independently conditional on those labels. The expected edge density, normalized by $n^2$, is $(1-1/n)\mu$.

An injective map of the $35$ vertices of $H$ has homomorphism probability exactly $\tau$. The proportion of maps identifying some two vertices is at most $\left(\genfrac{}{}{0ex}{}{35}{2}\right)/n=595/n$. Bounding each such indicator between zero and one gives

$$\left|\mathbb{E}t(H,G_n)-\tau \right|\le 595/n.$$

This argument retains all homomorphisms; it does not quietly replace them by injective copies. Choose

$$n>\frac{595+66{\mu }^{66}}{\Delta }.$$

Bernoulli’s inequality and convexity then imply

$$\begin{array}{rl}\mathbb{E}t(H,G_n)& <((1-1/n)\mu {)}^{66}\\ & =(\mathbb{E}p(G_n){)}^{66}\le \mathbb{E}[p(G_n{)}^{66}].\end{array}$$

Some realization therefore violates Sidorenko’s inequality. No concentration theorem is needed for this existence step.

Why the same example also obstructs forcing

The “Consequences” section interpolates the deficient kernel with $W_1(a,b)=p+\delta ab$, where $a,b$ are independent uniform signs, $0<\delta \le \min (p,1-p)$, and $p$ is the fixed edge density. Expanding the product over $H$ leaves only even-degree edge subsets. Every surviving term is nonnegative, and a cycle gives a strictly positive nonempty term, so $t(H,W_1)>p^{66}$.

Place the two kernels on independent coordinates and interpolate. Edge density stays $p$, whereas $t(H,\cdot )$ is continuous and crosses $p^{66}$. The variance is a sum of two nonnegative independent-coordinate contributions, positive throughout the interpolation, so the crossing kernel is nonconstant. For a finite kernel, equality $t(C_4,W)=p^4$ in the two Cauchy–Schwarz steps would force every row to be constant. Thus this nonconstant crossing retains excess $C_4$ density and is not quasirandom. The rank-layer theorem remains the research input behind the initial negative coefficient; the steps above explain how its output yields both conclusions.

See Also

• Ryser covering counterexamples also encodes a hypergraph through incidences, but studies covers and matchings rather than homomorphism densities.
• Coloring and clique minors uses dependent random constructions to suppress another family of graph configurations.

🏷️ Manuscripts and verification scope

• A counterexample to Sidorenko’s conjecture — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects the finite simple-graph density counterexample for the specified 35-vertex graph. The separate forcing-conjecture consequence is outside that statement. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. A counterexample to Sidorenko’s conjecture.