A Sauer-Shelah-like lermma for prefix tree

I proved a variant of the Sauer-Shelah lemma and I was wondering if something like that is already known.

Let $$S \subseteq \{0,1\}^n$$. We say that a set of coordinates $$K \subseteq [n]$$ is shattered by $$S$$ if $$S|_K = \{0,1\}^K$$. The Sauer-Shelah lemma says that if $$|S| > \sum_{i=0}^{d-1} \binom{n}{i}$$ then $$S$$ shatters some set $$K\subseteq[n]$$ of size $$d$$.

Karpovsky and Milman generalized the Sauer-Shelah lemma for larger alphabets in the natural way. Here, we say that a set $$S \subseteq \Sigma^n$$ (for some alphabet $$\Sigma$$) shatters a set $$K\subseteq [n]$$ if and only if $$S|_K = \Sigma^K$$. Informally, the Karpovsky-Milman result says that if $$S$$ is sufficiently large, then it shatters some large set $$K \subseteq [n]$$.

Unfortunately, when the alphabet $$\Sigma$$ is large (say, of the same order of magnitude as $$n$$), the Karpovsky-Milman result is rather weak quantitatively, in the sense that it requires $$S$$ to be extremely large. Moreover, this limitation is necessary.

Nevertheless, suppose that we are willing to compromise: instead of requiring that $$S \subseteq \Sigma^n$$ shatters $$K$$, we only require a weaker condition on $$K$$:

• There exist more than $$\frac{|\Sigma|}{2}$$ values $$\sigma_1 \in \Sigma$$ such that for each such $$\sigma_1$$ it holds that:
• There exist more than $$\frac{|\Sigma|}{2}$$ values $$\sigma_2 \in \Sigma$$ such that for each such $$\sigma_2$$ it holds that:
• $$\vdots$$
• There exist more than $$\frac{|\Sigma|}{2}$$ values $$\sigma_{|K|} \in \Sigma$$ such that $$(\sigma_1, \ldots, \sigma_{|K|}) \in S|_K$$.

In other words, the prefix tree of $$S|_K$$ has a subtree whose minimal degree is greater than $$\frac{|\Sigma|}{2}$$. The motivation for this condition is that if it holds for two sets $$S|_K, T|_K \subseteq \Sigma^K$$, then they must intersect.

Now, I can prove that if $$\frac{|S|}{|\Sigma|^n} > 2^{-n} \cdot \sum_{i=0}^{d-1} \binom{n}{i}$$ then $$S|_K$$ satisfies the above condition for some $$K \subseteq [n]$$ of size $$d$$. Note that here $$S$$ has the same density in $$\Sigma^n$$ as in the condition of the Sauer-Shelah Lemma. In particular, this condition, in terms of the density of the sets, is independent of the alphabet size $$|\Sigma|$$.

Is such a result already known? Was a similar notion considered in the literature?

1 Answer

(Joint work with Ilkka Törmä.)

From winning set/order-shattering considerations, we get a tight upper bound for the size of $$S$$ not having a subtree of a similar kind as you describe. It's not exactly equal, but it seems we get stronger results in any case.

Say a set $$S$$ has property $$P$$ if it satisfies what you write, meaning there is no set of coordinates $$K$$ such that (your conditions). We will define another property $$Q$$ such that property $$P$$ implies property $$Q$$. You give an upper bound on the size of sets with property $$P$$.

I will give a tight bound for $$S$$ with property $$Q$$, and show that (although $$P$$ and $$Q$$ are not equivalent) the maximal size of a set satisfying $$P$$ is the same as the maximal size for $$Q$$, so we are bounding the same thing. For even alphabets, our bound is exactly equal to yours. In the case of odd alphabets, your formula sometimes gives a better bound (which is in conflict with my claim that the bound is tight).

Suppose the alphabet size is $$|\Sigma| = n$$. The winning set of $$S$$ is defined as the set of words $$w$$ over alphabet $$\{1,2,...,n\}$$ such that Alice wins the following game: Alice and Bob play alternately, and Alice starts. For each $$i = 1, 2 \ldots, |w|$$, on the $$i$$th turn if $$w_i = k$$, then Alice will pick a subset of size $$k$$ from the alphabet. On Bob's turn, he picks a letter from the set Alice just picked. Alice wins if at the end the constructed word is in $$S$$.

Now we have the fundamental theorem of winning sets:

Theorem. The winning set of $$S \subset \Sigma^n$$ has the same cardinality as $$S$$.

For a proof, see [Anstee, R. P.; Rónyai, Lajos; Sali, Attila, Shattering news, Graphs Comb. 18, No. 1, 59-73 (2002). ZBL0990.05123.] for binary alphabets, and [Salo, Ville; Törmä, Ilkka, Playing with subshifts, Fundam. Inform. 132, No. 1, 131-152 (2014). ZBL1302.68230.] or https://arxiv.org/pdf/1911.08146.pdf for general alphabets.

Say $$S$$ has property $$P$$ if there is no $$K$$ such that the restriction to coordinates $$K$$ has, in its winning set, a word with all symbols having value strictly greater than $$|\Sigma|/2$$. I believe this is the condition from your post. Let's say $$S$$ has property $$Q$$ if its winning set does not have any word with at least $$d$$ letters whose value is strictly greater than $$|\Sigma|/2$$. I claim that $$P \implies Q$$. Namely, if $$Q$$ fails, then the game tree proving that the word $$w$$ is in the winning set gives a tree in the coordinates $$K$$ where we have large values. The properties $$P$$ and $$Q$$ are not equivalent, namely the winning shift of $$\{001, 010, 100, 111\}$$ is $$\{111,112,121,211\}$$ but it does not have $$P$$ (it fails for $$K = \{0,2\}$$)

Now let's consider a set with property $$Q$$. Let $$m = \lfloor \Sigma/2 \rfloor$$. The number of words in the winning set with $$i$$ letters greater than $$m$$ is at most $$\binom{n}{i} m^i (|\Sigma| - m)^{n - i}$$. So we get the upper bound $$|S| \leq \sum_{i = 0}^{d-1} \binom{n}{i} m^i (|\Sigma| - m)^{n - i}$$ if $$S$$ satisfies $$Q$$.

This formula is tight. Namely if we pick the alphabet $$\Sigma = \{1,2,...,|\Sigma|\}$$ then the set of words where at most $$d-1$$ symbols greater than $$|\Sigma|/2$$ appear is downward closed, i.e. if $$w$$ is in this set, and $$u_i \leq w_i$$ for all $$i$$, then $$u$$ is also in this set set. Now, it is known that if a set is downward closed, then it is its own winning set, and by definition then its winning set (i.e. itself) does not have any words with $$d$$ or more symbols of value $$|\Sigma|/2$$ or greater.

In fact, in this example, we also have property $$P$$, so it shows that although $$P$$ and $$Q$$ are not equivalent, the maximal size of a set $$S$$ satisfying $$P$$ is the same as for $$Q$$.

Let's compare with your formula. If $$S$$ satisfies your condition $$P$$, then it satisfies $$Q$$, and both formulas hold. If $$|S|$$ is even, then $$(|\Sigma| - m) = m$$ so our formula is $$|S| \leq \sum_{i = 0}^{d-1} \binom{n}{i} m^n$$ and dividing by $$(|\Sigma|/2)^n$$ we get exactly your condition $$|S|/|\Sigma|^n \leq 2^{-n} \sum_{i = 0}^{d-1} \binom{n}{i}$$.

On the other hand, if $$|S|$$ is odd, then we get $$(|\Sigma| - m) = m + 1$$ so the condition for the winning set gives $$|S| \leq \sum_{i = 0}^{d - 1} \binom{n}{i} m^i (m + 1)^{n - i}$$.

Your condition is $$|S|/(2m + 1)^n \leq 2^{-n} \sum_{i = 0}^{d-1} \binom{n}{i}$$ or $$|S|/ \leq \sum_{i = 0}^{d-1} \binom{n}{i} (m + 1/2)^n$$, which is close, but not quite the same.

Sometimes your formula gives better values, for example this happens when $$|\Sigma| = 5, d = 3, n = 6$$, where your formula gives $$5372$$ and ours gives $$8505$$. In these cases, it seems your formula must be wrong, since as discussed our formula is tight.

• Thanks! You are right - I was not careful enough when wrote the formula in my question, since I only had in mind alphabets of even size. The actual formula I get is exactly the same one as yours. From your description, it sounds like the proofs should be similar too. BTW, I sent you an e-mail with some follow-up questions. Mar 30, 2023 at 14:15