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 H {\displaystyle H} and graph G {\displaystyle G} on n {\displaystyle n} vertices with average degree p n {\displaystyle pn} , there are at least p | E ( H ) | n | V ( H ) | {\displaystyle p^{|E(H)|}n^{|V(H)|}} labeled copies of H {\displaystyle H} in G {\displaystyle G} , 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 H {\displaystyle H} in a graph is asymptotically minimized by a random graph, as one would expect a p | E ( H ) | {\displaystyle p^{|E(H)|}} fraction of possible subgraphs to be a copy of H {\displaystyle H} if each edge exists with probability p {\displaystyle p} .
Statement Let H {\displaystyle H} be a graph. Then H {\displaystyle H} is said to have Sidorenko's property if, for all graphons W {\displaystyle W} , the inequality
t ( H , W ) ≥ t ( K 2 , W ) | E ( H ) | {\displaystyle t(H,W)\geq t(K_{2},W)^{|E(H)|}}
is true, where t ( H , W ) {\displaystyle t(H,W)} is the homomorphism density of H {\displaystyle H} in W {\displaystyle W} . Sidorenko's conjecture (1986) states that every bipartite graph has Sidorenko's property. If W {\displaystyle W} is a graph G {\displaystyle G} , this means that the probability of a uniform random mapping from V ( H ) {\displaystyle V(H)} to V ( G ) {\displaystyle V(G)} being a homomorphism is at least the product over each edge in H {\displaystyle H} of the probability of that edge being mapped to an edge in G {\displaystyle G} . This roughly means that a randomly chosen graph with fixed number of vertices and average degree has the minimum number of labeled copies of H {\displaystyle H} . 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 H {\displaystyle H} is bipartite to have Sidorenko's property is necessary — if W {\displaystyle W} is a bipartite graph, then t ( K 3 , W ) = 0 {\displaystyle t(K_{3},W)=0} since W {\displaystyle W} is triangle-free. But t ( K 2 , W ) {\displaystyle t(K_{2},W)} is twice the number of edges in W {\displaystyle W} , so Sidorenko's property does not hold for K 3 {\displaystyle K_{3}} . 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:
… excerpt ends here. Continue reading the full article.
