In September 2026, OpenAI released a preprint (OpenAI 2026) announcing a counterexample to Sidorenko’s conjecture, a famous problem in extremal graph theory. The conjecture predicted that every bipartite graph appears in any sufficiently large graph at least as frequently as in a random graph with the same edge density, in a precise asymptotic sense.
Let us recall the problem.
A graph consists of a set of vertices, some pairs of which are joined by edges. A graph is called bipartite if its vertices can be divided into two classes so that every edge joins vertices from different classes. For example, every tree is bipartite, and so is every cycle of even length.
Suppose that and are two finite graphs. A graph homomorphism from to is a map between their vertex sets such that whenever two vertices are joined by an edge in , their images are joined by an edge in .
Notice that the map need not be injective: different vertices of may be mapped to the same vertex of , provided that the edge condition is satisfied.
Let denote the number of all such maps. We define the homomorphism density by where denotes the number of vertices of .
This has a simple probabilistic interpretation. Choose independently and uniformly at random a vertex of for every vertex of . Then is the probability that the resulting map preserves all edges.
Similarly, define the edge density where is the set of edges of . This is the probability that two independently and uniformly chosen vertices of are joined by an edge.
Now imagine that is a large random graph in which each possible edge is present independently with probability . If has edges, then one expects Indeed, roughly speaking, each of the edges of must be mapped to an edge of , and these requirements behave independently in a random graph.
Sidorenko (Sidorenko 1993) conjectured that, whenever is bipartite, this random-graph prediction actually gives a lower bound for every graph :
In other words, a random graph was conjectured to minimize the normalized number of homomorphisms of any fixed bipartite graph, among all graphs of the same edge density.
This prediction is quite plausible, and it was proved for many important families of bipartite graphs.
For example, let be the path on three vertices, consisting of two edges. If has vertices, then where denotes the number of neighbours of .
By the Cauchy–Schwarz inequality, Since the sum of all vertex degrees equals twice the number of edges, we obtain This is exactly Sidorenko’s inequality for .
The inequality was also known for all trees, all even cycles, and all complete bipartite graphs. Conlon, Fox, and Sudakov (Conlon et al. 2010) proved it for every bipartite graph containing a vertex adjacent to every vertex in the opposite class. Hatami (Hatami 2010) established further cases using a theory of graph norms, and many additional families were subsequently covered.
These successes suggested that the conjecture might hold for every bipartite graph, regardless of its structure.
However, the new preprint (OpenAI 2026) constructs a counterexample.
Thus, the conjectured inequality fails even for a relatively small bipartite graph .
The graph is constructed explicitly. Start with a collection of points and triples of these points. Create a graph with one vertex for every point and one vertex for every triple, joining a point to a triple exactly when the point belongs to that triple.
Such a graph is called an incidence graph. It is automatically bipartite, because all its edges join points to triples.
The resulting graph has vertices and edges, since every triple contains exactly three points.
The triples are chosen in a very special way. In particular, every pair of points that occurs together in one of the triples occurs together in exactly two triples. This repeated incidence structure plays an essential role in the proof.
The theorem asserts that there exists a graph for which the probability that a random map from to preserves all edges is smaller than the th power of the edge density of .
This contradicts Sidorenko’s conjecture.
Let us briefly discuss the construction. The main challenge is to create a graph whose edge relationships have carefully arranged negative correlations.
When we randomly map the vertices of into , the events that its different edges are preserved are generally not independent. Sidorenko’s conjecture predicted that, for bipartite , their combined probability could never be smaller than the product of their individual probabilities.
The authors construct a weighted model of a graph using matrices over finite fields and certain associated signs. The special arrangement of the triples ensures that some contributions cancel when averaged, while other terms survive and produce a negative correction to the predicted homomorphism density.
The proof then converts this weighted model into an ordinary finite graph by probabilistic sampling, preserving the strict inequality. Thus, the graph is given explicitly, while the required graph is established to exist.
The failure is stronger than merely violating the conjecture by a small amount. The authors show that, for every , there exists a graph such that This follows by taking suitable graph products, which multiply both the homomorphism densities and the corresponding powers of the edge densities.
The same example also disproves a related conjecture about quasirandom graphs. Roughly speaking, a sequence of graphs is quasirandom if its subgraph densities behave like those of random graphs with the same edge probability.
A classical theorem of Chung, Graham, and Wilson (Chung et al. 1989) shows that the correct densities of edges and four-cycles are enough to guarantee quasirandomness. A conjecture associated with Skokan and Thoma predicted that the four-cycle could be replaced by any bipartite graph containing a cycle.
The new counterexample shows that this is false. The authors construct a sequence of non-quasirandom graphs whose edge densities and -homomorphism densities approach exactly the values predicted by a random graph, although their four-cycle densities do not.
Thus, the counterexample reveals a limitation of two related principles: random graphs do not always minimize bipartite homomorphism densities, and the density of an arbitrary bipartite pattern does not always detect quasirandomness.
The result also raises new questions. Which bipartite graphs satisfy Sidorenko’s inequality, and which do not? Are there significantly smaller counterexamples? Can one characterize the graph structures that force the inequality to hold?
The 2026 preprint overturns a conjecture that guided research in extremal graph theory for more than three decades. Its main lesson is that the relationship between randomness and subgraph counting is more subtle than previously expected: even for bipartite graphs, carefully arranged correlations can produce fewer homomorphisms than the random model predicts.