1 Introduction Let [n] denote the set of integers { 1, 2, . , n} . Given a set X we write P (X) for its power set and X (k) for the set of all its k-element subsets (or k-subsets). The trace of a family A of sets on a set X is A | X = { A ∩ X : A ∈ A } . Vapnik and Chervonenkis [8], Sauer [6] and Shelah [7] independently showed that if A ⊂ P ([n]) is a family with more than Pkư 1 i=0 n i sets, then there is a k-subset X of [n] such that A | X = P (X). This bound is sharp, as shown for example by the family { A ⊂ [n] : | A| < k} , but no characterisation for the extremal families is known. The uniform case of the problem was considered by Frankl and Pach [1]. They proved that if A ⊂ [n] (k) is a family with more than n kư 1 sets, then there is a k-subset X of [n] such that A | X = P (X). This bound is not sharp and was improved later by Mubayi and Zhao [3], but the exact bound is still unknown. While the above problems concern families with traces not containing the power set, Patk´os [4, 5] considered the case of families with traces not containing a maximal chain. Here a maximal chain of a set X is a family of the form X0 ⊂ X1 ⊂ X2 . ⊂ Xr = X, where | X | = i for all i. He proved in [5] that if A ⊂ P ([n]) is a family with more
