= Sidorenko conjecture
{c}
{wiki}
The <Sidorenko conjecture> is the assertion that every finite <bipartite graph> $H$ satisfies
$$
t(H,G)\geq t(K_2,G)^{|E(H)|}
$$
for every nonempty finite <simple graph> $G$. Here $t(H,G)$ is the <homomorphism density>: the probability that a uniformly random map from $V(H)$ to $V(G)$ sends every edge to an edge. The host graph $G$ need not be bipartite. In the equivalent graphon formulation, the edge constraints are integrated against one symmetric measurable kernel.<Extremal numbers and Sidorenko’s conjecture by David Conlon and others>[Section1, equation1 and its graph specialization]{ref}
For the three-vertex <graph path>, writing $n=|V(G)|$ gives
$$
t(P_3,G)=\frac{\sum_v d(v)^2}{n^3}\geq\left(\frac{\sum_v d(v)}{n^2}\right)^2=t(K_2,G)^2
$$
by the <Cauchy-Schwarz inequality>. The example explains the comparison: correlations between adjacent edge constraints can increase the homomorphism count above the independent-edge heuristic. Bipartiteness is necessary for an assertion covering all hosts, since a nonbipartite $H$ has no homomorphism to a bipartite graph of positive edge density.
Back to article page
