Erdös–Ko–Rado Theorem—22 Years Later

Abstract

In 1961 Erdös, Ko, and Rado proved that, if a family $\mathcal{F}$ of k-subsets of an n-set is such that any 2 sets have at least l elements in common, then for n large enough $| \mathcal{F} | \leqq \begin{pmatrix} {n - l} \\ {k - l} \end{pmatrix}$. This result had great impact on combinatorics. Here we give a survey of known and of some new generalizations and analogues of this theorem. We consider mostly problems which were not included or were touched very briefly in the survey papers [17], [46], [51], [61].