Graph homomorphism

A graph homomorphism from $H$ to $G$ is a function $f:V(H)\to V(G)$ that sends every edge $uv$ of $H$ to an edge $f(u)f(v)$ of $G$.

For finite graphs $H,G$, the homomorphism density $t(H,G)$ is the probability that a uniformly random map $V(H)\to V(G)$ is a graph homomorphism. For bipartite graphs with prescribed vertex classes, the random map is chosen separately and uniformly into the corresponding classes.

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}$.