首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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,DF with |ABCD|?2r, we have ABCD≠∅. We prove that for n sufficiently large, View the MathML source, with equality only if ?FFF≠∅. 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 View the MathML source then F is close to satisfying ?FFF≠∅. The stability theorem is analogous to, and motivated by the fundamental result of Erd?s and Simonovits for graphs.
Keywords:05C35  05C65  05D05
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号