Optimal Multivalued Shattering
Zoltán Füredi, Attila Sali · SIAM Journal on Discrete Mathematics · 2012
We have found a general extension of the celebrated Sauer, Perles and Shelah, Vapnik and Chervonenkis result from 0-1 sequences to k-ary codes still giving a polynomial bound. Let $\mathcal{C}\subseteq \{ 0,1,\dots, k-1 \}^n$ be a k-ary code of length n. For a subset of coordinates $S\subset \{1,2,\ldots ,n\}$, the projection of $\mathcal{C}$ to S is denoted by $\mathcal{C}\vert_S$. We say that $\mathcal{C}$ $(i,j)$-shatters S if $\mathcal{C}\vert_S$ contains all the $2^{|S|}$ distinct vectors (codewords) with coordinates i and j. Suppose that $\mathcal{C}$ does not $(i,j)$-shatter any coordinate set of size $s_{i,j}\geq 1$ for every $0\leq i< j\leq k-1$, and let $p=\sum (s_{i,j}-1)$. Using a natural induction we prove that $|{\mathcal C}|\leq O(n^p) $ as $n\to \infty$. We give a construction showing that this exponent is the best possible. Several open problems are mentioned.