Sidorenko's conjecture


Sidorenko's conjecture is an important conjecture in the field of graph theory, posed by Alexander Sidorenko in 1986. Roughly speaking, the conjecture states that for any bipartite graph and graph on vertices with average degree, there are at least labeled copies of in, up to a small error term. Formally, it provides an intuitive inequality about graph homomorphism densities in graphons. The conjectured inequality can be interpreted as a statement that the density of copies of in a graph is asymptotically minimized by a random graph, as one would expect a fraction of possible subgraphs to be a copy of if each edge exists with probability.

Statement

Let be a graph. Then is said to have Sidorenko's property if, for all graphons, the inequality
is true, where is the homomorphism density of in.
Sidorenko's conjecture states that every bipartite graph has Sidorenko's property.
If is a graph, this means that the probability of a uniform random mapping from to being a homomorphism is at least the product over each edge in of the probability of that edge being mapped to an edge in. This roughly means that a randomly chosen graph with fixed number of vertices and average degree has the minimum number of labeled copies of. This is not a surprising conjecture because the right hand side of the inequality is the probability of the mapping being a homomorphism if each edge map is independent. So one should expect the two sides to be at least of the same order. The natural extension to graphons would follow from the fact that every graphon is the limit point of some sequence of graphs.
The requirement that is bipartite to have Sidorenko's property is necessary — if is a bipartite graph, then since is triangle-free. But is twice the number of edges in, so Sidorenko's property does not hold for. A similar argument shows that no graph with an odd cycle has Sidorenko's property. Since a graph is bipartite if and only if it has no odd cycles, this implies that the only possible graphs that can have Sidorenko's property are bipartite graphs.

Equivalent formulation

Sidorenko's property is equivalent to the following reformulation:
This is equivalent because the number of homomorphisms from to is twice the number of edges in, and the inequality only needs to be checked when is a graph as previously mentioned.
In this formulation, since the number of non-injective homomorphisms from to is at most a constant times, Sidorenko's property would imply that there are at least labeled copies of in.

Examples

As previously noted, to prove Sidorenko's property it suffices to demonstrate the inequality for all graphs. Throughout this section, is a graph on vertices with average degree. The quantity refers to the number of homomorphisms from to. This quantity is the same as.
Elementary proofs of Sidorenko's property for some graphs follow from the Cauchy–Schwarz inequality or Hölder's inequality. Others can be done by using spectral graph theory, especially noting the observation that the number of closed paths of length from vertex to vertex in is the component in the th row and th column of the matrix, where is the adjacency matrix of.

Cauchy–Schwarz: The 4-cycle ''C''4

By fixing two vertices and of, each copy of that have and on opposite ends can be identified by choosing two common neighbors of and. Letting denote the codegree of and , this implies
by the Cauchy–Schwarz inequality. The sum has now become a count of all pairs of vertices and their common neighbors, which is the same as the count of all vertices and pairs of their neighbors. So
by Cauchy–Schwarz again. So
as desired.

Spectral graph theory: The 2''k''-cycle ''C''2''k''

Although the Cauchy–Schwarz approach for is elegant and elementary, it does not immediately generalize to all even cycles. However, one can apply spectral graph theory to prove that all even cycles have Sidorenko's property. Note that odd cycles are not accounted for in Sidorenko's conjecture because they are not bipartite.
Using the observation about closed paths, it follows that is the sum of the diagonal entries in. This is equal to the trace of, which in turn is equal to the sum of the th powers of the eigenvalues of. If are the eigenvalues of, then the min-max theorem implies that
where is the vector with components, all of which are. But then
because the eigenvalues of a real symmetric matrix are real. So
as desired.

Entropy: Paths of length 3

J.L. Xiang Li and Balázs Szegedy introduced the idea of using entropy to prove some cases of Sidorenko's conjecture. Szegedy later applied the ideas further to prove that an even wider class of bipartite graphs have Sidorenko's property. While Szegedy's proof wound up being abstract and technical, Tim Gowers and Jason Long reduced the argument to a simpler one for specific cases such as paths of length. In essence, the proof chooses a nice probability distribution of choosing the vertices in the path and applies Jensen's inequality to deduce the inequality.

Partial results

Here is a list of some bipartite graphs which have been shown to have Sidorenko's property. Let have bipartition.
However, there are graphs for which Sidorenko's conjecture is still open. An example is the "Möbius strip" graph, formed by removing a -cycle from the complete bipartite graph with parts of size.
László Lovász proved a local version of Sidorenko's conjecture, i.e. for graphs that are "close" to random graphs in a sense of cut norm.

Forcing conjecture

A sequence of graphs is called quasi-random with density for some density if for every graph,
The sequence of graphs would thus have properties of the Erdős–Rényi random graph.
If the edge density is fixed at, then the condition implies that the sequence of graphs is near the equality case in Sidorenko's property for every graph.
From Chung, Graham, and Wilson's 1989 paper about quasi-random graphs, it suffices for the count to match what would be expected of a random graph. The paper also asks which graphs have this property besides. Such graphs are called forcing graphs as their count controls the quasi-randomness of a sequence of graphs.
The forcing conjecture states the following:
It is straightforward to see that if is forcing, then it is bipartite and not a tree. Some examples of forcing graphs are even cycles. Skokan and Thoma showed that all complete bipartite graphs that are not trees are forcing.
Sidorenko's conjecture follows from the forcing conjecture. Furthermore, the forcing conjecture would show that graphs that are close to equality in Sidorenko's property must satisfy quasi-randomness conditions.