Erdős–Ko–Rado theorem

The Johnson graph ${\displaystyle J(4,2)}$, 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 ${\displaystyle r=2}$ and ${\displaystyle n=2r=4}$ 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 ${\displaystyle r}$-element sets whose size exactly matches the Erdős–Ko–Rado bound is to choose any fixed element ${\displaystyle x}$, and let ${\displaystyle {\mathcal {A}}}$ consist of all ${\displaystyle r}$-element subsets that include ${\displaystyle x}$. For instance, for 2-element subsets of the 4-element set ${\displaystyle \{1,2,3,4\}}$, with ${\displaystyle x=1}$, this produces the family

${\displaystyle \{1,2\}}$, ${\displaystyle \{1,3\}}$, and ${\displaystyle \{1,4\}}$.

Any two sets in this family intersect, because they both include ${\displaystyle 1}$. The number of sets is ${\displaystyle {\tbinom {n-1}{r-1}}}$, because after the fixed element is chosen there remain ${\displaystyle n-1}$ other elements to choose, and each set chooses ${\displaystyle r-1}$ of these remaining elements.[10]

When ${\displaystyle n>2r}$ this is the only intersecting family of this size. However, when ${\displaystyle n=2r}$, there is a more general construction. Each ${\displaystyle r}$-element set can be matched up to its complement, the only ${\displaystyle r}$-element 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

${\displaystyle \{3,4\}}$, ${\displaystyle \{2,4\}}$, and ${\displaystyle \{2,3\}}$,

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.[10]

When ${\displaystyle n>2r}$, families of the first type (variously known as stars,[1] dictatorships,[11] juntas,[11] centered families,[12] or principal families[13]) 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 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.[15]

The seven points and seven lines (one drawn as a circle) of the Fano plane form a maximal intersecting family.

An intersecting family of ${\displaystyle r}$-element 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 ${\displaystyle n=7}$ and ${\displaystyle r=3}$ is the set of seven lines of the Fano plane, much less than the Erdős–Ko–Rado bound of 15.[16] More generally, the lines of any finite projective plane of order ${\displaystyle q}$ form a maximal intersecting family that includes only ${\displaystyle n}$ sets, for the parameters ${\displaystyle r=q+1}$ and ${\displaystyle n=q^{2}+q+1}$. The Fano plane is the case ${\displaystyle q=2}$ of this construction.[17]

The smallest possible size of a maximal intersecting family of ${\displaystyle r}$-element sets, in terms of ${\displaystyle r}$, is unknown but at least ${\displaystyle 3r}$ for ${\displaystyle r\geq 4}$.[18] Projective planes produce maximal intersecting families whose number of sets is ${\displaystyle r^{2}-r+1}$, but for infinitely many choices of ${\displaystyle r}$ there exist smaller maximal intersecting families of size ${\displaystyle {\tfrac {3}{4}}r^{2}}$.[17]

The largest intersecting families of ${\displaystyle r}$-element sets that are maximal but not maximum have size

$${\displaystyle {\binom {n-1}{r-1}}-{\binom {n-r-1}{r-1}}+1.}$$

They are formed from an element ${\displaystyle x}$ and an ${\displaystyle r}$-element set ${\displaystyle Y}$ not containing ${\displaystyle x}$, by adding ${\displaystyle Y}$ to the family of ${\displaystyle r}$-element sets that include both ${\displaystyle x}$ and at least one element of ${\displaystyle Y}$. This result is called the Hilton–Milner theorem, after its proof by Anthony Hilton and Eric Charles Milner in 1967.[19]

A generalization of the theorem applies to subsets that are required to have large intersections. This version of the theorem has three parameters: ${\displaystyle n}$, the number of elements the subsets are drawn from, ${\displaystyle r}$, the size of the subsets, as before, and ${\displaystyle t}$, the minimum size of the intersection of any two subsets. For the original form of the Erdős–Ko–Rado theorem, ${\displaystyle t=1}$. In general, for ${\displaystyle n}$ large enough with respect to the other two parameters, the generalized theorem states that the size of a ${\displaystyle t}$-intersecting family of subsets is at most[24]

$${\displaystyle {\binom {n-t}{k-t}}.}$$

More precisely, this bound holds when ${\displaystyle n\geq (t+1)(k-t+1)}$, and does not hold for smaller values of ${\displaystyle n}$. When ${\displaystyle n>(t+1)(k-t+1)}$, the only ${\displaystyle t}$-intersecting families of this size are obtained by designating ${\displaystyle t}$ elements as the common intersection of all the subsets, and constructing the family of all ${\displaystyle r}$-element subsets that include these ${\displaystyle t}$ designated elements.[25]

The corresponding graph-theoretic formulation of this generalization involves Johnson graphs in place of Kneser graphs.[26] For large enough values of ${\displaystyle n}$ and in particular for ${\displaystyle n>{\tfrac {1}{2}}k^{2}}$, 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 ${\displaystyle t}$-intersecting ${\displaystyle r}$-element subsets has Shannon capacity ${\displaystyle {\tbinom {n-t}{k-t}}}$.[27]

The theorem can also be generalized to families in which every ${\displaystyle h}$ subsets have a common intersection. Because this strengthens the condition that every pair intersects (for which ${\displaystyle h=2}$), these families have the same bound on their maximum size, ${\displaystyle {\tbinom {n-1}{r-1}}}$ when ${\displaystyle n}$ is sufficiently large. However, in this case the meaning of "sufficiently large" can be relaxed from ${\displaystyle n\geq 2r}$ to ${\displaystyle n\geq {\tfrac {h}{h-1}}r}$.[28]

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. If ${\displaystyle {\mathcal {S}}}$ is an intersecting family of ${\displaystyle k}$-dimensional subspaces of an ${\displaystyle n}$-dimensional vector space over a finite field of order ${\displaystyle q}$, and ${\displaystyle n\geq 2k}$, then

$${\displaystyle |{\mathcal {S}}|\leq {\binom {n-1}{k-1}}_{q},}$$

where the subscript q marks the notation for the Gaussian binomial coefficient, the number of subspaces of a given dimension within a vector space of a larger dimension over a finite field of order q. 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.[29]

Two permutations 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 ${\displaystyle n}$-element set, there is an obvious family of ${\displaystyle (n-1)!}$ 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 ${\displaystyle (n-1)!}$ are the cosets 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 ${\displaystyle t}$ and sufficiently large ${\displaystyle n}$, a family of permutations each pair of which has ${\displaystyle t}$ elements in common has maximum size ${\displaystyle (n-t)!}$, and the only families of this size are cosets of pointwise stabilizers.[30] Alternatively, in graph theoretic terms, the ${\displaystyle n}$-element permutations correspond to the perfect matchings of a complete bipartite graph ${\displaystyle K_{n,n}}$ and the theorem states that, among families of perfect matchings each pair of which share ${\displaystyle t}$ edges, the largest families are formed by the matchings that all contain ${\displaystyle t}$ chosen edges.[31] Another analog of the theorem, for partitions of a set, includes as a special case the perfect matchings of a complete graph ${\displaystyle K_{n}}$ (with ${\displaystyle n}$ even). There are ${\displaystyle (n-1)!!}$ matchings, where ${\displaystyle$ !!} denotes the double factorial. The largest family of matchings that pairwise intersect (meaning that they have an edge in common) has size ${\displaystyle (n-3)!!}$ and is obtained by fixing one edge and choosing all ways of matching the remaining ${\displaystyle n-2}$ vertices.[32]

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 point.[33]

A signed set consists of a set together with sign function that maps each element to ${\displaystyle \{1,-1\}}$. 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 ${\displaystyle r}$-element signed sets, drawn from an ${\displaystyle n}$-element universe, consists of at most

$${\displaystyle 2^{r-1}{\binom {n-1}{r-1}}}$$

signed sets. This number of signed sets may be obtained by fixing one element and its sign and letting the remaining ${\displaystyle r-1}$ elements and signs vary.[34]

For strings of length ${\displaystyle n}$ over an alphabet of size ${\displaystyle q}$, 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 ${\textstyle q^{n-1}}$ strings, and are the only pairwise intersecting families of this size. More generally, the largest families of strings in which every two have ${\displaystyle t}$ positions with equal symbols are obtained by choosing ${\displaystyle t+2i}$ positions and symbols for those positions, for a number ${\displaystyle i}$ that depends on ${\displaystyle n}$, ${\displaystyle q}$, and ${\displaystyle t}$, and constructing the family of strings that each have at least ${\displaystyle t+i}$ of the chosen symbols. These results can be interpreted graph-theoretically in terms of the Hamming scheme.[35]

An unproven conjecture, posed by Gil Kalai and Karen Meagher, concerns another analog for the family of triangulations of a convex polygon with ${\displaystyle n}$ vertices. The number of all triangulations is a Catalan number ${\displaystyle C_{n-2}}$, and the conjecture states that a family of triangulations every pair of which shares an edge has maximum size ${\displaystyle C_{n-3}}$. An intersecting family of size exactly ${\displaystyle C_{n-3}}$ may be obtained by cutting off a single vertex of the polygon by a triangle, and choosing all ways of triangulating the remaining ${\displaystyle (n-1)}$-vertex polygon.[36]