Counterexamples to Sidorenko’s conjecture and the forcing conjecture

The explanation

Draw a square: four corners, four sides. Call it the pattern. Now take a tiny host graph, a path of three dots a, b, c joined by two lines. Send each corner of the square to a dot, repeats allowed. The map counts if every side of the square lands on a line of the path. Out of 3⁴ = 81 maps, exactly 8 count. So the square's density in the path is 8/81, about 0.099.

Compare that with a random graph. The path links 4 of its 9 ordered pairs of dots, so its edge density is 4/9. In a random graph with that density, each side of the square is present with chance 4/9. All four together give (4/9)⁴ = 256/6561, about 0.039. The path holds about 2.5 times more squares than this random benchmark.

Here a map like this is called a homomorphism. Its share among all maps is the homomorphism density. A graph is bipartite when its dots split into two sides and every line crosses between them. The square is bipartite. Sidorenko's conjecture says a bipartite pattern never does worse than random. For every host graph, its density should be at least the edge density raised to the number of pattern lines. The bipartite condition matters. A triangle is not bipartite, and the four-dot graph with two dots on each side holds no triangles. Its edge density is 1/2, so random would predict (1/2)³ = 1/8.

The question grew out of a classical theme. Once a host has many lines, how many copies of a fixed bipartite pattern must it contain? Sidorenko formulated the inequalities in papers from 1991 and 1993. Trees, even cycles and complete bipartite graphs were basic positive cases. Conlon, Fox and Sudakov proved it in 2010 when one dot touches the whole other side. Hatami's 2010 graph-norm method covered the hypercube and other highly structured patterns. Many later papers added classes by gluing, entropy, tree decompositions and degree counts.

This paper proves the conjecture falseSource 1. Its pattern starts from 13 points and 22 chosen triples of themSource 2. The pattern has one dot per point and one per triple. A point joins each triple that contains it. That gives 35 dots and 66 lines. Each of the 33 point pairs used sits in exactly two triplesSource 3. The paper shows some finite host graph has fewer copies of this pattern than the random benchmark predictsSource 4.

The obstacle is that random is very hard to beat. Lovász had shown that hosts close enough to random always obey the inequality. Known proofs also covered most patterns with clean structure. This pattern was chosen to dodge those toolsSource 5,Source 6. No dot touches the whole other side, its degrees are uneven, and every dot has at least three lines. The paper builds a weighted host from matrices of numbers modulo a large primeSource 7. Each point pair gets a random sign, and each point-triple link gets a sign too. Because each point pair lies in two triples, the pair's random sign averages out. What survives is a link between four signs, two from each triple. The construction makes that link tilt the count below randomSource 8. A random sampling step then turns the weighted host into an ordinary graph.

So the square's comfortable margin over random does not hold for every bipartite pattern. Taking repeated products of the host even pushes the ratio below any fixed fraction, for this patternSource 9. The host graph is not written down, though. The paper proves it exists and does not state its sizeSource 4.

The same pattern also breaks a second conjecture. A sequence of graphs is quasirandom when every small pattern appears at its random rate. In 1989 Chung, Graham and Wilson showed that matching random on lines and squares forces this. Skokan and Thoma asked which bipartite patterns can replace the square. Conlon, Fox and Sudakov conjectured an answer: a pattern can, exactly when it is bipartite and contains a cycle. The paper claims to prove this fails at one density. It builds graphs whose line and pattern densities approach random rates. Yet their square density stays above randomSource 10. It does not claim failure at every densitySource 11.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. That statement fixes the 35-dot, 66-line pattern and gives a finite simple host graph with too few copies. The forcing consequence is outside that check. No specialist review of the paper has been published.

What it doesn't show. This does not give the host graph explicitly or say which other bipartite patterns fail.