### Theorem 7.4.1. Sidorenko [263].

For every tree \(T\) and graph \(G\text{,}\)

\begin{equation*}
t(T,G)\geq t(K_2,G)^{|E(T)|}\text{.}
\end{equation*}

A graph \(T\) is called a *tree* if it is connected and does not contain a cycle. It is easily observed that \(T\) is a tree if and only if there is a unique path between any two vertices of \(T\text{,}\) and that every tree satisfies \(|E(T)|=|V(T)|-1\text{.}\) In this section, we will apply the facts that we have learned about entropy to prove the following result which is akin to Theorem 4.2.7, but with the graph \(C_4\) replaced by a tree.^{ 1 }

Recall the definition of \(t(H,G)\) from Chapter 4.

Note that this theorem solves Challenge Problem 1.

“Tree.”

For every tree \(T\) and graph \(G\text{,}\)

\begin{equation*}
t(T,G)\geq t(K_2,G)^{|E(T)|}\text{.}
\end{equation*}

The proof will involve constructing a random homomorphism from \(T\) into a graph \(G\) and comparing its entropy to that of a random homomorphism from \(K_2\) to \(G\text{.}\) Thus, it will be useful to understand some basic properties of random homomorphisms from \(K_2\) to \(G\text{.}\)

Let \(G\) be a graph with at least one edge and let \(g\) be a uniformly random homomorphism from \(K_2\) to \(G\text{.}\) Then, for any \(x\in V(K_2)\) and \(v\in V(G)\text{,}\)

\begin{equation*}
\mathbb{P}(g(x)=v)=\frac{d(v)}{2|E(G)|}\text{.}
\end{equation*}

Also, for any \(xy\in E(K_2)\) and \(uv\in E(G)\text{,}\)

\begin{equation*}
\mathbb{P}(g(y)=v\mid g(x)=u)=\frac{1}{d(u)}\text{.}
\end{equation*}

The number of homomorphisms from \(K_2\) to \(G\) is \(2|E(G)|\text{.}\) The number of such homomorphisms that satisfy \(g(x)=v\) is \(d(v)\text{.}\) So, the probability that a random homomorphism satisfies \(g(x)=v\) is \(\frac{d(v)}{2|E(G)|}\text{.}\)

For the second part of the claim, again, note that the number of homomorphisms \(g\) with \(g(x)=u\) is \(d(u)\text{.}\) Since \(g\) is uniform, any of these homomorphisms should be equally likely; thus, the probability that \(g(y)=v\) given that \(g(x)=u\) is \(\frac{1}{d(u)}\text{.}\)

Next, we show that, if the vertices of a tree \(T\) are mapped into \(V(G)\) in a way that follows a “branching random walk,” then the resulting homomorphism will have properties similar to those described in Claim 7.4.2.

For any tree \(T\) and graph \(G\) with at least one edge, there is a distribution on homomorphisms from \(T\) to \(G\) such that if \(f\) is chosen according to that distribution, then, for any \(x\in V(T)\) and \(v\in V(G)\text{,}\)

\begin{equation*}
\mathbb{P}(f(x)=v)=\frac{d(v)}{2|E(G)|}\text{.}
\end{equation*}

Also, for any \(xy\in E(T)\) and \(uv\in E(G)\text{,}\)

\begin{equation*}
\mathbb{P}(f(y)=v\mid f(x)=u)=\frac{1}{d(u)}\text{.}
\end{equation*}

Let \(r\) be an arbitrary *root* vertex of \(T\text{.}\) For each \(x\in V(T)\setminus\{r\}\text{,}\) the *parent* of \(x\) is the unique neighbour \(p(x)\) of \(x\) that is closer to \(r\text{.}\) We say that \(x\) is a *child* of \(y\) if \(p(x)=y\text{.}\) We construct \(f\) as follows. Firstly, for the root, we let \(f(r)\) be a random vertex of \(G\) chosen according to the distribution

\begin{equation*}
\mathbb{P}(f(r)=v)=\frac{d(v)}{2|E(G)|}\text{.}
\end{equation*}

Next, for each child \(x\) of the root, we let \(f(x)\) be a uniformly random neighbour of \(f(r)\text{,}\) where all of these choices are made independently of one another. Generally speaking, for \(x\in V(T)\setminus\{r\}\text{,}\) we assume that \(f(p(x))\) has been chosen already and let \(f(x)\) be a uniformly random neighbour of \(f(p(x))\) chosen independently of all previous choices conditional on the choice of \(f(p(x))\text{.}\) The fact that \(f\) is a homomorphism is clear from construction.

Now, let us show that \(f\) has the desired properties. The first property clearly holds for \(x=r\) by construction. For \(x\in V(T)\setminus\{r\}\) and \(v\in V(G)\text{,}\) we have

\begin{equation*}
\mathbb{P}(f(x)=v)=\sum_{u\in N(v)}\mathbb{P}(f(x)=v\mid f(p(x))=u)\mathbb{P}(f(p(x))=u)
\end{equation*}

which, by induction on the distance from \(x\) to \(y\) and construction of \(f\text{,}\) is equal to

\begin{equation*}
\sum_{u\in N(v)}\frac{1}{d(u)}\cdot \frac{d(u)}{2|E(G)|} = \frac{d(v)}{2|E(G)|}\text{.}
\end{equation*}

Finally, let \(xy\in E(T)\) and \(uv\in E(G)\text{.}\) If \(x\) is the parent of \(y\text{,}\) then \(\mathbb{P}(f(y)=v\mid f(x)=u)=\frac{1}{d(u)}\) simply by construction. So, we assume that \(y\) is the parent of \(x\text{.}\) We have

\begin{equation*}
\mathbb{P}(f(y)=v\mid f(x)=u) = \frac{\mathbb{P}(f(y)=v\text{ and } f(x)=u)}{\mathbb{P}(f(x)=u)}= \frac{\mathbb{P}(f(x)=u\mid f(y)=v)\mathbb{P}(f(y)=v)}{\mathbb{P}(f(x)=u)}
\end{equation*}

\begin{equation*}
=\frac{(1/d(v))\cdot (d(v)/2|E(G)|)}{(d(u)/2|E(G)|)} = \frac{1}{d(u)}\text{.}
\end{equation*}

This completes the proof.

Finally, we prove the theorem.

Let \(n=|V(G)|\text{.}\) If \(T\) has only one vertex (and therefore no edges), then the result is trivial.^{ 2 }

So, assume that \(T\) has at least two vertices. Let \(r\) be an arbitrary root vertex of \(T\) and define “parents” and “children” as in the proof of Proposition 7.4.3.

In the case that \(|E(G)|=0\text{,}\) we view \(0^0\) as being \(1\text{.}\)

Let \(T'\) be a graph obtained from \(T\) by adding \(|V(T)|-2\) isolated vertices. Note that

\begin{equation}
\hom(T',G) = n^{|V(T)|-2}\hom(T,G)\text{.}\tag{7.4.1}
\end{equation}

Consider a random homomorphism \(f\) from \(T'\) to \(G\) where each of the vertices of \(T\) are mapped according to the distribution described in Proposition 7.4.3 and each isolated vertex is mapped to any given vertex \(v\) of \(G\) with probability \(\frac{d(v)}{2|E(G)|}\) independently of all other vertices. Then, by part a of Lemma 7.1.13, we have

\begin{equation*}
\log(\hom(T',G))\geq H(f)=H(f(x): x\in V(T'))\text{.}
\end{equation*}

Label the vertices of \(T'\) by \(v_1,\dots,v_{2|V(T)|-2}\) in such a way that the first \(|V(T)|-1\) vertices are the isolated vertices and the root \(r\) of \(T\text{,}\) and if \(v_i\in V(T)\setminus \{r\}\text{,}\) then \(p(v_i)\) comes before \(v_i\) in the list. Then

\begin{equation*}
H(f) = H(f(v_1),\dots,f(v_{2|V(T)|-2}))=\sum_{i=1}^{2|V(T)|-2}H(f(v_i)\mid f(v_1),\dots,f(v_{i-1}))\text{.}
\end{equation*}

Since the image of each vertex is independent of the image of all vertices that came before it, except for its parent (if it has one), this can be rewritten as

\begin{equation*}
\sum_{i=1}^{|V(T)|-1}H(f(v_i)) + \sum_{i=|V(T)|}^{2|V(T)|-2}H(f(v_i)\mid f(p(v_i)))\text{.}
\end{equation*}

Let \(V(K_2)=\{1,2\}\) and let \(g\) be a uniformly random homomorphism from \(K_2\) to \(G\text{.}\) By Claim 7.4.2 and Proposition 7.4.3, we have that \(f(v_i)\) has the same distribution as \(g(1)\text{.}\) Also, for any \(i\geq |V(T)|\text{,}\) the distribution of \(f(v_i)\) given \(f(p(v_i))\) is also identical to the distribution of \(g(2)\) given \(g(1)\text{.}\) If two random variables have the same distribution, then they have the same entropy. Thus, this expression can be rewritten as

\begin{equation*}
(|V(T)|-1)H(g(1)) + (|V(T)|-1)H(g(2)\mid g(1)) = |E(T)|\cdot H(g(1),g(2))
\end{equation*}

\begin{equation*}
=|E(T)|\cdot H(g)=|E(T)|\cdot\log(\hom(K_2,G))\text{.}
\end{equation*}

Therefore,

\begin{equation*}
\hom(T',G)\geq \hom(K_2,G)^{|E(G)|}\text{.}
\end{equation*}

Now, putting everything together, we get

\begin{equation*}
t(T,G)=\frac{\hom(T,G)}{n^{|V(T)|}} = \frac{\hom(T',G)}{n^{2|V(T)|-2}} \geq \frac{\hom(K_2,G)^{|E(T)|}}{n^{2|E(T)|}} = t(K_2,G)^{|E(T)|}
\end{equation*}

and so we are done.

Note that Theorem 7.4.1 is best possible (asymptotically) by letting \(G\) be a large random graph. In fact, any \(d\)-regular graph would also work; see Exercise 11 in Section 7.5.

Here is a YouTube video related to Sidorenko’s Conjecture for trees: