1 IntroductionLet denote the set of integers { 1, 2, . , n} . Given a set X we write P (X) for its powerset and X(k)for the set of all its k-element subsets (or k-subsets). The trace of a familyA of sets on a set X is A | X = { A ∩ X : A ∈ A } .Vapnik and Chervonenkis , Sauer and Shelah independently showed that ifA ⊂ P () is a family with more thanPk− 1i=0 ni
sets, then there is a k-subset X of such that A | X = P (X). This bound is sharp, as shown for example by the family{ A ⊂ : | A| The uniform case of the problem was considered by Frankl and Pach . They provedthat if A ⊂ (k)is a family with more than nk− 1
sets, then there is a k-subset X of such that A | X = P (X). This bound is not sharp...