An intersection theorem for four sets |
| |
Authors: | Dhruv Mubayi |
| |
Institution: | Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, 851 S. Morgan Street, Chicago, IL 60607-7045, USA |
| |
Abstract: | 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. |
| |
Keywords: | 05C35 05C65 05D05 |
本文献已被 ScienceDirect 等数据库收录! |
|