A new short proof of a theorem of Ahlswede and Khachatrian (Q2474500)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new short proof of a theorem of Ahlswede and Khachatrian |
scientific article |
Statements
A new short proof of a theorem of Ahlswede and Khachatrian (English)
0 references
6 March 2008
0 references
This paper gives a new, short proof for the nontrivial intersection theorem of Ahlswede and Khachatrian (conjectured originally by Frankl and Füredi): Let \(2\leq t+1\leq k \leq 2t+1\) and \(n\geq (t+1)(k-t+1).\) Let \(\mathcal F\) be a \(k\)-uniform \(t\)-intersecting family on an \(n\)-set. If \(| \bigcap_{F\in {\mathcal F}}F| \leq t\) then \(| {\mathcal F}| \leq (t+2){n-t-2 \choose k-t-1} + {n-t-2 \choose k-t-2}.\) The proof is based on the compression method and on Wilson's theorem on the exact bound of the Erdős-Ko-Rado theorem.
0 references
Erdős-Ko-Rado theorem
0 references
compression
0 references
nontrivial intersecting family
0 references