TAILIEUCHUNG - Báo cáo toán học: "Traces Without Maximal Chains"

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 .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học