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

1983/12/01 by Michel Deza, Péter Frankl · 3 citations
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics #Discrete mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Mathematics

paper · doi:10.1137/0604042

openalex publication_date 1983/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

In 1961 Erdös, Ko, and Rado proved that, if a family 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 | F | \leqq \beginpmatrix n - l k - l \endpmatrix. 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].

Citations

• A simple proof of the Erdös-Chao Ko-Rado theorem
• On the maximum number of permutations with given maximal or minimal distance
• Intersection theorems with geometric consequences
• On Sperner families satisfying an additional condition
• A generalization of a combinatorial theorem of macaulay
• Solution d'un problème de Erdös-Lovász
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS

Cited by

• The Erdös-Ko-Rado theorem for vector spaces
• A new proof of the Erdős–Ko–Rado theorem for intersecting families of permutations
• Erdős–Ko–Rado theorem [wikipedia]