For this section, please recall the discussion of graph basics in Section 1.1 and in particular the discussion of partial order graphs in Section 1.2.
A rooted, directed tree with root \(e \in S\) is a discrete, acyclic graph \((S, \upa)\) with the property that there is a unique finite path from \(e\) to \(x\) for each \(x \in S\).
A rooted directed tree \((S, \upa)\) is the covering graph for a partial order graph \((S, \preceq)\), so that \(x \preceq y\) if and only if \(x = y\) or there is a (unique) finite path from \(x\) to \(y\) in \((S, \upa)\).
By definition \(x \preceq x\) so the relation is reflexive. If \(x \preceq y\) and \(y \preceq x\) for \(x, \, y \in S\) then there is a path from \(x\) to \(y\) and a path from \(y\) to \(x\) in the covering graph \((S, \upa)\). But then \(x = y\) for otherwise there would be a cycle in the covering. So the antisymmetric property holds. Finally if \(x \preceq y\) and \(y \preceq z\) for \(x, \, y, \, z \in S\) then there exists a path from \(x\) to \(y\) and a path from \(y\) to \(z\) in the covering graph \((S, \upa)\). Concatenating the paths gives a path from \(x\) to \(z\) in the covering graph so \(x \preceq z\). Hence the transitive property holds.
Note that the root \(e\) is the minimum element of \((S, \preceq)\) and that \((S, \preceq)\) is well founded. Often our primary interest in the partial order graph \((S, \preceq)\), but the analysis of this graph depends very much on the covering graph \((S, \upa)\), and more generally on \((S, \upa^n)\) where \(\upa^n\) is the \(n\)-fold composition power of \(\upa\) for \(n \in \N\). Here are some graphs of secondary interest:
Let \((S, \upa)\) be a rooted tree with associated partial order graph \((S, \preceq)\).
In addition, we will consider downward run graphs and upward run graphs that can be constructed in natural ways from a rooted tree. In general, the base set \(S\) may be finite or countably infinite, but by assumption, \((S, \preceq)\) is locally finite, so that \([e, x]\) is finite for each \(x \in S\). The graph \((S, \preceq)\) is uniform since there is a unique path from \(x\) to \(y\) whenever \(x \prec y\). Here are some other basic definitions, some of which we have seen before:
Let \((S, \upa)\) be a rooted tree with associated partial order graph \((S, \preceq)\).
Suppose again that \((S, \upa)\) is a rooted tree. The corresponding partial order graph \((S, \preceq)\) is a lower semi-lattice.
For \(x, \, y \in S\), \(x \wedge y \) is the largest common ancestor of \(x\) and \(y\).
Note however that unless \((S, \upa)\) is a directed path, \((S, \preceq)\) is not an upper semi-lattice. If \(x, \, y \in S\) and \(x \parallel y\) then there is no upper bound of \(\{x, y\}\). Note that \((\{y \in S: x \preceq y\}, \upa)\) is the subtree of \((S, \upa)\) rooted at \(x\), Also, even though the tree \((S, \upa)\) is locally finite, it's possible for a vertex to have infinitely many children. Note that \(d(x, y) = d(y) - d(x)\) if \(x \preceq y\). Note also that for \(d(x, y) = n\) if and only if \(x \upa^n y\) for \((x, y) \in S^2\) and \(n \in \N\). Thus the collection \[\{\{y \in S: x \upa^n y\}: n \in \N\} = \{\{y \in S: d(x, y) = n\}: n \in \N\}\] partitions \(\{y \in S: x \preceq y\}\). In particular, when \(x = e\), the collection partitions \(S\). For the next result, recall that the \(\sigma\)-algebra associated with a graph is the \(\sigma\)-algebra generated by the collection of (right) neighbor sets. Of course since we are in a discrete setting, the reference \(\sigma\)-algebra is \(\ms P(S)\), the collection of all subsets of \(S\).
Let \(A_x = \{y \in S: x \upa y\}\), the set of children of \(x \in S\), Let \(\ms A\) be the collection of subsets that consists of \(\{e\}\) and \(A_x\) for \(x \in S\).
Since \((S, \preceq)\) is a discrete, left-finite partial order graph, part (b) holds by a result in Section 1.2. By another result in that section, the \(\sigma\)-algebras associated with \((S, \upa)\) and \((S, \prec)\) are the same and hence the common \(\sigma\)-algebra is \(\sigma(\ms A)\). The countable collection \(\ms A\) partitions \(S\). That is, the subsets in \(\ms A\) are pairwise disjoint and their union is \(S\). So the \(\sigma(\ms A)\) consists of all unions of sets in \(\ms A\).
Unless \((S, \upa)\) is a directed path, the \(\sigma\)-algebra \(\ms A\) associated with \((S, \upa)\) and \((S, \prec)\) is a strict subset of \(\ms P(S)\).
The following examples are trees that we will consider in this chapter. Recall \(\N_m = \{0, 1, \ldots, m\}\) for \(m \in \N_+\).
The infinite directed path is \((\N, \upa)\) where 0 is the root and \(x \upa x + 1\) for \(x \in \N\).
Of course, the infinite directed path was the basic graph studied in Chapter 4 and is associated the semigroup \((\N, +)\).
The (finite) directed path of height \(m \in \N_+\) is \((\N_m, \upa)\) where 0 is the root and \(x \upa x + 1\) for \(x \in \{0, 1, \ldots, m - 1\}\).
For both finite and infinite directed paths, as we have defined them, the corresponding order is the ordinary order \(\le\). Also \(d(x) = x\) for each vertex \(x\) and more generally, \(d(x, y) = y - x\) for verticies \(x, \, y\) with \(x \le y\).
The infinite regular rooted tree \((S, \upa)\) of degree \(k \in \N_+\) is defined by the property that every vertex \(x \in S\) has \(k\) children.
We can also consider the infinite regular rooted tree of infinite degree where every vertex \(x \in S\) has a (countably) infinite set of children. For \(x \in S\), the subtree \((x S, \upa)\) of a regular rooted tree of order \(k \in \N \cup \{\infty\}\) is also a regular rooted tree of order \(k\)
The (finite) regular rooted tree \((S, \upa)\) of degree \(k \in \N_+\) and height \(m \in \N_+\) is defined by the property that every vertex at distance \(j \lt m\) from the root \(e\) has \(k\) children, but the vertices at distance \(m\) from \(e\) are leaves.
The regular rooted tree of degree 1 is isomorphic to the directed path, both in the finite and infinite cases. A regular rooted tree of degree 2 (either finite or infinite) is a binary tree. Suppose that \((S, \upa)\) is the regular rooted tree of degree \(k\) and height \(m\). If \(x \in S\) with then the subtree \((x S, \upa)\) is a regular rooted tree of degree \(k\) with root \(x\) and height \(m - d(x)\).
Directed Binomial trees are defined recursively:
Starting with a directed binomial tree \((S, \upa)\) of order \(n \in \N\), a directed binomial tree of order \(n + 1\) can also be constructed by adding a new child by a new directed edge to every existing vertex in \(S\). The following proposition collects some basic facts about directed binomial trees.
Suppose that \((S, \upa)\) is a directed binomial tree of order \(n \in \N_+\).
So in particular, a directed binomial tree \((S, \upa)\) of order \(n \in \N_+\) has \(2^{n - 1}\) leaves and \(2^{n - 1}\) interior vertices. The vertices of a binomial tree of order \(n \in \N_+\) can be labeled with bit strings of length \(n\). There is a nice consistent way to do so.
Directed binomial trees can be labeled with bit strings as follows:
With the labeling above, vertices that end in 1 are leaves; vertices that end in 10 have one child; vertices that end in 100 have two children; and so forth. The root is labeled \(0 0 \cdots 0\) (\(n\) times). Undirected binomial trees are also interesting and arise in Section 1.10.
Let's return to the general case of a rooted tree \((S, \upa)\) as given in Proposition and the corresponding partial order graph \((S, \preceq)\).
The path function \(\gamma_n\) of order \(n \in \N\) for \((S, \preceq)\) is given by \[\gamma_n(x) = \binom{n + d(x)}{n} = \binom{n + d(x)}{d(x)}, \quad x \in S\]
Recall that by definition, \(\gamma_0(x) = 1\) for \(x \in S\). To construct a path of length \(n\) ending in \(x\) in the graph \((S, \preceq)\), we need to select a multiset of size \(n\) from the \(d(x) + 1\) vertices on the unique simple path of length \(d(x)\) in \((S, \upa)\) form \(e\) to \(x\). The number of ways to do this is \(\binom{n + d(x) + 1 - 1}{d(x)}\).
Generically, let \(\gamma_n\) denote the path function of order \(n \in \N\).
The generating function \(\Gamma\) for \((S, \preceq)\) is given by \[\Gamma(x, t) = \frac{1}{(1 - t)^{d(x)+1}}, \quad x \in S, \, |t| \lt 1\]
From the definition, \[\Gamma(x, t) = \sum_{n=0}^\infty \binom{n+d(x)}{d(x)} t^n = \frac{1}{(1 - t)^{d(x)+1}}, \quad |t| \lt 1, \; x \in \N\]
Generically, let \(\Gamma\) denote the path generating function.
The results follow form geometric and binomial series:
The Möbius kernel \(M\) of \((S, \preceq)\) is given as follows: \[M(x, y) = \begin{cases} 1, & y = x \\ -1, & x \upa y \\ 0, & \text{otherwise} \end{cases}\]
This is well known, but a proof is also easy from the definition: \(M(x, x) = 1\) for \(x \in S\), and \[M(x, y) = -\sum_{x \preceq t \prec y} M(x, t), \quad x \preceq y\]