Optimal multivalued shattering

DOI10.1137/110850104MaRDI QIDQ2910947zbMATH OpenOpenAlexFDO

Authors Attila Sali, Zoltán Füredi

Publication date 12 September 2012

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.1748

zbMATH Keywords

forbidden configurationshatteringVapnik-Chervonenkis-dimension

Mathematics Subject Classification ID

Extremal set theory (05D05) Extremal combinatorics (05D99)

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 $mathcalCsubseteq{0,1,\mathrm{...},k-1}^n$ be a $k$-ary code of length $n$. For a subset of coordinates $Ssubset1,2,\mathrm{...},n$ the projection of $mathcalC$ to $S$ is denoted by $mathcalC{|}_S$. We say that $mathcalC$ $(i,j)$-{em shatters} $S$ if $mathcalC{|}_S$ contains all the $2^{|S|}$ distinct vectors (codewords) with coordinates $i$ and $j$. Suppose that $mathcalC$ does not $(i,j)$-shatter any coordinate set of size $s_{i,j}geq1$ for every $1leqi<jleqq$ and let $p=sum(s_{i,j}-1)$. Using a natural induction we prove that ${\displaystyle }$ |{mathcal C}|leq O(n^p)${\displaystyle }$ for any given $p$ as $noinfty$ and give a construction showing that this exponent is the best possible. Several open problems are mentioned.

Recommendations

• Shattering news
• Standard monomials and extremal vector systems
• Shattering and more: Extending the complete object
• Embeddings and the trace of finite sets
• Shatter functions with polynomial growth rates

Cited in

(6)

• Multi-symbol forbidden configurations
• Embeddings and the trace of finite sets
• Shattering All Sets of ‘k’ Points in “General Position” Requires (k — 1)/2 Parameters
• Exponential multivalued forbidden configurations
• Shatter functions with polynomial growth rates
• Multivalued matrices and forbidden configurations

This page was built for publication: Optimal multivalued shattering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2910947)