A new generalization of the Erdős-Ko-Rado theorem (Q5916418)

From MaRDI portal
scientific article; zbMATH DE number 3993587
Language Label Description Also known as
English
A new generalization of the Erdős-Ko-Rado theorem
scientific article; zbMATH DE number 3993587

    Statements

    A new generalization of the Erdős-Ko-Rado theorem (English)
    0 references
    0 references
    1986
    0 references
    The author proves the following theorem: If \({\mathcal A}\) and \({\mathcal B}\) are subset systems of a finite set \({\mathcal K}\), satisfying the conditions \(A_ i\cap B_ r\neq \emptyset\), \(A_ i\not\subset A_ j\), \(B_ r\not\subset B_ s\), \(| A_ i| \leq k\), \(| B_ r| \leq m\) for \(A_ i,A_ j\in {\mathcal A}\) and \(B_ r,B_ s\in {\mathcal B}\) then \[ (1)\;if\;k>m,\quad 2k+m-2\leq n\quad then\quad | {\mathcal A}| \cdot | {\mathcal B}| \leq \quad \left( \begin{matrix} n-1\\ k-1\end{matrix} \right)\left( \begin{matrix} n-1\\ m-1\end{matrix} \right), \] \[ (2)\;if\;k=m,\quad 2k\leq n\quad then\quad | {\mathcal A}| \cdot | {\mathcal B}| \leq \quad \left( \begin{matrix} n-1\\ k-1\end{matrix} \right)^ 2. \] The proof uses a method of cyclic permutations.
    0 references
    finite set
    0 references
    Erdős-Ko-Rado theorem
    0 references

    Identifiers