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