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 result is independent of the alphabet size $|\Sigma|$.

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

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?