Optimal Multivalued Shattering

Abstract

We have found the most 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,..., k-1}^n$ be a $k$-ary code of length $n$. For a subset of coordinates $S\subset 1,2,...,n$ the projection of $\mathcal{C}$ to $S$ is denoted by $\mathcal{C}{|}_S$. We say that $\mathcal{C}$ $(i,j)$-{\em shatters} $S$ if $\mathcal{C}{|}_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}\ge 1$ for every $1\le i<j\le q$ and let $p=\sum (s_{i,j}-1)$. Using a natural induction we prove that $$|\mathcal{C}|\le O(n^p)$$ for any given $p$ as $n\to \infty$ and give a construction showing that this exponent is the best possible. Several open problems are mentioned.

arXiv comment12 pages