Sidorenko's conjecture

Sidorenko's property is equivalent to the following reformulation:

For all graphs ${\displaystyle G}$, if ${\displaystyle G}$ has ${\displaystyle n}$ vertices and an average degree of ${\displaystyle pn}$, then ${\displaystyle t(H,G)\geq p^{|E(H)|}}$.

This is equivalent because the number of homomorphisms from ${\displaystyle K_{2}}$ to ${\displaystyle G}$ is twice the number of edges in ${\displaystyle G}$, and the inequality only needs to be checked when ${\displaystyle W}$ is a graph as previously mentioned.

In this formulation, since the number of non-injective homomorphisms from ${\displaystyle H}$ to ${\displaystyle G}$ is at most a constant times ${\displaystyle n^{|V(H)|-1}}$, Sidorenko's property would imply that there are at least ${\displaystyle (p^{|E(H)|}-o(1))n^{|V(H)|}}$ labeled copies of ${\displaystyle H}$ in ${\displaystyle G}$.

By fixing two vertices ${\displaystyle u}$ and ${\displaystyle v}$ of ${\displaystyle G}$, each copy of ${\displaystyle C_{4}}$ that have ${\displaystyle u}$ and ${\displaystyle v}$ on opposite ends can be identified by choosing two (not necessarily distinct) common neighbors of ${\displaystyle u}$ and ${\displaystyle v}$. Letting ${\displaystyle \operatorname {codeg} (u,v)}$ denote the codegree of ${\displaystyle u}$ and ${\displaystyle v}$ (i.e. the number of common neighbors), this implies

${\displaystyle \operatorname {hom} (C_{4},G)=\sum _{u,v\in V(G)}\operatorname {codeg} (u,v)^{2}\geq {\frac {1}{n^{2}}}\left(\sum _{u,v\in V(G)}\operatorname {codeg} (u,v)\right)^{2}}$

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

${\displaystyle \operatorname {hom} (C_{4},G)\geq {\frac {1}{n^{2}}}\left(\sum _{x\in V(G)}\deg(x)^{2}\right)^{2}\geq {\frac {1}{n^{2}}}\left({\frac {1}{n}}\left(\sum _{x\in V(G)}\deg(x)\right)^{2}\right)^{2}={\frac {1}{n^{2}}}\left({\frac {1}{n}}(n\cdot pn)^{2}\right)^{2}=p^{4}n^{4}}$

by Cauchy–Schwarz again. So

${\displaystyle t(C_{4},G)={\frac {\operatorname {hom} (C_{4},G)}{n^{4}}}\geq p^{4}}$

as desired.

Although the Cauchy–Schwarz approach for ${\displaystyle C_{4}}$ 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 ${\displaystyle \operatorname {hom} (C_{2k},G)}$ is the sum of the diagonal entries in ${\displaystyle A^{2k}}$. This is equal to the trace of ${\displaystyle A^{2k}}$, which in turn is equal to the sum of the ${\displaystyle 2k}$th powers of the eigenvalues of ${\displaystyle A}$. If ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \dots \geq \lambda _{n}}$ are the eigenvalues of ${\displaystyle A}$, then the min-max theorem implies that

${\displaystyle \lambda _{1}\geq {\frac {\mathbf {1} ^{\intercal }A\mathbf {1} }{\mathbf {1} ^{\intercal }\mathbf {1} }}={\frac {1}{n}}\sum _{x\in V(G)}\deg(x)=pn,}$

where ${\displaystyle \mathbf {1} }$ is the vector with ${\displaystyle n}$ components, all of which are ${\displaystyle 1}$. But then

${\displaystyle \operatorname {hom} (C_{2k},G)=\sum _{i=1}^{n}\lambda _{i}^{2k}\geq \lambda _{1}^{2k}\geq p^{2k}n^{2k}}$

because the eigenvalues of a real symmetric matrix are real. So

${\displaystyle t(C_{2k},G)={\frac {\operatorname {hom} (C_{2k},G)}{n^{2k}}}\geq p^{2k}}$

as desired.

J.L. 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 ${\displaystyle 3}$.[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.