When a bipartite pattern is rarer than the random-graph benchmark

← All digests

Family 161 · Combinatorics
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

A graph with many edges must contain many small patterns. But which arrangement of the edges minimizes the number of copies of a specified pattern? Sidorenko’s conjecture predicts a remarkably broad answer for bipartite patterns: distributing edges as if independently at random gives the minimum benchmark.

The manuscript in family 161 claims a counterexample. Its pattern is a connected bipartite graph with 35 vertices and 66 edges. In a suitable host graph, this pattern occurs less frequently than the conjectured bound.

The same pattern also challenges a second idea. Matching a random graph’s edge density and the density of one suitably chosen bipartite pattern was conjectured to force random-like behavior more generally. The manuscript claims a nonrandom example matching those two quantities exactly in the graph-limit formulation.

These are related but different conclusions: one falls below a proposed minimum, while the other matches a benchmark without having the predicted structure.

2. Background and essential definitions

A bipartite graph has its vertices divided into two parts, with every edge joining the parts. Trees, even cycles and complete bipartite graphs are examples. An odd cycle is not bipartite.

For a pattern $H$ and a host $G$, a graph homomorphism sends vertices of $H$ to vertices of $G$ and preserves edges. Different pattern vertices may have the same image, provided this does not violate an edge requirement. Nonedges need not be preserved.

The homomorphism density is

$$t(H,G)=\frac{\operatorname{hom}(H,G)}{|V(G)|^{|V(H)|}}.$$

It is the probability that independently chosen images of the pattern vertices preserve all its edges. The corresponding edge density is

$$p(G)=t(K_2,G)=\frac{2|E(G)|}{|V(G)|^2}.$$

This uses ordered vertex pairs and allows choosing the same vertex twice. It differs slightly from $|E(G)|/\binom{|V(G)|}{2}$, the usual fraction of available distinct-vertex edges. Their difference tends to zero as the host size grows, but exact finite statements must retain the correct convention.

If $H$ has $e$ edges, the constant random benchmark is $p^e$. Sidorenko’s inequality is

$$t(H,G)\ge p(G)^e$$

for every bipartite $H$ and every nonempty finite host.

Graphons and quasirandomness

A graphon is a symmetric measurable function $W(x,y)\in[0,1]$, interpreted as an edge probability between vertex types. Choose independent types for all vertices, then insert edges with the indicated probabilities. The constant graphon $W=p$ models uniformly random edges.

Its pattern density is the expectation of the product of $W$ over the pattern’s edges. A graph sequence is quasirandom at density $p$ if every fixed pattern has limiting density $p^{|E(H)|}$. The forcing question asks when knowing just the edge density and one additional pattern density already implies all those conclusions.

3. Development history and previous partial results

Sidorenko’s conjecture belongs to the study of supersaturation: counting unavoidable patterns once a graph has many edges. Simonovits developed this viewpoint in extremal graph theory, and Sidorenko formulated the corresponding kernel inequalities in the early 1990s. His original functional formulation is available in the 1992 English translation.

Many substantial positive cases accumulated. Trees, even cycles and complete bipartite graphs satisfy the proposed inequality. Conlon, Fox and Sudakov proved it for bipartite graphs having a vertex adjacent to the entire opposite part, and obtained related approximation and stability results.

Another approach turns pattern densities into analytic norms. Hatami’s graph-norm work proves strong inequalities for suitable patterns, including hypercubes. Reflection constructions, entropy methods and structured gluing arguments subsequently supplied further classes. These results explain why the conjecture seemed compatible with many different sources of combinatorial structure.

Quasirandomness developed alongside this counting theory. Chung, Graham and Wilson showed that the edge and four-cycle densities characterize random-like behavior. Skokan and Thoma studied which other bipartite patterns could replace the four-cycle. The resulting forcing conjecture proposed precisely the bipartite graphs containing a cycle.

The new manuscript uses a pattern outside the positive classes it compares against. Its two parts have sizes 13 and 22; the latter part has degree three, while the first has varying degrees. The source does not treat failure of a known sufficient condition as a counterexample by itself. Its separate kernel construction supplies the claimed strict density deficit.

4. What the new manuscripts claim

M1 explicitly lists 22 triples on a set of 13 points. Its pattern $H$ is the incidence graph: one part represents points, the other represents triples, and a point is adjacent to a triple when it belongs to that triple. Therefore $H$ has 35 vertices and $3\times22=66$ edges.

Theorem 1.1 asserts a finite simple graph $G$ with at least one edge such that

$$t(H,G)<p(G)^{66}.$$

All homomorphisms are counted, including maps with repeated images. This is a counterexample to the ordinary formulation, not merely to an injective-copy variant.

Corollary 1.2 amplifies the deficit: for every $c>0$, some finite host $F$ satisfies $t(H,F)<c\,p(F)^{66}$. The host density may vary with $c$. Separately, the source obtains a sequence at one positive limiting density with a fixed proportional deficit in injective labeled copies.

Corollary 1.3 gives a fixed $p\in(0,1)$ and a nonconstant graphon $W$ with

$$t(K_2,W)=p, \qquad t(H,W)=p^{66}, \qquad t(C_4,W)>p^4.$$

The four-cycle discrepancy shows that matching the first two quantities does not force quasirandomness. Sampling produces corresponding finite graph sequences. This failure occurs at one density, which is enough to refute the assertion that the pattern forces quasirandomness at every density.

5. Why the advance matters

Importance: 5/5. Sidorenko’s conjecture is a central organizing prediction about bipartite graph counts. A counterexample would change the scope of a principle supported by many powerful and apparently diverse positive methods.

The forcing consequence adds a second conceptual impact. A pattern can have exactly its random benchmark density while still missing substantial information about the host. The claimed example would show that bipartiteness plus the presence of a cycle is insufficient to make one pattern a universal randomness test.

The rating does not suggest that earlier positive theorems disappear. They remain meaningful classifications of patterns with stronger counting behavior. The new task would be to understand which structural features separate those classes from the claimed counterexample.

6. The main idea

Design a negative correlation

The 22 triples form a finite combinatorial complex in which each of 33 selected point pairs belongs to exactly two triples. This double occurrence permits a sign correlation involving four incidences.

An elementary schematic identity explains the mechanism. If $\eta$ is an equally likely sign and $a,b$ are signs, then

$$\mathbb E_\eta[(1+\eta a)(1+\eta b)]=1+ab.$$

Linear sign terms disappear under averaging, while the joint term remains. The manuscript arranges many such interactions so that most unwanted contributions cancel and one surviving combined contribution is negative.

The actual edge kernel must be nonnegative, so a freely chosen negative signed expression would not suffice. M1 realizes the needed sign behavior using rank and determinant data of symmetric matrices over a finite field. Prescribed half-rank differences impose compatibility between the signs. This is where finite-field linear algebra enters a problem stated entirely in terms of graphs.

Make the intended pattern dominate

Vertices carry types identifying the point or triple they are meant to represent. Additional weights favor the intended type assignment over other homomorphisms, including those with repeated images. Coordinate choices cancel simple sign biases while retaining the higher-order overlap responsible for the deficit.

A rectangular kernel initially distinguishes the two bipartition sides. The source then combines it with its transpose to obtain a symmetric kernel suitable for ordinary graphs. Different small-parameter orders control the two orientations before this symmetrization.

Rare singular matrix configurations require separate estimates because their weights can be large. The manuscript uses the geometry of subspaces to bound their total weighted contribution. A small probability alone would not control a potentially large weighted error.

Return to finite graphs and exact equality

After obtaining a strict kernel deficit, the source rescales to values in $[0,1]$ and samples a finite simple graph. The strict margin lets the inequality survive the sampling approximation.

Tensor products multiply normalized deficits, producing arbitrarily small ratios when the host density is allowed to vary. Balanced blow-ups instead preserve a fixed deficit along growing graph orders at one limiting density.

Finally, interpolation between kernels of the same mean yields the exact equality $t(H,W)=p^{66}$ needed for the forcing counterexample. The construction still has excess four-cycles. Thus equality for this one pattern does not erase its underlying structure.

7. Scope, limitations, and open questions

The pattern is explicitly specified and modest in size, but the theorem does not give a smallest counterexample pattern or a small optimized host graph. The finite host is obtained through the construction and sampling argument.

The arbitrarily small normalized ratio allows the density to change. It should not be restated as an arbitrarily severe deficit at every prescribed positive density. Likewise, the forcing failure is demonstrated at one density, not uniformly at all densities.

Local positive results near constant kernels remain compatible with the claim. A counterexample outside a neighborhood of the constant graphon does not disprove inequalities known within that neighborhood.

The major remaining structural question is which bipartite patterns satisfy Sidorenko’s inequality or force quasirandomness. The source provides a negative instance, not a full classification. It also leaves open how small and geometrically simple a counterexample can be.

8. Sources and further reading

M1’s Theorem 1.1 and Corollaries 1.2–1.3 state the finite-graph, amplification and forcing conclusions. Table 1 gives the triple system. Sections 3–7 construct and control the kernel, while Section 8 passes to ordinary graphs and the equality example.

The primary sources linked in Section 3 explain the original inequality and two major families of positive results. Wikipedia’s graphon page is optional background for the continuous model; the finite counting conventions needed here are given explicitly above.

Source manuscripts

• M1. OpenAI, A counterexample to Sidorenko’s conjecture (September 23, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.