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](https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_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](https://www.sciencedirect.com/science/article/pii/0012365X78901978) 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](https://en.wikipedia.org/wiki/Trie) 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?



A Sauer-Shelah-like lermma for prefix tree
(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**](https://doi.org/10.1007/s003730200003), Graphs Comb. 18, No. 1, 59-73 (2002). [ZBL0990.05123](https://zbmath.org/?q=an:0990.05123).] for binary alphabets, and [*Salo, Ville; Törmä, Ilkka*, [**Playing with subshifts**](https://doi.org/10.3233/FI-2014-1037), Fundam. Inform. 132, No. 1, 131-152 (2014). [ZBL1302.68230](https://zbmath.org/?q=an:1302.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.


