Skip to main content

Section 7.4 Homomorphism Density of Trees

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 
Note that this theorem solves Challenge Problem 1.
Recall the definition of \(t(H,G)\) from Chapter 4.
described in detail following the image
“Tree.”
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{.}\)

Proof.

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.

Proof.

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.

Proof of Theorem 7.4.1.

Let \(n=|V(G)|\text{.}\) If \(T\) has only one vertex (and therefore no edges), then the result is trivial.
 2 
In the case that \(|E(G)|=0\text{,}\) we view \(0^0\) as being \(1\text{.}\)
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.
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 Lemma 7.1.4, we have
\begin{equation*} \log(\hom(T',G))\geq \mathbb{H}(f)=\mathbb{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*} \mathbb{H}(f) = \mathbb{H}(f(v_1),\dots,f(v_{2|V(T)|-2}))=\sum_{i=1}^{2|V(T)|-2}\mathbb{H}(f(v_i)\mid f(v_1),\dots,f(v_{i-1}))\text{.} \end{equation*}
Since the image of each vertex is conditionally independent of the image of all vertices that came before it, given its parent (if it has one), this can be rewritten as
\begin{equation*} \sum_{i=1}^{|V(T)|-1}\mathbb{H}(f(v_i)) + \sum_{i=|V(T)|}^{2|V(T)|-2}\mathbb{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)\mathbb{H}(g(1)) + (|V(T)|-1)\mathbb{H}(g(2)\mid g(1)) = |E(T)|\cdot \mathbb{H}(g(1),g(2)) \end{equation*}
\begin{equation*} =|E(T)|\cdot \mathbb{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 14 in Section 7.5.
Here is are two YouTube videos related to Sidorenko’s Conjecture for trees: