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 .

TÀI LIỆU LIÊN QUAN
32    57    0
45    42    0
6    65    0
4    53    0
6    55    0
6    52    0
6    45    0
5    59    0
7    58    0
6    64    0
TÀI LIỆU XEM NHIỀU
13    32501    1652
3    19368    204
25    18669    3690
20    16766    1477
16    15853    2496
14    14337    2540
37    13050    2802
1    11359    401
3    10974    211
23    10566    384
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
6    7    1    06-07-2022
7    14    1    06-07-2022
5    89    1    06-07-2022
3    2    1    06-07-2022
69    2    1    06-07-2022
6    12    1    06-07-2022
336    15    1    06-07-2022
49    15    1    06-07-2022
11    16    1    06-07-2022
158    21    1    06-07-2022
88    2    1    06-07-2022
22    13    1    06-07-2022
9    34    1    06-07-2022
8    2    1    06-07-2022
11    20    1    06-07-2022
1    2    1    06-07-2022
6    10    1    06-07-2022
9    108    2    06-07-2022
11    22    1    06-07-2022
10    12    1    06-07-2022
TÀI LIỆU HOT
3    19368    204
13    32501    1652
3    1505    75
580    3634    345
584    1964    81
62    4389    1
171    3992    621
2    1750    72
51    2480    150
53    3344    175
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.