A rooted, directed tree with root \(e \in S\) is a discrete, irreflexive 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)\).
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)\).
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 \(x S\). In particular, when \(x = e\), the collection partitions \(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 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 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\). Find the path function \(\gamma_n\) of order \(n \in \N\) for each of the following graphs:
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_{t \in [x, y)} M(x, t), \quad x \preceq y\]
Let \(I\) be a countable alphabet of letters, and let \(S\) denote the set of all finite length words using letters from \(I\). The empty word, with no letters, is denoted \(e\). Let \(\cdot\) denote the concatenation operation on elements of \(S\). That is, suppose that \(m, \, n \in \N\) and that \(x_i, \, y_j \in I\) for \(i \in \{1, 2, \ldots, m\}\) and \(j \in \{1, 2, \ldots, n\}\). Then \(x = x_1 \cdots x_m \in S\) and \(y = y_1 \cdots y_n \in S\), and \[x y = x_1 \cdots x_m y_1 \cdots y_n\] The space \((S, \cdot)\) is a discrete, positive semigroup, known as the free semigroup generated by \(I\).
The set of words \(S\) is sometimes denoted \(I^*\), and the elements of \(I\) are the irreducible elements of \((S, \cdot)\). The adjective free is used because there are no algebra rules
imposed on \((S, \cdot)\). Here are two examples that we will use in exercises:
The binary semigroup is the free semigroup on the alphabet \(\{0, 1\}\), and so the simplest non-trivial free semigroup. The nonempty words are simply bit strings.
The genetic semigroup is the free semigroup on the alphabet \(\{A, C, G, T\}\). In genetics, the letters refer to the nucleotides that are the base building blocks of DNA: adenine, cytosine, guanine, and thymine, respectively. Nonempty words may represent genes.
For \(x \in S\) and \(i \in I\), let \(d_i(x)\) denote the number of times that letter \(i\) occurs in \(x\), and let \(d(x) = \sum_{i \in I} d_i(x)\) denote the length of \(x\).
Note that \(d_i(x) = 0\) for all but finitely many \(i \in I\). For the partial order graph \((S, \preceq)\) associated with \((S, \cdot)\) note that \(x \preceq y\) if and only if \(y = x t\) for some \(t \in S\), so that \(x\) is a prefix of \(y\) and then \(x^{-1}y\) is the corresponding suffix. For the cover graph \((S, \upa)\) of \((S, \preceq)\) note that \(x \upa y\) if and only if \(y = x i\) for some \(i \in I\). More generally for \(n \in \N\), \(x \upa^n y\) if and only if \(y = x t\) for some \(t \in S\) with \(d(t) = n\). Hence \((S, \upa)\) is a regular tree rooted at \(e\) of degree \(\#(I)\) children. In particular, if \(\#(I) = k \in \N_+\), then \((S, \upa)\) is a regular rooted tree of degree \(k\). Specializing further, when \(k = 2\) and \(I = \{0, \,1\}\), the elements of \(S\) are finite bit strings and the corresponding cover graph \((S, \upa)\) is the binary tree. Note also that \(d(x)\) is the distance from \(e\) to \(x\) in the cover graph \((S, \upa)\) for \(x \in S\), so our notation is consistent. More generally, if \(x \preceq y\) then \(d(x, y) = d(y) - d(x)\) is the distance from \(x\) to \(y\) in \((S, \upa)\).
Let \[\N_I = \left\{(n_i: i \in I): n_i \in \N \text{ for } i \in I \text{ and } n_i = 0 \text{ for all but finitely many } i \in I \right\} \] We define the multinomial coefficients on \(\N_I\) by \[C(\bs{n}) = \#\left\{x \in S: d_i(x) = n_i \text{ for } i \in I\right\} = \frac{\left(\sum_{i \in I} n_i \right)!}{\prod_{i \in I} n_i!}, \quad \bs n = (n_i: i \in I) \in \N_I\]
The free semigroup has the property that\([e, x]\) is finite and totally ordered for each \(x\). Moreover, it is the only discrete positive semigroup with this property.
Suppose that \((S, \cdot)\) is a discrete positive semigroup with associated partial order \(\preceq\) and with the property that \([e, x]\) is finite and totally ordered for each \(x \in S\). Then \((S, \cdot)\) is isomorphic to a free semigroup on an alphabet.
Let \(I\) denote the set of irreducible elements of \((S, \cdot)\). If \(x \in S - \{e\}\) then \(i_1 \preceq x\) for some \(i_1 \in I\) and hence \(x = i_1y\) for some \(y \in S\). If \(y \succ e\) then we can repeat the argument to write \(y = i_2z\) for some \(i_2 \in I\) and \(z \in S\). Note that \(x = i_1 i_2 z\) and hence \(i_1 i_2 \preceq x\). Moreover, \(i_1\) and \(i_1 i_2\) are distinct. Since \([e, x]\) is finite, the process must terminate. Thus, we can write \(x\) in the form \(x = i_1 i_2 \cdots i_n\) for some \(n \in \N_+\) and some \(i_1, i_2, \ldots, i_n \in I\). Finally, we show that the factorization is unique. Suppose that \(x = i_1 i_2 \cdots i_n = j_1 j_2 \cdots j_m\) where \(i_1, \ldots, i_n \in I\) and \(j_1, \ldots, j_m \in I\). Then \(i_1 \preceq x\) and \(j_1 \preceq x\). Since the elements of \([e, x]\) are totally ordered, we must have \(i_1 = j_1\). Using left cancellation we have \(i_2 \cdots i_n = j_2 \cdots j_m\). Continuing in this fashion it follows that \(m = n\) and \(i_1 = j_1\), \(i_2 = j_2, \ldots, i_n = j_n\).
Suppose that \((S, \cdot)\) is a discrete positive semigroup with the property that every \(x \in S\) has a unique finite factoring over the set of irreducible elements \(I\). Then \((S, \cdot)\) is isomporphic to the free semigroup on \(I\).
Every \(x \in S\) has a finite factoring over \(I\), so that \(x = i_1 i_2 \cdots i_n\). If this factoring is unique, then clearly \((i_1, i_2, \ldots i_n) \mapsto i_1 i_2 \cdots i_n\) is an isomorphism from the free semigroup \((I^*, \cdot)\) onto \((S, \cdot)\).
The path functions for the graphs \((S, \preceq)\), \((S, \upa)\) and \((S, \Upa)\) are given Proposition and Proposition . Similarly, the generating functions for \((S, \preceq)\), \((S, \upa)\) and \((S, \Upa)\) are given Proposition and Proposition . Finally, the Möbius kernel is given in Proposition .
The semigroup dimension is the number of letters.
\(\dim(S, \cdot) = \#(I)\).
Note first that a homomorphism \(\phi\) from \((S, \cdot)\) into \((\R, +)\) can uniquely be specified by defining \(\phi(i)\) for all \(i \in I\) and then defining \[\phi(i_1 i_2 \cdots i_n) = \phi(i_1) + \phi(i_2) + \cdots \phi(i_n)\] Thus, if \(\phi\) is a such a homomorphism and \(\phi(i) = 0\) for all \(i \in I\), then \(\phi(x) = 0\) for all \(x \in S\). Now suppose that \(B \subseteq S\) and \(\#(B) \lt \#(I)\). We will show that there exists a nonzero homomorphism from \((S, \cdot)\) into \((\R, +)\) with \(\phi(x) = 0\) for all \(x \in B\). Let \(I_B\) denote the set of letters contained in the words in \(B\). Suppose first that \(I_B\) if a proper subset of \(I\) (and note that this must be the case if \(I\) is infinite). Define a homomorphism \(\phi\) by \(\phi(i) = 0\) for \(i \in I_B\) and \(\phi(i) = 1\) for \(i \in I - I_B\). Then \(\phi(x) = 0\) for \(x \in B\), but \(\phi\) is not the zero homomorphism. Suppose next that \(I_B = I\). Thus \(I\) is finite, so let \(k = \#(B)\) and \(n = \#(I)\), with \(k \lt n\). Denote the words in \(B\) by \[i_{j 1} i_{j 2} \cdots i_{j m_j}, \quad j = 1, 2, \ldots, k\] The set of linear, homogeneous equations \[\phi(i_{j 1}) + \phi(i_{j 2}) + \cdots + \phi(i_{j m_j}) = 0, \quad j = 1, 2, \ldots, k\] has \(n\) unkowns, namely \(\phi(i)\) for \(i \in I\), but only \(k\) equations. Hence there exists a non-trivial solution. The homomorphism so constructed satisfies \(\phi(x) = 0\) for \(x \in B\).
We can use the strict positive semigroup to provide a simple example of a discrete semigroup in which multiples of counting measure \(\#\) are not the only left invariant measures.
Suppose that \(I\) has at least two elements and consider the strict positive semigroup \((S_+, \cdot)\) associated with the free semigroup \((S, \cdot)\). That is, \(S_+ = S - \{e\}\) while \(\cdot\) is still concatenation. Define the function \(g: S_+ \to (0, \infty)\) by \(g(x) = c_i\) if the terminal letter of \(x\) is \(i \in I\), where \(c_i \in (0, \infty)\) for each \(i \in I\) and \(c_i \ne c_j\) for some \(i, \, j \in I\). Let \(\lambda\) be the positive measure on \(S_+\) with density \(g\) (relative to \(\#\)). That is, \[\lambda(A) = \sum_{x \in A} g(x) = \sum_{i \in I} c_i n_i(A), \quad A \subseteq S_+\] where \(n_i(A)\) is the number of words in \(A\) with terminal letter \(i\) for each \(i \in I\). Then \(\lambda\) is left invariant: If \(x \in S\) and \(A \subseteq S\) then the words in \(x A\) have the same terminal letters as the corresponding words in \(A\), so \(\lambda(x A) = \lambda(A)\). But \(\lambda\) is clearly not a multiple of counting measure.