Erdős-Ko-Rado theorem with conditions on the maximal degree
type: Item
instance of: scholarly article
title: Erdős-Ko-Rado theorem with conditions on the maximal degree
zbMATH Open document ID: 0661.05002
DOI: 10.1016/0097-3165(87)90005-7
published in: Journal of Combinatorial Theory. Series A
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 4079426
zbMATH Keywords: distinct subsets
zbMATH Keywords: maximum degree
zbMATH Keywords: intersecting families
Wikidata QID: Q105583667
author: Peter Frankl
MaRDI profile type: Publication
full work available at URL: 0097-3165(87)90005-7
OpenAlex ID: W2153305111
cites work: THE ERDÖS–KO–RADO THEOREM WITH VALENCY CONDITIONS
cites work: Q4134005
cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: On intersecting families of finite sets
cites work: A new short proof for the Kruskal-Katona theorem
cites work: Non-trivial intersecting families
cites work: Finite projective spaces and intersecting hypergraphs
cites work: Q3929742
cites work: An intersection problem with 6 extremes
cites work: Families of finite sets with minimum shadows
cites work: SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: Extremal problems for finite sets and convex hulls---a survey
cites work: Intersection theorems for systems of finite sets
cites work: Q5726070
cites work: A generalization of a theorem of Kruskal
description: scientific article; zbMATH DE number 4079426