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)(k−t+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 |?F∈FF|<t, then , 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 等数据库收录! |
|