MULTIVALUED GENERALIZATIONS OF THE FRANKL–PACH THEOREM
Gábor Hegedüs, Lajos Rónyai · Journal of Algebra and Its Applications · 2011
In [On disjointly representable sets, Combinatorica4 (1984) 39–45] Frankl and Pach proved the following uniform version of Sauer's lemma. Let n,d,s be natural numbers such thatd ≤ n, s + 1 ≤ n/2. Let [Formula: see text] be an arbitrary d-uniform set system such that [Formula: see text] does not shatter an s + 1-element set, then[Formula: see text] 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.