Optimal Multivalued Shattering

Details Optimal Multivalued Shattering Optimal Multivalued Shattering

2011-09-08

arxiv.org/abs/1109.1748v1

Mathematics

Combinatorics

12 pages

Scientific paper

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}\geq 1$ for every $1\leq i< j\leq q$ and let $p=\sum (s_{i,j}-1)$. Using a natural induction we prove that $$ |{\mathcal C}|\leq 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.

Affiliated with

Also associated with

No associations

Rating

Optimal Multivalued Shattering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Multivalued Shattering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Multivalued Shattering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-475500