A Sauer-Shelah-like lermma for prefix tree

Question

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?

Answer 1

(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.