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