I recently wrote a tiny bit about the style of the original published proof of the Erdős-Ko-Rado theorem. In this note I’ll write a bit about the theorem and a bit more about the style of some later proofs. In particular I want to write about two different readings of Katona’s proof.
For a recent vacation I packed my copy of Béla Bollobás “The Art of Mathematics”, Cambridge 2006. It is a book I have written about before and a good source of distraction during long plane flights and long travel connections.
Problem 71 turns out to be the Erdős-Ko-Rado theorem and the solution hint is designed to try and lead you into Katona’s beautiful re-proof of the result. In fact this later proof is listed in Martin Aigner and Günter M. Ziegler’s “Proofs from THE BOOK”, 4th edition, Springer 2009.
The Erdős-Ko-Rado theorem
According to Bollobás the result was proven in the 1930s, and first published in: “Intersection Theorems for Systems of Finite Sets” P. Erdős, Chao Ko, R. Rado; Quart. J. Math., Oxford (2), 12 (1961), pp. 313-320.
The theorem (which for many may not be as attractive as the proof) is stated as follows:
Fix two integers k and n (k ≥ 1, n ≥ 2k). Let F be a set of subsets of the integers {0,...,n-1} such that:
- If
AinFthen|A| = k. - If
A,BinFthenA intersect B != emptyset.
We call such an F a (k,n)-intersecting family.
The Erdős-Ko-Rado theorem states that |F| ≤ (n-1 choose k-1). That is, you can only design F to be so large and still have all the non-empty intersections.
It turns there is a standard construction of a large F: pick any element of {0,...,n-1} and insist it be in every set in F. For example let’s try F where A in F only iff 0 in A, A contained in {0,...,n-1}, and |A|=k. It is easy to show there are exactly (n-1 choose k-1) such A (this is pretty much the definition of (n-1 choose k-1) as we are forming each set A by choosing zero plus k-1 more items from {1,...,n-1}), and that this F is a (k,n)-intersecting family.
So the theorem is “tight” we know there are (k,n)-intersecting F such that |F| = (n-1 choose k-1) so once we prove |F| ≤ (n-1 choose k-1) for any/all F we have the size fairly locked-down.
This result helped popularize a field that came to be called “extremal graph theory.” The excitement of extremal graph theory is not towering abstractions (most of the work is done of sets of sets, without introducing a lot of new structures or terminology)- but the definitiveness of the results. Many of the results are of the form: “if you try to make a maximal system of sets with the following properties then the size is exactly x and the structure is exactly the following.”
The structure of F
An additional result is when n>2k: the above solution is in fact the only maximal solution. When n>2k the only way to make a maximal intersecting family of sets is to pick an element to be in all the sets. This is often stated as being part of the original Erdős-Ko-Rado theorem, but I think (from my brief inspection of the literature) this wasn’t published until J. W. Hilton, E. C. Milner, “Some intersection theorems for systems of finite sets” Quart. J. Math. Oxford Ser. (2) 18 (1967), 369-384.
The proofs
The original proof
The original proof was a clever induction that reduced the problem to two smaller problems using a technique that came to be called “shifting” (see “Old and New Proofs of the Erdős-Ko-Rado Theorem”, P. Frankl, R. L. Graham, Journal of Sichuan University, Natural Science Edition, Vol 26, pp. 112-122). Shifting (not even named in the original paper) has gone on to be an important technique. However, the original proof is involved and requires examining a lot of cases.
Katona’s circle method proof
A new proof was given in Katona, G. O. H. (1972), “A simple proof of the Erdős-Chao Ko-Rado theorem”, Journal of Combinatorial Theory, Series B 13 (2): pp. 183–184.
This (and not the original proof) is “the proof from THE BOOK.”
The idea is to first identify a special kind of A in our (k,n)-intersecting family F. Call A an (k,n)-cyclic interval (or cyclic interval) if it is of the form A = {a,a+1,...,a+k-1} modulo n. That is A is an contiguous cyclic interval of {0,...,n-1} of size k where we allow “wrapping around”. The point is there are exactly n possible cyclic intervals of size k drawn from {0,...,n-1} (as each such set is uniquely determined by n,k,a). And furthermore any intersecting system can at most include k such cyclic intervals because once two cyclic intervals that start k-units apart they no longer overlap.
For both versions of Katona’s proof we will need:
Pto denote the set ofn!permutations of{0,...,n-1}.- The function
f()over set of integers such thatf(A) = 1ifAis an cyclic interval (modulon) of sizekand0otherwise.
The probabilistic method proof
This version is from Bollobás.
- For a set of sets of integers
Fdefinef(F) = sum(A in F) f(A). - For a permutation
pdrawn fromPdefinep(F)as the set of sets of integers:{p(A)|A in F}.
Let’s look at E[f(p(F))] where F is a (k,n)-intersecting family (where E[] is the expected value taken over drawing a permutation p from P uniformly at random). Now a permutation of a (k,n)-intersecting family is again a (k,n)-intersecting family. So we know that f(p(F)) ≤ k for all permutations p (by our argument that cyclic intervals that are too far apart can not intersect). Since f(p(F)) ≤ k for all p we must also have E[f(p(F))] ≤ k.
Now let’s look at p(A) for a fixed A in F. The probability f(p(A))=1 is exactly n/(n choose k) as a p drawn uniformly from P maps A uniformly to exactly (n choose k) different sets and precisely n of these are cyclic intervals. So by linearity of expectation we have E[f(p(F))] = |F| n/(n choose k).
So combining the last two paragraphs we have |F| n/(n choose k) = E[f(p(F))] ≤ k. So |F| ≤ k (n choose k) /n = (n-1 choose k-1) and we are done. This is a very exciting proof using an indicator function f() and ideas like linearity of expectation (as celebrated in Noga Alon, Joel H. Spencer, “The Probabilistic Method”, 3rd edition, Wiley, 2008).
The “count in two different ways” version.
This is close to the version from the Wikipedia and a bit closer to the “proof from THE BOOK.”
Write down pairs (A,p) where A in F and p in P. Let’s look at the size of the set G = {(A,p) | A in F, p in P, f(p(A))=1 (i.e. p(A) is a cyclic interval)}.
We can enumerate the pairs in G from A to p. For a given cyclic interval I there are exactly
k! (n-k)! permutations p such that p(A)=I (as sets). There are n target intervals to hit, so |G| = |F| n k! (n-k)!.
We can also enumerate the pairs in G from p to A. Each p can map at most k items to cyclic intervals (as that is how many there are, and permutations are 1 to 1) and there are n! permutations. So |G| ≤ n! k.
Combining the last two statements gives us: |F| n k! (n-k)! = |G| ≤ n! k. So again |F| ≤ (n-1 choose k-1).
Which proof is better?
I would argue the second “counting two ways” proof is better. Both proofs involve a lot of clever ideas (the restricting to intervals, computing the bounds too ways, using distinctness of the interval targets). Where they differ is: the first proof adds a probabilistic model and the second proof adds a clever joint structure (pairs).
As general, powerful, and exciting as the probabilistic method is, I feel in this case the extra machinery introduced in the first proof isn’t completely justified. The point being: neither proof used any steps that were much easier to state in probabilistic versus counting terms (such as conditional probabilities or independence).
Now the question is: which version is closer to Katona’s original? Katona used the “count in two different ways” method very succinctly in a paper shorter than my attempted explination.
Categories: Mathematics
jmount
Data Scientist and trainer at Win Vector LLC. One of the authors of Practical Data Science with R.