Sidorenko’s conjecture for blow-ups

Sidorenko’s conjecture for blow-ups, Discrete Analysis 2021:2, 13 pp.

Let \(G\) be a bipartite graph with finite vertex sets \(X\) and \(Y\). If \(G\) has density \(\alpha\), then the average degree of the vertices in \(X\) is \(\alpha|Y|\), so the mean-square degree is at least \(\alpha^2|Y|^2\). This is easily seen to be equivalent to the statement that if two vertices \(y_1,y_2\) are selected independently and uniformly at random from \(Y\), then the average number of neighbours they have in common in \(X\) is at least \(\alpha^2|X|\). It follows that the mean-square number of common neighbours is at least \(\alpha^4|X|^2\), and this translates into the statement that if \((x_1,x_2,y_1,y_2)\) is a random element of \(X^2\times Y^2\), then the probability that all four pairs \(x_iy_j\) are edges of \(G\) is at least \(\alpha^4\). This can be interpreted as saying that the 4-cycle density of a graph \(G\) is always at least as large as it would be for a typical random graph of the same density.

The above argument can be straightforwardly generalized from 4-cycles to general complete bipartite graphs \(K_{r,s}\). The famous Sidorenko conjecture (also asked by Erdős and Simonovits) states that the conclusion holds for all bipartite graphs. That is, if \(H\) is a bipartite graph with vertex sets \(U\) and \(V\) of size \(r\) and \(s\), \(G\) is as above, and \(\phi:U\to X\) and \(\psi:V\to Y\) are random functions, then the probability that \(\phi(u)\psi(v)\) is an edge of \(G\) for every \(uv\in E(H)\) is at least \(\alpha^{|E(H)|}\).

One might think that this conjecture would either have a simple counterexample or would follow fairly easily from known inequalities, but this appears not to be the case. A good way to get a feel for the difficulty is to try to prove it for paths of length 3. It is known to be true in this case, but a certain amount of ingenuity is required to prove it.

In fact, it is known to be true for quite a large class of bipartite graphs, with results typically taking the form that a bipartite graph satisfies the conjecture if it can be built up in a certain way from graphs that belong to a particularly simple class. The achievement of this paper is that it proves the conjecture for a class of graphs that cannot be built up in that way. In other words, it obtains a proof that is not just a refinement of existing methods but a genuine extension of the available techniques.

A particular class of graphs for which they obtain a positive result is that of blow-ups. These are bipartite graphs obtained as follows: let \(H\) be a bipartite graph with vertex sets \(A\) and \(B\) and let \(p\) be a positive integer, take \(p\) disjoint copies \(H_1,\dots,H_p\) of \(H\) and identify corresponding vertices that belong to \(A\). (For example, if \(H\) is a single edge, then the blow-up is the complete bipartite graph \(K_{1,p}\) – that is, a star with \(p\) edges.) The authors show that for every bipartite graph \(H\) there is some \(p\) such that the blow-up satisfies Sidorenko’s conjecture.

The rough idea behind the proof is that blow-ups have a property that allows one to replace the graph by a simpler graph to which known techniques apply.

Perhaps the simplest case for which Sidorenko’s conjecture is still unknown is the graph obtained from the complete bipartite graph \(K_{5,5}\) by removing a 10-cycle. While the authors do not resolve this question, their result does imply that the “square” of this graph (that is, the blow-up when \(p=2\)) satisfies the conjecture. Another consequence of their results is that for every bipartite graph \(H\) there is a bipartite graph \(H'\) such that the disjoint union of \(H\) and \(H'\) satisfies the conjecture.

So is Sidorenko’s conjecture true? The experts on the problem are reluctant to take a strong view either way. The results proved so far place significant restrictions on what a counterexample could be like (though these leave open relatively small possibilities such as the \(K_{5,5}\setminus C_{10}\) example), which perhaps points in the positive direction. On the other hand, a natural analogue of the conjecture for 3-uniform hypergraphs, which places a restriction on what a proof could be like – it cannot be too generalizable.

This paper is a valuable addition to our understanding of a tantalizing question.