Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "The 11-element case of Frankl’s conjecture"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: The 11-element case of Frankl’s conjecture. | The 11-element case of Frankl s conjecture Ivica Bosnjak and Petar Markovic Department of Mathematics and Informatics University of Novi Sad Serbia ivb@im.ns.ac.yu pera@im.ns.ac.yu Submitted Jan 24 2007 Accepted Jun 27 2008 Published Jul 6 2008 Mathematics Subject Classifications primary 05D05 secondary 05A05 Abstract In 1979 P. Frankl conjectured that in a finite union-closed family F of finite sets F 0 there has to be an element that belongs to at least half of the sets in F. We prove this when I S F 11. 1 Introduction Frankl s conjecture 9 sometimes also called the union-closed sets conjecture is one of the most celebrated open problems in combinatorics. In 10 it is referred to as diabolical presumably since it has an elementary even trivial statement but seems to be quite difficult. In its original statement the conjecture is that in a finite union-closed family F of finite sets F 0 there has to be an element that belongs to at least half of the sets in F. Several equivalents have been found in various areas of mathematics the most popular of which is probably the lattice-theoretic one see 10 Chapter 3 Problem 39a . Recently there have been quite a few new partial results concerning the original version of the problem see for instance 2 3 6 7 11 12 13 . Many of these papers are using the idea introduced first in 8 Theorem 1. This is a way for rapid verification of the conjecture for a large class of union-closed families using a weight function. We use a similar approach introduced in 6 . The main difference is that Theorem 1 of 8 gives a necessary and sufficient condition for a subfamily F0 to force that an element of u F0 is in at least half of the sets of F for any F D F0 such F0 are called FC families in 11 while our easier Lemma 2.1 gives a necessary and sufficient condition for F to satisfy Frankl s Conjecture. We are able to use our approach to prove that any counterexample F to Frankl s Conjecture must satisfy I klF 12. The second author was supported .