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

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.