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