The exact bound in the Erdős-Ko-Rado theorem (Q761464)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The exact bound in the Erdős-Ko-Rado theorem
scientific article

    Statements

    The exact bound in the Erdős-Ko-Rado theorem (English)
    0 references
    1984
    0 references
    The Erdős-Ko-Rado theorem states that if F is a family of k-subsets of an n-set, \(| A\cap B| \geq t\) holds for \(A,B\in F,\) then \(| F| \leq \left( \begin{matrix} n-t\\ k-t\end{matrix} \right)\) for \(n\geq n_ 0.\) [\textit{P. Erdős}, \textit{C. Ko} and \textit{R. Rado}, Quart. J. Math., Oxford II. Ser. 12, 313-320 (1961; Zbl 0100.019).] The rather poor upper bound for \(n_ 0\) was improved by \textit{P. Frankl} to \(n_ 0=(t+1)(k-t+1)\) if \(t\geq 15\), and \(n_ 0=0(t(k-t))\) for all t [Combinatorics, Keszthely 1976, Colloq. Math. Soc. János Bolyai 18, 365-375 (1978; Zbl 0401.05001)]. In this paper it is shown that Frankl's estimate holds for all t. If \(n>n_ 0\) then there is only one extremal family. Extending former research by P. Frankl and A. Schrijver the author uses linear algebraic methods with some lengthy calculation of eigenvalues.
    0 references
    extremal set systems
    0 references
    Erdős-Ko-Rado theorem
    0 references
    extremal family
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references