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


A new short proof of a theorem of Ahlswede and Khachatrian
Authors:  zsef Balogh,Dhruv Mubayi
Affiliation:a Department of Mathematics, University of Illinois, Urbana, IL 61801, USA
b Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL 60607, USA
Abstract:
Ahlswede and Khachatrian [R. Ahlswede, L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Theory Ser. A 76 (1996) 121-138] proved the following theorem, which answered a question of Frankl and Füredi [P. Frankl, Z. Füredi, Nontrivial intersecting families, J. Combin. Theory Ser. A 41 (1986) 150-153]. Let 2?t+1?k?2t+1 and n?(t+1)(kt+1). Suppose that F is a family of k-subsets of an n-set, every two of which have at least t common elements. If |?FFF|<t, then View the MathML source, and this is best possible. We give a new, short proof of this result. The proof in [R. Ahlswede, L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Theory Ser. A 76 (1996) 121-138] requires the entire machinery of the proof of the complete intersection theorem, while our proof uses only ordinary compression and an earlier result of Wilson [R.M. Wilson, The exact bound in the Erd?s-Ko-Rado theorem, Combinatorica 4 (1984) 247-257].
Keywords:Nontrivial intersecting family   Compression   Extremal set theory
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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