کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4667578 1345467 2007 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An intersection theorem for four sets
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات (عمومی)
پیش نمایش صفحه اول مقاله
An intersection theorem for four sets
چکیده انگلیسی

Fix integers n,r⩾4 and let F denote a family of r-sets of an n-element set. Suppose that for every four distinct A,B,C,D∈F with |A∪B∪C∪D|⩽2r, we have A∩B∩C∩D≠∅. We prove that for n sufficiently large, , with equality only if ⋂F∈FF≠∅. This is closely related to a problem of Katona and a result of Frankl and Füredi [P. Frankl, Z. Füredi, A new generalization of the Erdős–Ko–Rado theorem, Combinatorica 3 (3–4) (1983) 341–349], who proved a similar statement for three sets. It has been conjectured by the author [D. Mubayi, Erdős–Ko–Rado for three sets, J. Combin. Theory Ser. A, 113 (3) (2006) 547–550] that the same result holds for d sets (instead of just four), where d⩽r, and for all n⩾dr/(d−1). This exact result is obtained by first proving a stability result, namely that if |F| is close to then F is close to satisfying ⋂F∈FF≠∅. The stability theorem is analogous to, and motivated by the fundamental result of Erdős and Simonovits for graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Mathematics - Volume 215, Issue 2, 10 November 2007, Pages 601-615