Erdős–Ko–Rado theorem

Paul Erdős, Chao Ko, and Richard Rado proved the theorem in 1938, but did not publish it until 1961.

It is part of the field of combinatorics, and one of the central results of extremal set theory.

The Erdős–Ko–Rado theorem can also be described in terms of hypergraphs or independent sets in Kneser graphs.

Several analogous theorems apply to other kinds of mathematical object than sets, including linear subspaces, permutations, and strings.

The theorem thus gives an upper bound for the number of pairwise overlapping hyperedges in an

[5] Paul Erdős, Chao Ko, and Richard Rado proved this theorem in 1938 after working together on it in England.

Rado had moved from Berlin to the University of Cambridge and Erdős from Hungary to the University of Manchester, both escaping the influence of Nazi Germany; Ko was a student of Louis J. Mordell at Manchester.

[6] The 1961 paper stated the result in an apparently more general form, in which the subsets were only required to be size at most

-element sets whose size exactly matches the Erdős–Ko–Rado bound is to choose any fixed element

In this case, a family of nearly-maximum size has an element which is common to almost all of its sets.

[14] This property has been called stability,[13] although the same term has also been used for a different property, the fact that (for a wide range of parameters) deleting randomly-chosen edges from the Kneser graph does not increase the size of its independent sets.

[18] Projective planes produce maximal intersecting families whose number of sets is

This result is called the Hilton–Milner theorem, after its proof by Anthony Hilton and Eric Charles Milner in 1967.

, follows easily from the facts that an intersecting family cannot include both a set and its complement, and that in this case the bound of the Erdős–Ko–Rado theorem is exactly half the number of all

[20] In 1972, Gyula O. H. Katona gave the following short proof using double counting.

[23] A generalization of the theorem applies to subsets that are required to have large intersections.

large enough with respect to the other two parameters, the generalized theorem states that the size of a

[29] Many results analogous to the Erdős–Ko–Rado theorem, but for other classes of objects than finite sets, are known.

These generally involve a statement that the largest families of intersecting objects, for some definition of intersection, are obtained by choosing an element and constructing the family of all objects that include that chosen element.

Examples include the following: There is a q-analog of the Erdős–Ko–Rado theorem for intersecting families of linear subspaces over finite fields.

In this case, a largest intersecting family of subspaces may be obtained by choosing any nonzero vector and constructing the family of subspaces of the given dimension that all contain the chosen vector.

-element permutations correspond to the perfect matchings of a complete bipartite graph

and the theorem states that, among families of perfect matchings each pair of which share

[32] Another analog of the theorem, for partitions of a set, includes as a special case the perfect matchings of a complete graph

The largest family of matchings that pairwise intersect (meaning that they have an edge in common) has size

and is obtained by fixing one edge and choosing all ways of matching the remaining

[36] An unproven conjecture, posed by Gil Kalai and Karen Meagher, concerns another analog for the family of triangulations of a convex polygon with

, and the conjecture states that a family of triangulations every pair of which shares an edge has maximum size

may be obtained by cutting off a single vertex of the polygon by a triangle, and choosing all ways of triangulating the remaining

[38] The stability properties of the Erdős–Ko–Rado theorem play a key role in an efficient algorithm for finding monochromatic edges in improper colorings of Kneser graphs.

Two intersecting families of two-element subsets of a four-element set. The sets in the left family all contain the bottom left element. The sets in the right family avoid this element.
The Kneser graph , with a vertex for each 2-element subset of the 5-element set {1,2,3,4,5} and an edge for each pair of disjoint subsets. According to the Erdős–Ko–Rado theorem, the independent sets in this graph have at most four vertices.
The Johnson graph , with a vertex for each two-element subset of {1,2,3,4} and an edge connecting intersecting pairs of subsets, arranged geometrically as an octahedron with disjoint sets at opposite vertices. The largest intersecting families for and come from the triangular faces of this octahedron. Replacing a set in one of these families by its complement corresponds to moving from a triangle to one of its three neighboring triangles.
The seven points and seven lines (one drawn as a circle) of the Fano plane form a maximal intersecting family.