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.