Sidorenko conjecture

The Sidorenko conjecture states that every bipartite graph $H$ satisfiesfor every bipartite host graph $G$. Thus a random map is at least as likely to preserve every edge as the heuristic that treats the edge constraints independently predicts.

Every tree $T$ satisfies the Sidorenko conjecture. If a bipartite host graph has edge density $\alpha$, then a uniformly random bipartition-respecting map from a $k$-vertex tree into the host is a graph homomorphism with probability at least ${\alpha }^{k-1}$.