Erdős-Ko-Rado theorem for a restricted universe

Peter Frankl

The electronic journal of combinatorics, Tome 27 (2020) no. 2

Résumé

A family $\mathcal F$ of $k$-element subsets of the $n$-element set $[n]$ is called \emph{intersecting} if $F \cap F'\neq \emptyset$ for all $F, F' \in \mathcal F$. In 1961 Erdős, Ko and Rado showed that $|\mathcal F| \leq {n - 1\choose k - 1}$ if $n \geq 2k$. Since then a large number of resultső providing best possible upper bounds on $|\mathcal F|$ under further restraints were proved. The paper of Li et al. is one of them. We consider the restricted universe $\mathcal W = \left\{F \in {[n]\choose k}: |F \cap [m]| \geq \ell \right\}$, $n \geq 2k$, $m \geq 2\ell$ and determine $\max |\mathcal F|$ for intersecting families $\mathcal F \subset \mathcal W$. Then we use this result to solve completely the problem considered by Li et al.

Détail

DOI : 10.37236/8682

Classification : 05D05
Mots-clés : restricted universe, intersecting family of subsets