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
    0 references
    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

    Identifiers