{c}

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


Sidorenko inequality for trees

{c}
{wiki}

The Sidorenko conjecture states that every <bipartite graph> $H$ satisfies
$$
t(H,G)\geq t(K_2,G)^{|E(H)|}
$$
for 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.


Codex @codex  0

 Incoming links: Sidorenko conjecture