
In mathematics, the Erdős–Ko–Rado theorem limits the number of
sets in a
family of sets
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set fa ...
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
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
, 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 that contain the chosen element. The Erdős–Ko–Rado theorem states that when
is large enough for the problem to be nontrivial this construction produces the largest possible intersecting families. When
there are other equally-large families, but for larger values of
only the families constructed in this way can be largest.
The Erdős–Ko–Rado theorem can also be described in terms of
hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) ...
s or
independent sets in
Kneser graphs. Several analogous theorems apply to other kinds of mathematical object than sets, including
linear subspaces,
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...
s, 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
is a family of distinct
subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...
s of an set and that each two subsets share at least one element. Then the theorem states that the number of sets in
is at most the
binomial coefficient
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
The requirement that
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
hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) ...
s. 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

The theorem may also be formulated in terms of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
: the
independence number
Independence is a condition of a person, nation, country, or Sovereign state, state in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independ ...
of the
Kneser graph for
is
This is a graph with a vertex for each subset of an set, and an edge between every pair of
disjoint sets
In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. ...
. 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 graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism
:f : G \to G\
such that
:f(v_1) = v_2.\
In other words, a graph is vertex-transitive ...
s), 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
, mottoeng = Literal: From here, light and sacred draughts.
Non literal: From this place, we gain enlightenment and precious knowledge.
, established =
, other_name = The Chancellor, Masters and Schola ...
and Erdős from Hungary to the
University of Manchester
The University of Manchester is a public university, public research university in Manchester, England. The main campus is south of Manchester city centre, Manchester City Centre on Wilmslow Road, Oxford Road. The university owns and operates majo ...
, both escaping the influence of Nazi Germany; Ko was a student of
Louis J. Mordell
Louis Joel Mordell (28 January 1888 – 12 March 1972) was an American-born British mathematician, known for pioneering research in number theory. He was born in Philadelphia, United States, in a Jewish family of Lithuanian extraction.
Educatio ...
at However, they did not publish the result with the long delay occurring in part because of a lack of interest in combinatorial set theory in the 1930s, and increased interest in the topic in The 1961 paper stated the result in an apparently more general form, in which the subsets were only required to be size and to satisfy the additional requirement that no subset be contained in any 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

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
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
, because after the fixed element is chosen there remain
other elements to choose, and each set chooses
of these remaining elements.
When
this is the only intersecting family of this size. However, when
, there is a more general construction. Each set can be matched up to its
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-clas ...
, 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

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
and
is the set of seven lines of the
Fano plane
In finite geometry, the Fano plane (after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and lines ...
, much less than the Erdős–Ko–Rado bound More generally, the lines of any
finite projective plane of order
form a maximal intersecting family that includes only
sets, for the parameters
The Fano plane is the case
of this construction.
The smallest possible size of a maximal intersecting family of sets, in terms is unknown but at least
Projective planes produce maximal intersecting families whose number of sets but for infinitely many choices of
there exist smaller maximal intersecting families of
The largest intersecting families of sets that are maximal but not maximum have size
They are formed from an and an not by adding
to the family of sets that include both
and at least one element This result is called the Hilton–Milner theorem, after its proof by
Anthony Hilton
Anthony J. W. Hilton (born 4 April 1941) is a British mathematician specializing in combinatorics and graph theory. His current positions are as emeritus professor of Combinatorial Mathematics at the University of Reading and professorial research ...
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
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-clas ...
, 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
In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of ...
and reduce it to a canonical form that is easier to
In 1972,
Gyula O. H. Katona
Gyula O. H. Katona (born 16 March 1941 in Budapest) is a Hungarian mathematician known for his work in combinatorial set theory, and especially for the Kruskal–Katona theorem and his beautiful and elegant proof of the Erdős–Ko–Rado the ...
gave the following short proof using
It is also possible to derive the Erdős–Ko–Rado theorem as a special case of the
Kruskal–Katona theorem, another important result in Many other proofs are
Related results
Generalizations
A generalization of the theorem applies to subsets that are required to have large intersections. This version of the theorem has three parameters:
, the number of elements the subsets are drawn from,
, the size of the subsets, as before, and
, the minimum size of the intersection of any two subsets. For the original form of the Erdős–Ko–Rado theorem, In general, for
large enough with respect to the other two parameters, the generalized theorem states that the size of a family of subsets is at
More precisely, this bound holds and does not hold for smaller values When the only families of this size are obtained by designating as the common intersection of all the subsets, and constructing the family of all subsets that include these
designated
The corresponding graph-theoretic formulation of this generalization involves
Johnson graph
Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph J(n,k) are the k-element subsets of an n-element set; two vertices are adjacent when the intersection of the two vertices (subse ...
s in place of Kneser For large enough values of
and in particular both the Erdős–Ko–Rado theorem and its generalization can be strengthened from the independence number to the
Shannon capacity of a graph: the Johnson graph corresponding to the subsets has Shannon
The theorem can also be generalized to families in which every
subsets have a common intersection. Because this strengthens the condition that every pair intersects (for which these families have the same bound on their maximum size,
when
is sufficiently large. However, in this case the meaning of "sufficiently large" can be relaxed from
Analogs
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
-analog of the Erdős–Ko–Rado theorem for intersecting families of
linear subspaces over
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subt ...
s. If
is an intersecting family of subspaces of an
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but ...
over a finite field of then
where the subscript marks the notation for the
Gaussian binomial coefficient
In mathematics, the Gaussian binomial coefficients (also called Gaussian coefficients, Gaussian polynomials, or ''q''-binomial coefficients) are ''q''-analogs of the binomial coefficients. The Gaussian binomial coefficient, written as \binom ...
, the number of subspaces of a given dimension within a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but ...
of a larger dimension over a finite field of 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
Two
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...
s on the same set of elements are defined to be intersecting if there is some element that has the same image under both permutations. On an set, there is an obvious family of
intersecting permutations, the permutations that fix one of the elements (the
stabilizer subgroup of this element). The analogous theorem is that no intersecting family of permutations can be larger, and that the only intersecting families of size
are the
coset
In mathematics, specifically group theory, a subgroup of a group may be used to decompose the underlying set of into disjoint, equal-size subsets called cosets. There are ''left cosets'' and ''right cosets''. Cosets (both left and right) ...
s of one-element stabilizers. These can be described more directly as the families of permutations that map some fixed element to another fixed element. More generally, for any
and sufficiently large
, a family of permutations each pair of which has
elements in common has maximum size
, and the only families of this size are cosets of pointwise Alternatively, in graph theoretic terms, the permutations correspond to the
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
s of a
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory ...
and the theorem states that, among families of perfect matchings each pair of which share
edges, the largest families are formed by the matchings that all contain
chosen Another analog of the theorem, for
partitions of a set, includes as a special case the perfect matchings of a
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...
(with
even). There are
matchings, where
denotes the
double factorial
In mathematics, the double factorial or semifactorial of a number , denoted by , is the product of all the integers from 1 up to that have the same parity (odd or even) as . That is,
:n!! = \prod_^ (n-2k) = n (n-2) (n-4) \cdots.
For even , the ...
. 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
vertices.
A
partial geometry is a system of finitely many abstract points and lines, satisfying certain axioms including the requirement that all lines contain the same number of points and all points belong to the same number of lines. In a partial geometry, a largest system of pairwise-intersecting lines can be obtained from the set of lines through any single
A
signed set In mathematics, a signed set is a set of elements together with an assignment of a sign (positive or negative) to each element of the set.
Representation
Signed sets may be represented mathematically as an ordered pair of disjoint sets, one set for ...
consists of a set together with sign function that maps each element Two signed sets may be said to intersect when they have a common element that has the same sign in each of them. Then an intersecting family of signed sets, drawn from an universe, consists of at most
signed sets. This number of signed sets may be obtained by fixing one element and its sign and letting the remaining
elements and signs
For
strings of over an
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a s ...
of two strings can be defined to intersect if they have a position where both share the same symbol. The largest intersecting families are obtained by choosing one position and a fixed symbol for that position, and letting the rest of the positions vary arbitrarily. These families consist of
strings, and are the only pairwise intersecting families of this size. More generally, the largest families of strings in which every two have
positions with equal symbols are obtained by choosing
positions and symbols for those positions, for a number
that depends on
,
, and
, and constructing the family of strings that each have at least
of the chosen symbols. These results can be interpreted graph-theoretically in terms of the
An unproven
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 1 ...
, posed by
Gil Kalai and Karen Meagher, concerns another analog for the family of triangulations of a
convex polygon
In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a ...
with
vertices. The number of all triangulations is a and the conjecture states that a family of triangulations every pair of which shares an edge has maximum An intersecting family of size exactly
may be obtained by cutting off a single vertex of the polygon by a triangle, and choosing all ways of triangulating the remaining polygon.
Applications
The Erdős–Ko–Rado theorem can be used to prove the following result in
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
. Let
be independent
0–1 random variables with probability
of being one, and let
be any fixed
convex combination
In convex geometry and vector algebra, a convex combination is a linear combination of points (which can be vectors, scalars, or more generally points in an affine space) where all coefficients are non-negative and sum to 1. In other ...
of these variables. Then
The proof involves observing that subsets of variables whose
indicator vectors have large convex combinations must be non-disjoint and using the Erdős–Ko–Rado theorem to bound the number of these
The stability properties of the Erdős–Ko–Rado theorem play a key role in an efficient
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for finding monochromatic edges in
improper colorings of Kneser graphs. The Erdős–Ko–Rado theorem has also been used to characterize the symmetries of the space of
phylogenetic trees.
See also
*
Helly's theorem, on conditions ensuring that intersecting families of convex sets have a common intersection
*
Sperner's theorem, an upper bound on families of pairwise non-nested sets
*
Steiner system, maximum-sized uniform set families in which no pair (rather than every pair) has a large intersection
*
Sunflower (mathematics)
In the mathematical fields of set theory and extremal combinatorics, a sunflower or \Delta-system is a collection of sets whose pairwise intersection is constant. This constant intersection is called the kernel of the sunflower.
The main re ...
, a family of sets where (unlike the maximum intersecting families here) all pairs have equal intersections
*
Thrackle A thrackle is an embedding of a graph in the plane, such that each edge is a Jordan arc
and every pair of edges meet exactly once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. ...
, an unsolved problem on the size of families of intersecting curves
References
Notes
Works cited
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
External links
*
{{DEFAULTSORT:Erdos-Ko-Rado theorem
Families of sets
Intersection
Theorems in discrete mathematics
Articles containing proofs
Factorial and binomial topics
Ko-Rado theorem