A new short proof of a theorem of Ahlswede and Khachatrian (Q2474500)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5243727
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A new short proof of a theorem of Ahlswede and Khachatrian |
scientific article; zbMATH DE number 5243727 |
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
0.833817720413208
0 references
0.833817720413208
0 references
0.8212506771087646
0 references
0.8105388879776001
0 references
0.8092457056045532
0 references