thumb|upright=1.2|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.
In mathematics, the Erdős–Ko–Rado theorem limits the number of sets in a family of sets for which every two sets have at least one element in common. 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
The theorem applies to families of sets that all have the same and are all subsets of some larger set of size One way to construct a family of sets with these parameters, each two sharing an element, is to choose a single element to belong to all the subsets, and then form all of the subsets of that contain the chosen element. The Erdős–Ko–Rado theorem states that when <math>n</math> is large enough for the problem to be nontrivial this construction produces the largest possible intersecting families. When <math>n=2r</math> there are other equally-large families, but for larger values of <math>n</math> only the families constructed in this way can be largest.
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. They again describe the largest possible intersecting families as being formed by choosing an element and forming the family of all objects that contain the chosen element.
Statement
Suppose that <math>\mathcal{A}</math> is a family of distinct subsets of an set and that each two subsets share at least one element. Then the theorem states that the number of sets in <math>\mathcal{A}</math> is at most the binomial coefficient
<math display=block>\binom{n-1}{r-1}.</math>
The requirement that <math>n\ge 2r</math> is necessary for the problem to be nontrivial: all sets intersect, and the largest intersecting family consists of all sets, with
The same result can be formulated as part of the theory of hypergraphs. A family of sets may also be called a hypergraph, and when all the sets (which are called "hyperedges" in this context) are the same it is called an hypergraph. The theorem thus gives an upper bound for the number of pairwise overlapping hyperedges in an hypergraph with
thumb|The Kneser graph <math>KG_{5,2}</math>, 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 set (graph theory)|independent sets in this graph have at most four vertices.]]
The theorem may also be formulated in terms of graph theory: the independence number of the Kneser graph <math>KG_{n,r}</math> for <math>n\ge 2r</math> is
<math display=block>\alpha(KG_{n,r})=\binom{n-1}{r-1}.</math>
This is a graph with a vertex for each subset of an set, and an edge between every pair of disjoint sets. An independent set is a collection of vertices that has no edges between its pairs, and the independence number is the size of the largest Because Kneser graphs have symmetries taking any vertex to any other vertex (they are vertex-transitive graphs), their fractional chromatic number equals the ratio of their number of vertices to their independence number, so another way of expressing the Erdős–Ko–Rado theorem is that these graphs have fractional chromatic number
History
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 However, they did not publish the result A family of subsets meeting these conditions can be enlarged to subsets of size either by an application of or by choosing each enlarged subset from the same chain in a symmetric chain decomposition
Maximum and maximal families
Families of maximum size
thumb|The [[Johnson graph <math>J(4,2)</math>, 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 <math>r=2</math> and <math>n=2r=4</math> 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.]]
A simple way to construct an intersecting family of sets whose size exactly matches the Erdős–Ko–Rado bound is to choose any fixed and let <math>\mathcal{A}</math> consist of all subsets that For instance, for 2-element subsets of the 4-element this produces the family
Any two sets in this family intersect, because they both The number of sets is <math>\tbinom{n-1}{r-1}</math>, because after the fixed element is chosen there remain <math>n-1</math> other elements to choose, and each set chooses <math>r-1</math> of these remaining elements.
When <math>n>2r</math> this is the only intersecting family of this size. However, when <math>n=2r</math>, there is a more general construction. Each set can be matched up to its complement, the only set from which it is disjoint. Then, choose one set from each of these complementary pairs. For instance, for the same parameters above, this more general construction can be used to form the family
where every two sets intersect despite no element belonging to all three sets. In this example, all of the sets have been complemented from the ones in the first example, but it is also possible to complement only some of the sets.
families of the first type (variously known as stars, dictatorships, juntas, centered families, or principal families) are the unique maximum families. In this case, a family of nearly-maximum size has an element which is common to almost all of its This property has been called 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
Maximal intersecting families
thumb|240px|The seven points and seven lines (one drawn as a circle) of the [[Fano plane form a maximal intersecting family.]]
An intersecting family of sets may be maximal, in that no further set can be added (even by extending the ground set) without destroying the intersection property, but not of maximum size. An example with <math>n=7</math> and <math>r=3</math> is the set of seven lines of the Fano plane, much less than the Erdős–Ko–Rado bound More generally, the lines of any finite projective plane of order <math>q</math> form a maximal intersecting family that includes only <math>n</math> sets, for the parameters <math>r=q+1</math> The Fano plane is the case <math>q=2</math> of this construction.
The smallest possible size of a maximal intersecting family of sets, in terms is unknown but at least <math>3r</math> Projective planes produce maximal intersecting families whose number of sets but for infinitely many choices of <math>r</math> there exist smaller maximal intersecting families of
The largest intersecting families of sets that are maximal but not maximum have size <math display=block>\binom{n-1}{r-1}-\binom{n-r-1}{r-1}+1.</math>
They are formed from an and an not by adding <math>Y</math> to the family of sets that include both <math>x</math> and at least one element This result is called the Hilton–Milner theorem, after its proof by Anthony Hilton and Eric Charles Milner in
Proofs
The original proof of the Erdős–Ko–Rado theorem used induction The base case, 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 sets. The induction step for uses a method called shifting, of substituting elements in intersecting families to make the family smaller in lexicographic order and reduce it to a canonical form that is easier to
In 1972, Gyula O. H. Katona gave the following short proof using