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


A new short proof of a theorem of Ahlswede and Khachatrian
Authors:József Balogh  Dhruv Mubayi
Institution: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号