Multivalued generalizations of the Frankl--Pach Theorem

Abstract

P. Frankl and J. Pach proved the following uniform version of Sauer's Lemma. Let $n,d,s$ be natural numbers such that $d\le n$, $s+1\le n/2$. Let $\cF \subseteq {[n] \choose d}$ be an arbitrary $d$-uniform set system such that $\cF$ does not shatter an $s+1$-element set, then $$ |\cF|\leq {n \choose s}.$$ We prove here two generalizations of the above theorem to $n$-tuple systems. To obtain these results, we use Gröbner basis methods, and describe the standard monomials of Hamming spheres.

arXiv comment21 pages, accepted by J. of Algebra and its Applications