2 Preliminaries

Let ${\mathbb {N}}$ denote the set of natural numbers (which for us include $0$ ) and, for any $n \in {\mathbb {N}}$ , let $[n]$ denote the first n natural numbers. That is,

$$\begin{align*}[n] := \{ 0, 1, 2, \dots, n-1 \}. \end{align*}$$

In particular, $[0] = \emptyset $ . For sets X and Y, let ${}^{X}{Y}$ denote the set of all functions from X to Y. For $n \in {\mathbb {N}}$ and a non-empty set L, let

$$\begin{align*}{}^{\leq n}{L} := \bigcup_{i=0}^n {}^{[i]}{L}. \end{align*}$$

Given $f \in {}^{[n]}{L}$ and $\ell \in L$ , let “ $f {}^{\frown} \langle \ell \rangle $ ” denote the function in ${}^{[n+1]}{L}$ given by

$$\begin{align*}(f {}^{\frown} \langle \ell \rangle)(i) = \begin{cases} f(i) & \text{ if } i \in [n], \\ \ell & \text{ if } i = n. \end{cases} \end{align*}$$

If we think of elements of ${}^{[n]}{L}$ as strings of length n with alphabet L, then this is usual concatenation.

In this article, we work with finite trees in the partial order sense. (The results can also be suitably modified to the world of finite rooted trees in the graph-theoretic sense.) Most of this terminology listed below is standard (see, e.g., [Reference West16]). We say that a partial order $(T, \unlhd )$ is a tree if it has a unique $\unlhd $ -minimal element (called the root) and, for all $a \in T$ , the set $\{ b \in T : b \unlhd a \}$ is linearly ordered by $\unlhd $ . We say that $a \in T$ is a leaf of T if it is $\unlhd $ -maximal in T. Let $\operatorname {\mathrm {Lf}}(T)$ denote the set of leaves of T. For $a \in T$ , the height (or level) of a, denoted $\operatorname {\mathrm {ht}}(a)$ , is the number of elements that are strictly $\unlhd $ -below a; in particular, if $r \in T$ is the root, then $\operatorname {\mathrm {ht}}(r) = 0$ . The height of T, denoted $\operatorname {\mathrm {ht}}(T)$ , is the smallest integer larger than $\operatorname {\mathrm {ht}}(a)$ for all $a \in T$ . Given $a, b \in T$ , we say that b is a child of a (or a is the parent of b) if $a \lhd b$ and, for all $c \in T$ , if $a \unlhd c \unlhd b$ , then $c = a$ or $c = b$ . The branching factor (or arity) of T, denoted $\operatorname {\mathrm {br}}(T)$ , is the maximum number of children of an element of T. Note that, for all $n, m \in {\mathbb {N}}$ , if T is a tree with $\operatorname {\mathrm {ht}}(T) \leq n$ and $\operatorname {\mathrm {br}}(T) \leq m$ , then we have that

$$\begin{align*}\left| \operatorname{\mathrm{Lf}}(T) \right| \leq m^{n-1}. \end{align*}$$

For $m \in {\mathbb {N}}$ , we say that T is a full m-ary tree if every element of T has either $0$ children or m children. Finally, we say that T is a complete m-ary tree if it is a full m-ary tree such that, for all leaves $a, b \in T$ , $\operatorname {\mathrm {ht}}(a) = \operatorname {\mathrm {ht}}(b)$ . If T is a full m-ary tree, then $\operatorname {\mathrm {br}}(T) = m$ (or $\operatorname {\mathrm {br}}(T) = 0$ if there is only one element in T).

Given a finite tree $(T, \unlhd )$ and $a, b \in T$ , the meet of a and b, denoted $a \wedge b$ , is the $\unlhd $ -largest element c such that $c \unlhd a$ and $c \unlhd b$ . One can check that this exists for any a and b. If $(T, \unlhd )$ and $(T', \unlhd )$ are trees, then an embedding of T into $T'$ is an injective function $f : T \rightarrow T'$ such that, for all $a, b \in T$ , $a \unlhd b$ if and only if $f(a) \unlhd f(b)$ (this is the usual notion of embedding between the structures $(T, \unlhd )$ and $(T', \unlhd )$ ). We say that f is meet-preserving if, for all $a, b \in T$ , $f(a \wedge b) = f(a) \wedge f(b)$ . We say that f is level-preserving if, for all $a, b \in T$ , $\operatorname {\mathrm {ht}}(a) = \operatorname {\mathrm {ht}}(b)$ if and only if $\operatorname {\mathrm {ht}}(f(a)) = \operatorname {\mathrm {ht}}(f(b))$ .

Let $(T, \unlhd )$ be a finite tree and $T' \subseteq T$ . Then, $(T',\unlhd )$ is a tree and we clearly have that $\operatorname {\mathrm {ht}}(T') \leq \operatorname {\mathrm {ht}}(T)$ . We say that $T'$ is $\unlhd $ -downward closed if, for all $a \in T'$ and $b \in T$ , if $b \unlhd a$ , then $b \in T'$ . If $T'$ is a $\unlhd $ -downward closed subtree of $(T, \unlhd )$ , then it preserves meets and the parent–child relationship. Therefore, $\operatorname {\mathrm {br}}(T') \leq \operatorname {\mathrm {br}}(T)$ .

Let $n \in {\mathbb {N}}$ and let L be a finite, non-empty set. Then, ${}^{\leq n}{L}$ has a natural tree structure given by $f \unlhd g$ if $f = g |_{[i]}$ for some $i \leq n$ with $[i] \subseteq \operatorname {\mathrm {dom}}(f)$ . This makes ${}^{\leq n}{L}$ into a complete $|L|$ -ary tree of height $n+1$ ; in fact, up to isomorphism, this is the unique such tree. In this tree, the height of f is given by $\operatorname {\mathrm {ht}}(f) = |\operatorname {\mathrm {dom}}(f)|$ and the meet of f and g is given by $f \wedge g = f |_{[i]}$ where i is largest such that $f |_{[i]} = g |_{[i]}$ . Note that the unique function in ${}^{\emptyset }{L}$ is the root of ${}^{\leq n}{L}$ and the set of leaves is $\operatorname {\mathrm {Lf}}({}^{\leq n}{L}) = {}^{[n]}{L}$ .

3 The Chase–Freitag Lemma

With this terminology, the Chase–Freitag Lemma (Theorem 5.3 of [Reference Chase and Freitag6]) can be restated as follows. See also Theorem 2.2 of [Reference Walker14].

Theorem 3.1 (Theorem 5.3 of [Reference Chase and Freitag6])

Fix $n, m, d \in {\mathbb {N}}$ with $m \geq 1$ and $n \geq d$ . Fix a tree $(T, \unlhd )$ with $\operatorname {\mathrm {ht}}(T) \leq n+1$ and $\operatorname {\mathrm {br}}(T) \leq m$ . If are no meet-preserving and level-preserving embeddings of ${}^{\leq d+1}{[m]}$ into T, then

$$\begin{align*}|\operatorname{\mathrm{Lf}}(T)| \leq \sum_{i=0}^d \binom{n}{i} (m-1)^{n-i}. \end{align*}$$

As a corollary, if there are no embeddings of ${}^{\leq d+1}{[m]}$ into T, then the conclusion still follows (as there are certainly no meet-preserving and level-preserving embeddings).

Given $n, m, d \in {\mathbb {N}}$ with $m \geq 1$ and $n \geq d$ , define

$$\begin{align*}\Phi_{d,m}(n) = \sum_{i=0}^d \binom{n}{i} (m-1)^{n-i}. \end{align*}$$

In particular, by the Binomial Theorem,

$$\begin{align*}\Phi_{d,m}(d) = \sum_{i=0}^d \binom{d}{i} 1^i (m-1)^{d-i} = m^d. \end{align*}$$

To prove Theorem 3.1, we first need a quick lemma, which follows from Pascal’s Rule.

Lemma 3.2. Given $n, m, d \in {\mathbb {N}}$ with $m \geq 1$ and $n \geq d \geq 1$ ,

$$\begin{align*}(m-1) \cdot \Phi_{d,m}(n-1) + \Phi_{d-1,m}(n-1) = \Phi_{d,m}(n). \end{align*}$$

We are now ready to prove Theorem 3.1. This is essentially the same proof given in [Reference Chase and Freitag6], though suitably modified for this setting.

Proof of Theorem 3.1

We prove this by induction on d.

Suppose that $d = 0$ . Suppose that $\operatorname {\mathrm {br}}(T) \geq m$ ; say that $a \in T$ has at least m children. Then, we can embed ${}^{\leq 1}{[m]}$ into T by sending the root to a and each child of the root to a different child of a; this is clearly a meet-preserving and level-preserving embedding. Therefore, if there exists no meet-preserving and level-preserving embedding of ${}^{\leq 1}{[m]}$ into T, then $\operatorname {\mathrm {br}}(T) < m$ . Therefore,

$$\begin{align*}\left| \operatorname{\mathrm{Lf}}(T) \right| \leq (m-1)^n = \Phi_{0,m}(n). \end{align*}$$

Fix $d> 0$ and proceed by induction on $n \geq d$ . Suppose that $\operatorname {\mathrm {ht}}(T) \leq n+1$ and $\operatorname {\mathrm {br}}(T) \leq m$ and there is no meet-preserving and level-preserving embedding of ${}^{\leq d+1}{[m]}$ into T. If $n = d$ , then notice that $\Phi _{d,m}(n) = m^n$ . Thus, in this case,

$$\begin{align*}\left| \operatorname{\mathrm{Lf}}(T) \right| \leq m^n = \Phi_{d,m}(n). \end{align*}$$

So we may assume $n> d$ . Consider the following subtree of T:

$$\begin{align*}T^* := \{ a \in T : \operatorname{\mathrm{ht}}(a) < n \}. \end{align*}$$

Clearly $\operatorname {\mathrm {ht}}(T^*) \leq n$ and, since $T^*$ is $\unlhd $ -downward closed, $\operatorname {\mathrm {br}}(T^*) \leq m$ . Moreover, as T does not embed ${}^{\leq d+1}{[m]}$ preserving meets and levels, then neither does $T^*$ . By induction on n, we have that

$$\begin{align*}|\operatorname{\mathrm{Lf}}(T^*)| \leq \Phi_{d,m}(n-1). \end{align*}$$

Next, let $A'$ denote the elements $a \in T$ such that $\operatorname {\mathrm {ht}}(a) = n-1$ and a has exactly m children in T. Let $T'$ be the $\unlhd $ -downward closure of $A'$ in T; that is,

$$\begin{align*}T' := \{ b \in T : (\exists a \in A')[ b \unlhd a ] \}. \end{align*}$$

This is clearly a subtree of $T^*$ , so $\operatorname {\mathrm {ht}}(T') \leq n$ . Moreover, as $T'$ is $\unlhd $ -downward closed, $\operatorname {\mathrm {br}}(T') \leq m$ . Moreover, by construction, $A' = \operatorname {\mathrm {Lf}}(T')$ . Finally, we claim that there exists no meet-preserving and level-preserving embedding of ${}^{\leq d}{[m]}$ into $T'$ .

Towards a contradiction, suppose that $f : {}^{\leq d}{[m]} \rightarrow T'$ were such an embedding. From this, we will create a meet-preserving and level-preserving embedding $f'$ of ${}^{\leq d+1}{[m]}$ into T. First, for each $b \in {}^{<d}{[m]}$ , set $f'(b) = f(b)$ . For each $b \in {}^{[d]}{[m]}$ , choose some $a \in \operatorname {\mathrm {Lf}}(T')$ such that $f(b) \unlhd a$ and set $f'(b) = a$ . Since $a \in A'$ , it has exactly m children in T. Thus, for each $b'$ a child of b, we can choose a unique child of a and set $f'(b')$ to that child. Check that $f'$ is a meet-preserving and level-preserving embedding of ${}^{\leq d+1}{[m]}$ into T, contrary to assumption.

Therefore, by induction on d, we have that

$$\begin{align*}|A'| = |\operatorname{\mathrm{Lf}}(T')| \leq \Phi_{d-1,m}(n-1). \end{align*}$$

For each $a \in \operatorname {\mathrm {Lf}}(T)$ , if $\operatorname {\mathrm {ht}}(a) < n$ , then $a \in \operatorname {\mathrm {Lf}}(T^*)$ . Otherwise, either the parent b of a has at most $m-1$ children, in which case $b \in \operatorname {\mathrm {Lf}}(T^*)$ , or b has m children, in which case $b \in \operatorname {\mathrm {Lf}}(T^*)$ and $b \in A'$ . Therefore, we conclude that

$$ \begin{align*} |\operatorname{\mathrm{Lf}}(T)| & \leq (m-1) |\operatorname{\mathrm{Lf}}(T^*)| + |A'| = \\ & (m-1) \cdot \Phi_{d,m}(n-1) + \Phi_{d-1,m}(n-1) = \Phi_{d,m}(n). \end{align*} $$

The last equality follows from Lemma 3.2.

4 Applications to Sauer–Shelah and Bhaskar

Let L be a non-empty set (of “labels”) and let X be a set (the “base set”). A concept class ${\mathcal {C}}$ (on X with labels in L) is a subset of ${}^{X}{L}$ (in other words, ${\mathcal {C}}$ is a set of colorings of X with colors in L). We will assume that L is finite, but we make no such assumptions on X or ${\mathcal {C}}$ . When $L = [2]$ , this gives the usual notion of a (binary) concept class.

Given a concept class ${\mathcal {C}}$ on X with labels in L and $n \in {\mathbb {N}}$ , a well-labeling of ${\mathcal {C}}$ of height n is a function $f : T \rightarrow X \cup {\mathcal {C}}$ such that

• • $T \subseteq {}^{\leq n}{L}$ ;

• • $\operatorname {\mathrm {Lf}}(T) \subseteq {}^{[n]}{L}$ ;

• • T is $\unlhd $ -downward closed;

• • for all $a \in T$ , if $\operatorname {\mathrm {ht}}(a) < n$ , then $f(a) \in X$ ;

• • for all $a \in T$ , if $\operatorname {\mathrm {ht}}(a) = n$ , $f(a) \in {\mathcal {C}}$ ;

• • for all $a, b \in T$ with $\operatorname {\mathrm {ht}}(a) = n$ , and for all $\ell \in L$ , if $b {}^{\frown} \langle \ell \rangle \unlhd a$ , then $[f(a)](f(b)) = \ell $ .

In other words, we take T a $\unlhd $ -downward closed subtree of ${}^{\leq n}{L}$ whose leaves are of height n, we label all the nodes of T of height $< n$ with elements of X, and we label all the nodes of T of height n with elements of ${\mathcal {C}}$ . Moreover, we demand that if b is below a in the “ $\ell $ -direction” and $\operatorname {\mathrm {ht}}(a) = n$ , then $f(a)$ labels $f(b)$ with $\ell $ . Let $\operatorname {\mathrm {lf}}(f) = |\operatorname {\mathrm {Lf}}(T)|$ , which is at most $|L|^n$ . Although the height of T is $n+1$ , the “X-labeled part” of T has height n, justifying the name “well-labeling of height n.” Since T is $\unlhd $ -downward closed, we have that $\operatorname {\mathrm {br}}(T) \leq |L|$ .

We say that a well-labeling f of ${\mathcal {C}}$ of height n is balanced if, for all $a, b \in \operatorname {\mathrm {dom}}(f)$ , if $\operatorname {\mathrm {ht}}(a) = \operatorname {\mathrm {ht}}(b) < n$ , then $f(a) = f(b)$ . Let $\text {Wl}({\mathcal {C}},n)$ denote the set of all well-labelings of ${\mathcal {C}}$ of height n and let $\text {Wl}_{\text {b}}({\mathcal {C}},n)$ denote the set of all balanced well-labelings of ${\mathcal {C}}$ of height n.

The above diagram depicts a well-labeling of ${\mathcal {C}} = {}^{X}{L}$ of height $2$ , where $X = \{ 1, 2, 3 \}$ and $L = \{ \mathrm {red}, \mathrm {green}, \mathrm {blue} \}$ . For example, the label “rgb” means that we color the element $1$ red, the element $2$ green, and the element $3$ blue. There can be no other children of the left-most $1$ , since we are demanding that $1$ be colored red. This well-labeling is clearly not balanced, as the nodes of height $1$ have different labels.

When $L = [2]$ , this is the usual definition of the Littlestone and VC dimensions. Although VC dimension is typically defined in terms of the “shattering” of sets, it is easily seen to be equivalent to the above definition. From the above definition, it is clear that $\pi _{{\mathcal {C}}}(n) \leq \rho _{{\mathcal {C}}}(n) \leq |L|^n$ for all $n \in {\mathbb {N}}$ and that $\operatorname {\mathrm {VCdim}}({\mathcal {C}}) \leq \operatorname {\mathrm {Ldim}}({\mathcal {C}})$ .

In this terminology, we can now state the Sauer–Shelah Lemma (Theorem 1 of [Reference Sauer11], Theorem 1.5 of [Reference Shelah12], and Lemma 1 of [Reference Vapnik and Chervonenkis13]) and Bhaskar’s Lemma (Theorem 4.2 of [Reference Bhaskar3]). These reduce to the usual versions when $L = [2]$ .

Theorem 4.2 (Sauer–Shelah Lemma, [Reference Sauer11–Reference Vapnik and Chervonenkis13])

Let $d \in {\mathbb {N}}$ , X be a set, L a finite, non-empty set, and ${\mathcal {C}}$ a concept class on X with labels in L. If $\operatorname {\mathrm {VCdim}}({\mathcal {C}}) \leq d$ , then, for all $n \in {\mathbb {N}}$ with $n \geq d$ ,

$$\begin{align*}\pi_{{\mathcal{C}}}(n) \leq \sum_{i=0}^d \binom{n}{i} (|L|-1)^{n-i}. \end{align*}$$

The proof of Bhaskar’s Lemma is easier, as we don’t even need the “level-preserving” condition.

Theorem 4.3 (Bhaskar’s Lemma, [Reference Bhaskar3])

Let $d \in {\mathbb {N}}$ , X be a set, L a finite, non-empty set, and ${\mathcal {C}}$ a concept class on X with labels in L. If $\operatorname {\mathrm {Ldim}}({\mathcal {C}}) \leq d$ , then, for all $n \in {\mathbb {N}}$ with $n \geq d$ ,

$$\begin{align*}\rho_{{\mathcal{C}}}(n) \leq \sum_{i=0}^d \binom{n}{i} (|L|-1)^{n-i}. \end{align*}$$

Note that, when $L = [2]$ , these two theorems give a polynomial bound on the respective shatter functions. However, when $|L|> 2$ , the bound is exponential. They do reduce the base of the exponent in these cases. For example, when ${\mathcal {C}}$ is ternary-labeled, if ${\mathcal {C}}$ has bounded Littlestone dimension, then any well-labeling of ${\mathcal {C}}$ is “essentially binary.”

Note the difference in the application of the Chase–Freitag Lemma to the Sauer–Shelah Lemma versus Bhaskar’s Lemma. For the Sauer–Shelah Lemma, we need the full strength of the non-existence of a meet-preserving and level-preserving embedding of the complete m-ary tree of height $d+2$ into our fixed tree. However, for Bhaskar’s Lemma, we only need the non-existence of meet-preserving embeddings.