TY - JOUR

T1 - A new short proof of a theorem of Ahlswede and Khachatrian

AU - Balogh, József

AU - Mubayi, Dhruv

N1 - Funding Information:
1 Research supported in part by NSF grants DMS-0603769 and DMS-0600303, UIUC Campus Research Board #06139, and OTKA 049398. 2 Research supported in part by NSF grant DMS-0400812 and an Alfred P. Sloan Research Fellowship.

PY - 2008/2

Y1 - 2008/2

N2 - 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 ≤ 2 t + 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 | {n-ary intersection}F ∈ F F | < t, then | F | ≤ (t + 2) ((n - t - 2; k - t - 1)) + ((n - t - 2; k - t - 2)), 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 Erdo{combining double acute accent}s-Ko-Rado theorem, Combinatorica 4 (1984) 247-257].

AB - 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 ≤ 2 t + 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 | {n-ary intersection}F ∈ F F | < t, then | F | ≤ (t + 2) ((n - t - 2; k - t - 1)) + ((n - t - 2; k - t - 2)), 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 Erdo{combining double acute accent}s-Ko-Rado theorem, Combinatorica 4 (1984) 247-257].

KW - Compression

KW - Extremal set theory

KW - Nontrivial intersecting family

UR - http://www.scopus.com/inward/record.url?scp=41749088051&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=41749088051&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2007.03.010

DO - 10.1016/j.jcta.2007.03.010

M3 - Article

AN - SCOPUS:41749088051

SN - 0097-3165

VL - 115

SP - 326

EP - 330

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

IS - 2

ER -