Erdős–Ko–Rado theorem

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 extremal set theory.^[1]

The theorem applies to families of sets that all have the same size, $r$ , and are all subsets of some larger set of size $n$ . 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 $n$ is large enough for the problem to be nontrivial ( $n\geq 2r$ ) this construction produces the largest possible intersecting families. When $n=2r$ there are other equally-large families, but for larger values of $n$ 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 ${\mathcal {A}}$ is a family of distinct $r$ -element subsets of an $n$ -element set with $n\geq 2r$ , and that each two subsets share at least one element. Then the theorem states that the number of sets in ${\mathcal {A}}$ is at most the binomial coefficient

{\binom {n-1}{r-1}}.

The requirement that

n\geq 2r

is necessary for the problem to be nontrivial: when

n<2r

, all

r

-element sets intersect, and the largest intersecting family consists of all

r

-element sets, with size

{\tbinom {n}{r}}

.^[2]

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

The Kneser graph $KG_{5,2}$ , 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 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}}.

This is a graph with a vertex for each

r

-element subset of an

n

-element 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 independent set.^[4] 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 exactly

n/r

.^[5]

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 Manchester.^[6] However, they did not publish the result until 1961,^[7] 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 1960s.^[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 $r$ , and to satisfy the additional requirement that no subset be contained in any other.^[7] A family of subsets meeting these conditions can be enlarged to subsets of size exactly $r$ either by an application of Hall's marriage theorem,^[8] or by choosing each enlarged subset from the same chain in a symmetric chain decomposition of sets.^[9]

Maximum and maximal families

Families of maximum size

A simple way to construct an intersecting family of $r$ -element sets whose size exactly matches the Erdős–Ko–Rado bound is to choose any fixed element $x$ , and let ${\mathcal {A}}$ consist of all $r$ -element subsets that include $x$ . For instance, for 2-element subsets of the 4-element set $\{1,2,3,4\}$ , with $x=1$ , this produces the family

\{1,2\}

,

\{1,3\}

, and

\{1,4\}

.

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

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

\{3,4\}

,

\{2,4\}

, and

\{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 $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]

Maximal intersecting families

An intersecting family of $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 $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.^[16] More generally, the lines of any finite projective plane of order $q$ form a maximal intersecting family that includes only $n$ sets, for the parameters $r=q+1$ and $n=q^{2}+q+1$ . The Fano plane is the case $q=2$ of this construction.^[17]

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

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

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

They are formed from an element

x

and an

r

-element set

Y

not containing

x

, by adding

Y

to the family of

r

-element sets that include both

x

and at least one element of

Y

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

Proofs

The original proof of the Erdős–Ko–Rado theorem used induction on $n$ . The base case, for $n=2r$ , 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 $r$ -element sets. The induction step for larger $n$ 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 analyze.^[20]

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

Let

{\mathcal {A}}

be any intersecting family of

r

-element subsets of an

n

-element set. Arrange all

n

elements into any cyclic order, and consider the sets from

{\mathcal {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, only some of these intervals can belong to ${\mathcal {A}}$ , because they do not all intersect. Katona's key observation is that at most $r$ intervals from a single cyclic order may belong to ${\mathcal {A}}$ . This is because, if $(a_{1},a_{2},\dots ,a_{r})$ is one of these intervals, 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 ${\mathcal {A}}$ . Thus, the number of intervals in ${\mathcal {A}}$ is at most one plus the number $r-1$ of pairs that can be separated.^[21]

Based on this idea, it is possible to count the 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)!$ . Comparing 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^[21]

|{\mathcal {A}}|\leq {\frac {r(n-1)!}{r!(n-r)!}}={n-1 \choose r-1}.

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 extremal set theory.^[22] Many other proofs are known.^[23]

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: $n$ , the number of elements the subsets are drawn from, $r$ , the size of the subsets, as before, and $t$ , the minimum size of the intersection of any two subsets. For the original form of the Erdős–Ko–Rado theorem, $t=1$ . In general, for $n$ large enough with respect to the other two parameters, the generalized theorem states that the size of a $t$ -intersecting family of subsets is at most^[24]

{\binom {n-t}{r-t}}.

More precisely, this bound holds when

n\geq (t+1)(r-t+1)

, and does not hold for smaller values of

n

. When

n>(t+1)(r-t+1)

, the only

t

-intersecting families of this size are obtained by designating

t

elements as the common intersection of all the subsets, and constructing the family of all

r

-element subsets that include these

t

designated elements.^[25] The maximal size of a

t

-intersecting family when

n<(t+1)(r-t+1)

was determined by Ahlswede and Khachatrian, in their Ahlswede–Khachatrian theorem.^[26]

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

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

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 $q$ -analog of the Erdős–Ko–Rado theorem for intersecting families of linear subspaces over finite fields. If ${\mathcal {S}}$ is an intersecting family of $r$ -dimensional subspaces of an $n$ -dimensional vector space over a finite field of order $q$ , and $n\geq 2r$ , then

|{\mathcal {S}}|\leq {\binom {n-1}{r-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.^[30]

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

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.^[34]

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

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

r-1

elements and signs vary.^[35]

For strings of length $n$ over an alphabet of size $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 $t$ positions with equal symbols are obtained by choosing $t+2i$ positions and symbols for those positions, for a number $i$ that depends on $n$ , $q$ , and $t$ , and constructing the family of strings that each have at least $t+i$ of the chosen symbols. These results can be interpreted graph-theoretically in terms of the Hamming scheme.^[36]

Unsolved problem in mathematics:

Is the largest family of intersecting triangulations of a convex polygon obtained by cutting off one vertex and choosing all triangulations of the remaining polygon?

(more unsolved problems in mathematics)

An unproven conjecture, posed by Gil Kalai and Karen Meagher, concerns another analog for the family of triangulations of a convex polygon with $n$ vertices. The number of all triangulations is a Catalan number $C_{n-2}$ , and the conjecture states that a family of triangulations every pair of which shares an edge has maximum size $C_{n-3}$ . An intersecting family of size exactly $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 $(n-1)$ -vertex polygon.^[37]

Applications

The Erdős–Ko–Rado theorem can be used to prove the following result in probability theory. Let $x_{i}$ be independent 0–1 random variables with probability $p\geq {\tfrac {1}{2}}$ of being one, and let $c({\vec {x}})$ be any fixed convex combination of these variables. Then

\Pr \left[c({\vec {x}})\geq {\tfrac {1}{2}}\right]\geq p.

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 subsets.^[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.^[39] The Erdős–Ko–Rado theorem has also been used to characterize the symmetries of the space of phylogenetic trees.^[40]

References

Notes

^ ^a ^b Das & Tran (2016).
^ Aigner & Ziegler (2018); Godsil & Meagher (2015), p. xiii.
^ Füredi (1995).
^ Harvey & Wood (2014); Godsil & Meagher (2015), p. xiv.
^ Godsil & Meagher (2015), p. 43.
^ ^a ^b Anderson (2013).
^ ^a ^b Erdős, Ko & Rado (1961); Erdős (1987).
^ van Lint & Wilson (1992).
^ Anderson (1987).
^ ^a ^b Aigner & Ziegler (2018).
^ ^a ^b Dinur & Friedgut (2009).
^ Borg (2012).
^ ^a ^b Friedgut (2008).
^ Friedgut (2008); Dinur & Friedgut (2009); Das & Tran (2016).
^ Bollobás, Narayanan & Raigorodskii (2016); Balogh, Krueger & Luo (2022).
^ Polcyn & Ruciński (2017).
^ ^a ^b Füredi (1980).
^ Dow et al. (1985).
^ Hilton & Milner (1967); Frankl & Füredi (1986); Godsil & Meagher (2015), Section 1.6: The Hilton–Milner theorem, pp. 15–17.
^ Erdős, Ko & Rado (1961); Godsil & Meagher (2015), Section 1.1: The original proof, pp. 2–6.
^ ^a ^b ^c Katona (1972); Anderson (1987); van Lint & Wilson (1992); Aigner & Ziegler (2018).
^ Godsil & Meagher (2015), Section 1.5: The Kruskal–Katona theorem, pp. 11–15.
^ Frankl & Graham (1989); Godsil & Meagher (2015), p. 22.
^ Erdős, Ko & Rado (1961); Godsil & Meagher (2015), Theorem 0.0.2, p. xiv.
^ Wilson (1984); Godsil & Meagher (2015), p. 2.
^ Ahlswede & Khachatrian (1997)
^ Godsil & Meagher (2015), p. xiv.
^ Schrijver (1981); Deza & Frankl (1983).
^ Frankl (1976); Anderson (1987).
^ Frankl & Wilson (1986); Godsil & Meagher (2015), Chapter 9: The Grassmann scheme, pp. 161–183.
^ Frankl & Deza (1977); Cameron & Ku (2003); Larose & Malvenuto (2004); Godsil & Meagher (2009); Ellis, Friedgut & Pilpel (2011); Godsil & Meagher (2015), Chapter 14: Permutations, pp. 260–278.
^ Godsil & Meagher (2015), Section 7.5: Perfect matchings in complete bipartite graphs.
^ Godsil & Meagher (2015), Section 15.2: Perfect matchings, pp. 282–284.
^ Godsil & Meagher (2015), Section 5.6: Partial geometries, pp. 100–103.
^ Bollobás & Leader (1997).
^ Ahlswede & Khachatrian (1998); Godsil & Meagher (2015), Chapter 10: The Hamming scheme, pp. 184–209.
^ Olarte et al. (2020).
^ Liggett (1977); Anderson (1987).
^ Haviv (2022).
^ Grindstaff (2020).

Works cited

Ahlswede, Rudolf; Khachatrian, Levon H. (1997), "The complete intersection theorem for systems of finite sets", European Journal of Combinatorics, 18: 125–136, doi:10.1006/eujc.1995.0092
Ahlswede, Rudolf; Khachatrian, Levon H. (1998), "The diametric theorem in Hamming spaces—optimal anticodes", Advances in Applied Mathematics, 20 (4): 429–449, doi:10.1006/aama.1998.0588, MR 1612850
Aigner, Martin; Ziegler, Günter M. (2018), "Chapter 30: Three famous theorems on finite sets", Proofs from THE BOOK (6th ed.), Springer, pp. 213–217, doi:10.1007/978-3-662-57265-8_15, ISBN 978-3-662-57265-8, MR 3823190, Zbl 1392.00001
Anderson, Ian (1987), "Chapter 5: Intersecting systems and the Erdős–Ko–Rado theorem", Combinatorics of Finite Sets, Oxford Science Publications, Oxford University Press, pp. 70–86, ISBN 0-19-853367-5, MR 0892525
Anderson, Ian (2013), "Combinatorial set theory", in Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, pp. 309–328, doi:10.1093/acprof:oso/9780199656592.003.0014, ISBN 978-0-19-965659-2, MR 3204727
Balogh, József; Krueger, Robert A.; Luo, Haoran (2022), "Sharp threshold for the Erdős–Ko–Rado theorem", Random Structures & Algorithms, 62: 3–28, arXiv:2105.02985, doi:10.1002/rsa.21090, S2CID 234093039
Bollobás, Béla; Leader, Imre (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, Zbl 0901.05088
Bollobás, Béla; Narayanan, Bhargav P.; Raigorodskii, Andrei M. (2016), "On the stability of the Erdős-Ko-Rado theorem", Journal of Combinatorial Theory, Series A, 137: 64–78, arXiv:1408.1288, doi:10.1016/j.jcta.2015.08.002, MR 3403515
Borg, Peter (2012), "Cross-intersecting sub-families of hereditary families", Journal of Combinatorial Theory, Series A, 119 (4): 871–881, arXiv:1103.3858, doi:10.1016/j.jcta.2011.12.002, MR 2881232
Cameron, Peter J.; Ku, C. Y. (2003), "Intersecting families of permutations", European Journal of Combinatorics, 24 (7): 881–890, doi:10.1016/S0195-6698(03)00078-7, MR 2009400, Zbl 1026.05001
Das, Shagnik; Tran, Tuan (2016), "Removal and stability for Erdős–Ko–Rado", SIAM Journal on Discrete Mathematics, 30 (2): 1102–1114, doi:10.1137/15M105149X, MR 3504983
Deza, Michel; Frankl, Péter (1983), "Erdős–Ko–Rado theorem – 22 years later", SIAM Journal on Algebraic and Discrete Methods, 4 (4): 419–431, doi:10.1137/0604042, MR 0721612
Dinur, Irit; Friedgut, Ehud (2009), "Intersecting families are essentially contained in juntas", Combinatorics, Probability and Computing, 18 (1–2): 107–122, doi:10.1017/S0963548308009309, MR 2497376, S2CID 8923303
Dow, Stephen J.; Drake, David A.; Füredi, Zoltán; Larson, Jean A. (1985), "A lower bound for the cardinality of a maximal family of mutually intersecting sets of equal size", Proceedings of the sixteenth Southeastern international conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1985), Congressus Numerantium, 48: 47–48, MR 0830697
Ellis, David; Friedgut, Ehud; Pilpel, Haran (2011), "Intersecting families of permutations", Journal of the American Mathematical Society, 24 (3): 649–682, arXiv:1011.3342, doi:10.1090/S0894-0347-2011-00690-5, MR 2784326, S2CID 9198144
Erdős, Paul (1987), "My joint work with Richard Rado" (PDF), in Whitehead, C. (ed.), Surveys in combinatorics, 1987: Invited Papers for the Eleventh British Combinatorial Conference, London Mathematical Society Lecture Note Series, vol. 123, Cambridge University Press, pp. 53–80, ISBN 978-0-521-34805-8, MR 0905276, Zbl 0623.01010
Erdős, P.; Ko, Chao; 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, MR 0140419, Zbl 0100.01902
Frankl, Péter (1976), "On Sperner families satisfying an additional condition", Journal of Combinatorial Theory, Series A, 20 (1): 1–11, doi:10.1016/0097-3165(76)90073-x, MR 0398842
Frankl, Péter; Deza, Mikhail (1977), "On the maximum number of permutations with given maximal or minimal distance", Journal of Combinatorial Theory, Series A, 22 (3): 352–360, doi:10.1016/0097-3165(77)90009-7, MR 0439648, Zbl 0352.05003
Frankl, Péter; Füredi, Zoltán (1986), "Nontrivial intersecting families", Journal of Combinatorial Theory, Series A, 41 (1): 150–153, doi:10.1016/0097-3165(86)90121-4, MR 0826944
Frankl, Péter; Graham, Ronald L. (1989), "Old and new proofs of the Erdős–Ko–Rado theorem" (PDF), Journal of Sichuan University Natural Science Edition, 26 (Special Issue): 112–122, MR 1059690
Frankl, Péter; Wilson, Richard 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, MR 0867648, Zbl 0609.05055
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, MR 2501247, S2CID 7225916, Zbl 1199.05319, archived from the original (PDF) on 2021-01-25
Füredi, Zoltán (1980), "On maximal intersecting families of finite sets", Journal of Combinatorial Theory, Series A, 28 (3): 282–289, doi:10.1016/0097-3165(80)90071-0, MR 0570210
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, Zbl 0839.05077, archived from the original on 2017-08-30, retrieved 2022-08-23{{citation}}: CS1 maint: bot: original URL status unknown (link)
Godsil, Chris; Meagher, Karen (2009), "A new proof of the Erdős–Ko–Rado theorem for intersecting families of permutations", European Journal of Combinatorics, 30 (2): 404–414, arXiv:0710.2109, doi:10.1016/j.ejc.2008.05.006, MR 2489272, Zbl 1177.05010
Godsil, Christopher; Meagher, Karen (2015), Erdős–Ko–Rado Theorems: Algebraic Approaches, Cambridge Studies in Advanced Mathematics, Cambridge University Press, ISBN 9781107128446
Grindstaff, Gillian (2020), "The isometry group of phylogenetic tree space is $S n$ ", Proceedings of the American Mathematical Society, 148 (10): 4225–4233, arXiv:1901.02982, doi:10.1090/proc/15154, MR 4135291, S2CID 57761161
Harvey, Daniel J.; Wood, David R. (2014), "Treewidth of the Kneser graph and the Erdős–Ko–Rado theorem", Electronic Journal of Combinatorics, 21 (1), Paper 1.48, arXiv:1310.5400, doi:10.37236/3971, MR 3177543, S2CID 15461040, Zbl 1300.05084
Haviv, Ishay (2022), "A fixed-parameter algorithm for the Kneser problem", in Bojanczyk, Mikolaj; Merelli, Emanuela; Woodruff, David P. (eds.), 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4–8, 2022, Paris, France, LIPIcs, vol. 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 72:1–72:18, arXiv:2204.06761, doi:10.4230/LIPIcs.ICALP.2022.72, ISBN 9783959772358
Hilton, A. J. W.; Milner, E. C. (1967), "Some intersection theorems for systems of finite sets", Quarterly Journal of Mathematics, Second Series, 18: 369–384, doi:10.1093/qmath/18.1.369, MR 0219428
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, MR 0304181, Zbl 0262.05002
Larose, Benoit; Malvenuto, Claudia (2004), "Stable sets of maximal size in Kneser-type graphs", European Journal of Combinatorics, 25 (5): 657–673, doi:10.1016/j.ejc.2003.10.006, MR 2061391
Liggett, Thomas M. (1977), "Extensions of the Erdős–Ko–Rado theorem and a statistical application", Journal of Combinatorial Theory, Series A, 23 (1): 15–21, doi:10.1016/0097-3165(77)90075-9, MR 0441750
van Lint, J. H.; Wilson, Richard M. (1992), A Course in Combinatorics, Cambridge University Press, Cambridge, pp. 45–46, ISBN 0-521-41057-6, MR 1207813
Olarte, Jorge Alberto; Santos, Francisco; Spreer, Jonathan; Stump, Christian (2020), "The EKR property for flag pure simplicial complexes without boundary" (PDF), Journal of Combinatorial Theory, Series A, 172: 105205, 29, doi:10.1016/j.jcta.2019.105205, MR 4052307, S2CID 119158469
Polcyn, Joanna; Ruciński, Andrzej (2017), "A hierarchy of maximal intersecting triple systems", Opuscula Mathematica, 37 (4): 597–608, arXiv:1608.06114, doi:10.7494/OpMath.2017.37.4.597, MR 3647803, S2CID 55674958, Zbl 1402.05209
Schrijver, Alexander (1981), "Association schemes and the Shannon capacity: Eberlein polynomials and the Erdős–Ko–Rado theorem", in Lovász, László; Sós, Vera T. (eds.), Algebraic Methods in Graph Theory, Vol. I, II: Papers from the Conference held in Szeged, August 24–31, 1978, Colloquia Mathematica Societatis János Bolyai, vol. 25, North-Holland, pp. 671–688, MR 0642067
Wilson, Richard M. (1984), "The exact bound in the Erdős–Ko–Rado theorem", Combinatorica, 4 (2–3): 247–257, doi:10.1007/BF02579226, MR 0771733, S2CID 44504849

External links

Cameron, Peter (September 29, 2017), "EKR, Steiner systems, association schemes, and all that", Peter Cameron's Blog

[FOOTNOTEDasTran2016-1] Das & Tran (2016).

[2] Aigner & Ziegler (2018); Godsil & Meagher (2015), p. xiii.

[FOOTNOTEFüredi1995-3] Füredi (1995).

[4] Harvey & Wood (2014); Godsil & Meagher (2015), p. xiv.

[FOOTNOTEGodsilMeagher201543-5] Godsil & Meagher (2015), p. 43.

[FOOTNOTEAnderson2013-6] Anderson (2013).

[erdos-recalls-7] Erdős, Ko & Rado (1961); Erdős (1987).

[FOOTNOTEvan_LintWilson1992-8] van Lint & Wilson (1992).

[FOOTNOTEAnderson1987-9] Anderson (1987).

[FOOTNOTEAignerZiegler2018-10] Aigner & Ziegler (2018).

[FOOTNOTEDinurFriedgut2009-11] Dinur & Friedgut (2009).

[FOOTNOTEBorg2012-12] Borg (2012).

[FOOTNOTEFriedgut2008-13] Friedgut (2008).

[14] Friedgut (2008); Dinur & Friedgut (2009); Das & Tran (2016).

[15] Bollobás, Narayanan & Raigorodskii (2016); Balogh, Krueger & Luo (2022).

[FOOTNOTEPolcynRuciński2017-16] Polcyn & Ruciński (2017).

[FOOTNOTEFüredi1980-17] Füredi (1980).

[FOOTNOTEDowDrakeFürediLarson1985-18] Dow et al. (1985).

[19] Hilton & Milner (1967); Frankl & Füredi (1986); Godsil & Meagher (2015), Section 1.6: The Hilton–Milner theorem, pp. 15–17.

[20] Erdős, Ko & Rado (1961); Godsil & Meagher (2015), Section 1.1: The original proof, pp. 2–6.

[katona-proof-21] Katona (1972); Anderson (1987); van Lint & Wilson (1992); Aigner & Ziegler (2018).

[FOOTNOTEGodsilMeagher2015Section_1.5:_The_Kruskal–Katona_theorem,_pp._11–15-22] Godsil & Meagher (2015), Section 1.5: The Kruskal–Katona theorem, pp. 11–15.

[23] Frankl & Graham (1989); Godsil & Meagher (2015), p. 22.

[24] Erdős, Ko & Rado (1961); Godsil & Meagher (2015), Theorem 0.0.2, p. xiv.

[25] Wilson (1984); Godsil & Meagher (2015), p. 2.

[26] Ahlswede & Khachatrian (1997)

[FOOTNOTEGodsilMeagher2015xiv-27] Godsil & Meagher (2015), p. xiv.

[28] Schrijver (1981); Deza & Frankl (1983).

[29] Frankl (1976); Anderson (1987).

[30] Frankl & Wilson (1986); Godsil & Meagher (2015), Chapter 9: The Grassmann scheme, pp. 161–183.

[31] Frankl & Deza (1977); Cameron & Ku (2003); Larose & Malvenuto (2004); Godsil & Meagher (2009); Ellis, Friedgut & Pilpel (2011); Godsil & Meagher (2015), Chapter 14: Permutations, pp. 260–278.

[FOOTNOTEGodsilMeagher2015Section_7.5:_Perfect_matchings_in_complete_bipartite_graphs-32] Godsil & Meagher (2015), Section 7.5: Perfect matchings in complete bipartite graphs.

[FOOTNOTEGodsilMeagher2015Section_15.2:_Perfect_matchings,_pp._282–284-33] Godsil & Meagher (2015), Section 15.2: Perfect matchings, pp. 282–284.

[FOOTNOTEGodsilMeagher2015Section_5.6:_Partial_geometries,_pp._100–103-34] Godsil & Meagher (2015), Section 5.6: Partial geometries, pp. 100–103.

[FOOTNOTEBollobásLeader1997-35] Bollobás & Leader (1997).

[36] Ahlswede & Khachatrian (1998); Godsil & Meagher (2015), Chapter 10: The Hamming scheme, pp. 184–209.

[FOOTNOTEOlarteSantosSpreerStump2020-37] Olarte et al. (2020).

[38] Liggett (1977); Anderson (1987).

[FOOTNOTEHaviv2022-39] Haviv (2022).

[FOOTNOTEGrindstaff2020-40] Grindstaff (2020).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

Erdős–Ko–Rado theorem

Statement

History

Maximum and maximal families

Families of maximum size

Maximal intersecting families

Proofs

Related results

Generalizations

Analogs

Applications

See also

References

Notes

Works cited

External links

Ryusuke Kawasaki

Antigonus II Matatias

Tungau debu rumah

David Robert Mitchell

Bank of America

Euler–Maruyama method

Elisabeth Couperus-Baud

Marguerite De La Motte

Mr. Big (gruppo musicale)

Keuskupan Port Harcourt

Estremoz

Pesta Olahraga Gay 2018

Kayangan Api

Ferenc Deák

Copa América

Henk Timmer

8 cm Raketen-Vielfachwerfer

Pertempuran Dnieper

Sheol

270