Erdős–Ko–Rado theorem

In combinatorics, the Erdős–Ko–Rado theorem of Paul Erdős, Chao Ko, and Richard Rado is a theorem bounding the size of intersecting families of sets.

Statement and history

The theorem is as follows. Suppose that ${\mathcal {A}}$ is a family of distinct subsets of $\{1,2,...,n\}$ such that each subset is of size $r$ and each pair of subsets has a nonempty intersection, and suppose that $n\geq 2r$. Then the number of sets in ${\mathcal {A}}$ is less than or equal to the binomial coefficient $${\binom {n-1}{r-1}}.$$

The result is 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 size $r$, it is called an $r$-uniform hypergraph. The theorem thus gives an upper bound for the number of pairwise non-disjoint hyperedges in an $r$-uniform hypergraph with $n$ vertices and $n\geq 2r$.

The theorem may also be formulated in terms of graph theory: the independence number of the Kneser graph $KG_{n,r}$ for $n\geq 2r$ is $$\alpha (KG_{n,r})={\binom {n-1}{r-1}}.$$

According to Erdős (1987) the theorem was proved in 1938, but was not published until 1961 in an apparently more general form. The subsets in question were only required to be size at most $r$, and with the additional requirement that no subset be contained in any other.

A version of the theorem also holds for signed sets.

Proof

The original proof of 1961 used induction on $n$. In 1972, Gyula O. H. Katona gave the following short proof using double counting.

Let ${\mathcal {A}}$ be any family of subsets of $\{1,2,...,n\}$. Arrange these numbers into any cyclic order, and consider the sets from $A$ that form intervals of length $r$ within this chosen cyclic order. For example if $n=8$ and $r=3$, one possible cyclic order for the numbers $\{1,2,...,8\}$ is the order $(3,1,5,4,2,7,6,8)$, which has eight 3-element intervals (including the ones that wrap around):

$(3,1,5)$, $(1,5,4)$, $(5,4,2)$, $(4,2,7)$, $(2,7,6)$, $(7,6,8)$, $(6,8,3)$, and $(8,3,1)$.

However, it is not possible for all of the intervals of the cyclic order to belong to ${\mathcal {A}}$, because some pairs of them are disjoint. Katona's key observation is that at most $r$ of the intervals for a single cyclic order may belong to ${\mathcal {A}}$. To see this, note that if $(a_{1},a_{2},\dots ,a_{r})$ is one of these intervals in $A$, then every other interval of the same cyclic order that belongs to ${\mathcal {A}}$ separates $a_{i}$ from $a_{i+1}$, for some $i$, by containing precisely one of these two elements. The two intervals that separate these elements are disjoint, so at most one of them can belong to $A$. Thus, the number of intervals in $A$ is at most one plus the number $r-1$ of pairs that can be separated.

Based on this idea, it is possible to count the number of pairs $(S,C)$, where $S$ is a set in ${\mathcal {A}}$ and $C$ is a cyclic order for which $S$ is an interval, in two ways. First, for each set $S$ one may generate $C$ by choosing one of $r!$ permutations of $S$ and $(n-r)!$ permutations of the remaining elements, showing that the number of pairs is $|{\mathcal {A}}|r!(n-r)!$. And second, there are $(n-1)!$ cyclic orders, each of which has at most $r$ intervals of ${\mathcal {A}}$, so the number of pairs is at most $r(n-1)!$. Combining these two counts gives the inequality $$|{\mathcal {A}}|r!(n-r)!\leq r(n-1)!$$ and dividing both sides by $r!(n-r)!$ gives the result $$|{\mathcal {A}}|\leq {\frac {r(n-1)!}{r!(n-r)!}}={n-1 \choose r-1}.$$

Families of maximum size

Two constructions for an intersecting family of $r$-sets: fix one element and choose the remaining elements in all possible ways, or (when $n=2r$) exclude one element and choose all subsets of the remaining elements. Here $n=4$ and $r=2$.

There are two different and straightforward constructions for an intersecting family of $r$-element sets whose size exactly matches the Erdős–Ko–Rado bound. First, choose any fixed element $x$, and let ${\mathcal {A}}$ consist of all $r$-subsets of $\{1,2,...,n\}$ that include $x$. For instance, if $n=4$, $r=2$, and $x=1$, this produces the family of three 2-sets {{bi|left=1.6|$\{1,2\}$, $\{1,3\}$, and $\{1,4\}$. Any two sets in this family intersect, because they both include $1$. Second, when $n=2r$ and with $x$ as above, let ${\mathcal {A}}$ consist of all $r$-subsets of $\{1,2,...,n\}$ that do not include $x$. For the same parameters as above, this produces the family {{bi|left=1.6|$\{2,3\}$, $\{2,4\}$, and $\{3,4\}$. Any two sets in this family have a total of $2r=n$ elements among them, chosen from the $n-1$ elements that are unequal to $x$, so by the pigeonhole principle they must have an element in common.

When $n>2r$, families of the first type (variously known as sunflowers, stars, dictatorships, centred families, principal families) are the unique maximum families. Friedgut (2008) proved that in this case, a family which is almost of maximum size has an element which is common to almost all of its sets. This property is known as stability.

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

Maximal intersecting families

An intersecting family of $r$-element sets may be maximal, in that no further set can be added without destroying the intersection property, but not of maximum size. An example with $n=7$ and $r=3$ is the set of seven lines of the Fano plane, much less than the Erdős–Ko–Rado bound of 15.

Intersecting families of subspaces

There is a q-analog of the Erdős–Ko–Rado theorem for intersecting families of subspaces over finite fields. If ${\mathcal {S}}$ is an intersecting family of $k$-dimensional subspaces of an $n$-dimensional vector space over a finite field of order $q$, and $n\geq 2k$, then $$|{\mathcal {S}}|\leq {\binom {n-1}{k-1}}_{q}.$$

References

• Bollobás, B.; Leader, I. (1997), "An Erdős-Ko-Rado theorem for signed sets", Computers and Mathematics with Applications, 34 (11): 9–13, doi:10.1016/S0898-1221(97)00215-0, MR 1486880
• Erdős, P. (1987), "My joint work with Richard Rado", in Whitehead, C. (ed.), Surveys in combinatorics, 1987: Invited Papers for the Eleventh British Combinatorial Conference (PDF), London Mathematical Society Lecture Note Series, vol. 123, Cambridge University Press, pp. 53–80, ISBN 978-0-521-34805-8.
• Erdős, P.; Ko, C.; Rado, R. (1961), "Intersection theorems for systems of finite sets" (PDF), Quarterly Journal of Mathematics, Second Series, 12: 313–320, doi:10.1093/qmath/12.1.313.
• Frankl, P.; Wilson, R. M. (1986), "The Erdős-Ko-Rado theorem for vector spaces", Journal of Combinatorial Theory, Series A, 43 (2): 228–236, doi:10.1016/0097-3165(86)90063-4.
• Friedgut, Ehud (2008), "On the measure of intersecting families, uniqueness and stability" (PDF), Combinatorica, 28 (5): 503–528, doi:10.1007/s00493-008-2318-9, S2CID 7225916
• Füredi, Zoltán (1995), "Extremal hypergraphs and combinatorial geometry" (PDF), Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994), Basel: Birkhäuser, pp. 1343–1352, doi:10.1007/978-3-0348-9078-6_65, MR 1404036
• Katona, G. O. H. (1972), "A simple proof of the Erdös-Chao Ko-Rado theorem", Journal of Combinatorial Theory, Series B, 13 (2): 183–184, doi:10.1016/0095-8956(72)90054-8.

• Godsil, Christopher; Karen, Meagher (2015), Erdős–Ko–Rado Theorems: Algebraic Approaches, Cambridge Studies in Advanced Mathematics, Cambridge University Press, ISBN 9781107128446.