Erdős-Ko-Rado theorem with conditions on the maximal degree (Q1112818)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Erdős-Ko-Rado theorem with conditions on the maximal degree |
scientific article; zbMATH DE number 4079426
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Erdős-Ko-Rado theorem with conditions on the maximal degree |
scientific article; zbMATH DE number 4079426 |
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