Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4667578 | Advances in Mathematics | 2007 | 15 Pages |
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.