2010/08/27 by Hegedüs, Gabor, Ronyai, Lajos
#05E40 #13P10 #Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics
paper · doi:10.48550/arxiv.1008.4660
P. Frankl and J. Pach proved the following uniform version of Sauer's Lemma. Let n,d,s be natural numbers such that d≤ n, s+1≤ n/2. Let \cF ⊆ [n] \choose d be an arbitrary d-uniform set system such that \cF does not shatter an s+1-element set, then |\cF|≤ 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.