= Solution
Write $r=|V_0|$, $s=|V_1|$, and $e=|E(G)|=\alpha|X||Y|$. We construct a random <graph homomorphism> $\Psi:T\to G$. Choose a root of the <tree>. Map it according to the <degree-biased vertex distribution> on the corresponding side of the <bipartite graph>; after mapping any vertex, map each child independently and uniformly to a neighbour of its parent's image.
Every oriented tree edge is then mapped uniformly onto the $e$ edges of $G$. Every tree vertex in $V_0$ has the degree-biased marginal on $X$, of entropy $H_X$, and every vertex in $V_1$ has the analogous marginal of entropy $H_Y$. Repeated use of the <chain rule for information entropy> along the rooted tree gives
$$
H(\Psi)
=(k-1)\log e
-\sum_{v\in V_0}(\deg_Tv-1)H_X
-\sum_{v\in V_1}(\deg_Tv-1)H_Y.
$$
Since a $k$-vertex <tree> has $k-1$ edges,
$$
\sum_{v\in V_0}(\deg_Tv-1)=s-1,
\qquad
\sum_{v\in V_1}(\deg_Tv-1)=r-1.
$$
The <maximum entropy distribution on a finite set> gives $H_X\leq\log|X|$ and $H_Y\leq\log|Y|$. Hence
$$
\begin{aligned}
H(\Psi)
&\geq(k-1)\log(\alpha|X||Y|)
-(s-1)\log|X|-(r-1)\log|Y|\\
&=\log\!\left(\alpha^{k-1}|X|^r|Y|^s\right).
\end{aligned}
$$
If $N$ is the number of bipartition-respecting <graph homomorphisms> $T\to G$, the support of $\Psi$ has size $N$, so the <maximum entropy distribution on a finite set> also gives $H(\Psi)\leq\log N$. Thus
$$
N\geq\alpha^{k-1}|X|^r|Y|^s.
$$
There are $|X|^r|Y|^s$ bipartition-respecting maps in total, so a uniformly chosen one is a <graph homomorphism> with probability at least $\alpha^{k-1}$. This proves the <Sidorenko inequality for trees>.
Solved by gpt-5.6-sol high.
Back to article page
