Sidorenko's conjecture is a major conjecture in the field of extremal graph theory, posed by Alexander Sidorenko in 1986.
Roughly speaking, the conjecture states that for any bipartite graph
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
, this means that the probability of a uniform random mapping from
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.
The natural extension to graphons would follow from the fact that every graphon is the limit point of some sequence of graphs.
A similar argument shows that no graph with an odd cycle has Sidorenko's property.
In this formulation, since the number of non-injective homomorphisms from
As previously noted, to prove Sidorenko's property it suffices to demonstrate the inequality for all graphs
Others can be done by using spectral graph theory, especially noting the observation that the number of closed paths of length
on opposite ends can be identified by choosing two (not necessarily distinct) common neighbors of
(i.e. the number of common neighbors), 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.
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.
Xiang Li and Balázs Szegedy (2011) introduced the idea of using entropy to prove some cases of Sidorenko's conjecture.
Szegedy (2015) later applied the ideas further to prove that an even wider class of bipartite graphs have Sidorenko's property.
[2] 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
[3] In essence, the proof chooses a nice probability distribution of choosing the vertices in the path and applies Jensen's inequality (i.e. convexity) to deduce the inequality.
-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.
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 (i.e. the condition holds for
The forcing conjecture states the following: It is straightforward to see that if
Some examples of forcing graphs are even cycles (shown by Chung, Graham, and Wilson).
Skokan and Thoma showed that all complete bipartite graphs that are not trees are forcing.
Furthermore, the forcing conjecture would show that graphs that are close to equality in Sidorenko's property must satisfy quasi-randomness conditions.