کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655952 1343411 2009 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On averaging Frankl's conjecture for large union-closed-sets
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On averaging Frankl's conjecture for large union-closed-sets
چکیده انگلیسی

Let F be a union-closed family of subsets of an m-element set A. Let n=|F|⩾2 and for a∈A let s(a) denote the number of sets in F that contain a. Frankl's conjecture from 1979, also known as the union-closed sets conjecture, states that there exists an element a∈A with n−2s(a)⩽0. Strengthening a result of Gao and Yu [W. Gao, H. Yu, Note on the union-closed sets conjecture, Ars Combin. 49 (1998) 280–288] we verify the conjecture for the particular case when m⩾3 and n⩾m2−2m/2. Moreover, for these “large” families F we prove an even stronger version via averaging. Namely, the sum of the n−2s(a), for all a∈A, is shown to be non-positive. Notice that this stronger version does not hold for all union-closed families; however we conjecture that it holds for a much wider class of families than considered here. Although the proof of the result is based on elementary lattice theory, the paper is self-contained and the reader is not assumed to be familiar with lattices.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 116, Issue 3, April 2009, Pages 724-729