Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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: On a Conjecture of Frankl and F¨redi u. | On a Conjecture of Frankl and Fiiredi Ameera Chowdhury Submitted Nov 8 2010 Accepted Feb 27 2011 Published Mar 11 2011 Mathematics Subject Classification 05D05 Abstract Frankl and Furedi conjectured that if F c 2X is a non-trivial A-intersecting family of size m then the number of pairs x y E X that are contained in some F E F is at least m P. Frankl and Z. Furedi. A Sharpening of Fisher s Inequality. Discrete Math. 90 1 103-107 1991 . We verify this conjecture in some special cases focusing especially on the case where F is additionally required to be k-uniform and A is small. 1 Introduction Let X be an n-element set and let 2X denote the family of all subsets of X. For 0 k n let X denote the family of all subsets of X of cardinality k. For a family F c 2X we define the i-shadow of F denoted BZF to consist of those i-subsets of X contained in at least one member of F BiF E E X E c F E F ị . i A family F c 2X is called A-intersecting if we have F1 n F2 A for any distinct F1 F2 E F. The well-known Fisher s Inequality states that if F is a A-intersecting family of size m then Ỡ1F m. Inspired by Fisher s Inequality Frankl and Furedi 7 conjectured a similar inequality for Ỡ2F . Conjecture 1.1 easily implies Fisher s Inequality since f1 2F Ợm proves Ỡ1F m. Conjecture 1.1 Frankl-Furedi 1991 Let F c 2X be a A-intersecting family of size m. If there does not exist x E X such that x E F for all F E F then d2F m . Department of Mathematics University of California San Diego La Jolla CA 92093 USA. E-mail anchowdh@math.ucsd.edu THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P56 1 Frankl and Fiiredi 7 verified Conjecture 1.1 when A 1. While this paper appears to be the first to consider Conjecture 1.1 since 7 several special cases of Conjecture 1.1 had already been proved before 7 was published. For example Ryser 13 Woodall 16 and Babai 1 showed Conjecture 1.1 is true when m n. Majindar 11 proved Conjecture 1.1 for regular A-intersecting families. Notation We say F is .
