Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Traces Without Maximal Chains. | Traces Without Maximal Chains Ta Sheng Tan Submitted Feb 10 2010 Accepted Mar 3 2010 Published Mar 15 2010 Mathematics Subject Classification 05D05 Abstract The trace of a family of sets A on a set X is A x A Cl X A G A . If A is a family of k-sets from an n-set such that for any r-subset X the trace A x does not contain a maximal chain then how large can A be Patkos conjectured that for n sufficiently large the size of A is at most ra-k r-1 . Our aim in this paper is to prove this conjecture. 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 c X A G A . Vapnik and Chervonenkis 8 Sauer 6 and Shelah 7 independently showed that if A c P n is a family with more than k Q n 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 c 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 Ac n k is a family with more than k- J 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 Patkos 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 c X1 c X2. c Xr X where Xj i for all i. He proved in 5 that if A c P n is a family with more Department of Pure Mathematics and Mathematical Statistics Centre for Mathematical Sciences University of Cambridge Wilberforce Road Cambridge CB3 0WB United Kingdom. Email . THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N16 1 than E - nn sets then there is a k-subset X of n such that the trace A x contains a maximal chain of X .
