Sidorenko’s conjecture for blow-ups
- The Division of Physics, Mathematics and Astronomy, Caltech
- More about David Conlon
- Department of Mathematics, University College London
- More about Joonkyung Lee
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 α, then the average degree of the vertices in X is α|Y|, so the mean-square degree is at least α2|Y|2. This is easily seen to be equivalent to the statement that if two vertices y1,y2 are selected independently and uniformly at random from Y, then the average number of neighbours they have in common in X is at least α2|X|. It follows that the mean-square number of common neighbours is at least α4|X|2, and this translates into the statement that if (x1,x2,y1,y2) is a random element of X2×Y2, then the probability that all four pairs xiyj are edges of G is at least α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 Kr,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 ϕ:U→X and ψ:V→Y are random functions, then the probability that ϕ(u)ψ(v) is an edge of G for every uv∈E(H) is at least α|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 H1,…,Hp 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 K1,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 K5,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 K5,5∖C10 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.