TAILIEUCHUNG - Báo cáo toán học: " A NEW CONSTRUCTION FOR CANCELLATIVE FAMILIES OF SETS"

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í toán học quốc tế đề tài: A NEW CONSTRUCTION FOR CANCELLATIVE FAMILIES OF SETS. | A NEW CONSTRUCTION FOR CANCELLATIVE FAMILIES OF SETS James B. Shearer IBM Research Division . Watson Research Center . Box 218 Yorktown Heights NY 10598 email jbs@ Submitted March 25 1996 Accepted April 20 1996 Abstract. Following 2 we say a family H of subsets of a n-element set is can-cellative if A u B A u C implies B C when A B C 2 H. We show how to construct cancellative families of sets with c2 54797n elements. This improves the previous best bound c2 52832n and falsifies conjectures of Erdos and Katona 3 and Bollobas 1 . AMS Subject Classification. 05C65 We will look at families of subsets of a n-set with the property that A u B A u C B C for any A B C in the family. Frankl and Furedi 2 call such families cancellative. We ask how large cancellative families can be. We define f n to be the size of the largest possible cancellative family of subsets of a n-set and f k n to be the size of the largest possible cancellative family of k-subsets of a n-set. Note the condition A u B A u C B C is the same as the condition B4C c A B C where 4 denotes the symmetric difference. Let F1 be a family of subsets of a nl -set Sl. Let F2 be a family of subsets of a n2-set S2. We define the product Fl X F2 to be the family of subsets of the nl n2 -set Sl u S2 whose members consist of the union of any element of Fl with any element of F2. It is easy to see that the product of two cancellative families is also a cancellative family Al A2 u Bl B2 Al A u Cl C2 Al u Bl A2 u B2 Al u Cl A2 u C2 Al u Bl Al u Cl and A 2 u B2 A 2 u C2 Bl Cl and B2 C2 Bl B2 Cl C2 . Hence f nl n2 f nl f n2 . Similarly f kl k2 nl n2 f kl nl f k2 n2 . Typeset by Ạ 5-TpX 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 3 1996 R 15 2 It is easy to show that f n1 n2 f n1 f n2 implies that limn_ 1 nlg f n exists Ig means log base 2 . Let this limit be a. Note that a nIg f n for any hxed n. Clearly f 1 n n as we may take all the 1-element sets. Let Hn be the family of all 1-element sets of a n-set. .

• Báo cáo khoa học
• 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
• các bài toán hay
• trình bày báo cáo
• báo cáo ngành văn học
• báo cáo tiếng anh
• nghiên cứu văn thơ
• giọng điệu trào phúng
• nghiên cứu khoa học
• báo cáo khoa học
• thơ lục bát
• chính sách phát triển
• gia đình việt nam
• nghiên cứu xã hội