Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Minimal weight in union-closed families"

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: Minimal weight in union-closed families. | Minimal weight in union-closed families Victor Falgas-Ravry School of Mathematical Sciences Queen Mary University of London London E1 4NS UK v.f algas-ravry@qmul.ac.uk Submitted Nov 8 2010 Accepted Apr 12 2011 Published Apr 21 2011 Mathematics Subject Classification 05D05 Abstract Let Q be a finite set and let S c P Q be a set system on Q. For x E Q we denote by ds x the number of members of S containing x. A long-standing conjecture of Frankl states that if S is union-closed then there is some x E Q with ds x 2 S . We consider a related question. Define the weight of a family S to be w S VasS A . Suppose S is union-closed. How small can w S be Reimer showed w S 1 S log2 S and that this inequality is tight. In this paper we show how Reimer s bound may be improved if we have some additional information about the domain Q of S if S separates the points of its domain then w S Q . This is stronger than Reimer s Theorem when Q Ự S log2 S . In addition we construct a family of examples showing the combined bound on w S is tight except in the region Q y S log2 S where it may be off by a multiplicative factor of 2. Our proof also gives a lower bound on the average degree if S is a pointseparating union-closed family on Q then tQt ds x 1 V S log2 S O 1 I I xeQ and this is best possible except for a multiplicative factor of 2. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P95 1 1 Introduction Let Q be a finite set. We may identify X c Q with its characteristic function and consider a collection of subsets of Q as a family of functions from Q into 0 1 . For such a family S c P Q we refer to Q Q S as the domain of S. Note that the domain of a set system S is not uniquely determined by knowledge S. Therefore when we speak of a set system S we shall in fact mean a pair S Q where S c P Q so that the domain of S is implicitly specified. We also let V S JAes A be the set of all elements x G Q which appear as a member of at least one set A G S. For x G Q we denote by ds x the .