Erdős-Ko-Rado theorem with conditions on the maximal degree (Q1112818)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Erdős-Ko-Rado theorem with conditions on the maximal degree
scientific article

    Statements

    Erdős-Ko-Rado theorem with conditions on the maximal degree (English)
    0 references
    1987
    0 references
    A family \({\mathcal F}\) of distinct k-element subsets of the n-element set X is called intersecting if \(F\cap F'\neq \emptyset\) holds for all F, F'\(\in {\mathcal F}\). Erdős, Ko, and Rado proved that for \(n\geq 2k\) necessarily \(| {\mathcal F}| \leq \left( \begin{matrix} n-1\\ k-1\end{matrix} \right)\) holds, which is clearly best possible (take all k-sets through a fixed element). For a family \({\mathcal F}\), its maximum degree d(\({\mathcal F})\) is the maximum number of sets in \({\mathcal F}\) containing any particular element of X. For \(3\leq i\leq k+1\) define intersecting families \({\mathcal F}_ i\) as follows. Let \(x\not\in I\in \left( \begin{matrix} X\\ i-1\end{matrix} \right)\) and set \({\mathcal F}_ i=\{F\in \left( \begin{matrix} X\\ k\end{matrix} \right):\) \(x\in F\), \(F\cap I\neq \emptyset \}\cup \{F\in \left( \begin{matrix} X\\ k\end{matrix} \right):\) \(x\not\in F\), \(I\subset F\}\). The main result of the present paper is: if \({\mathcal F}\subset \left( \begin{matrix} X\\ k\end{matrix} \right)\) is intersecting, d(\({\mathcal F})\leq d({\mathcal F}_ i)\) and \(n\geq 2k\), then \(| {\mathcal F}| \leq | {\mathcal F}_ i|\) holds.
    0 references
    distinct subsets
    0 references
    maximum degree
    0 references
    intersecting families
    0 references
    0 references

    Identifiers