15 2.The Probabilistic Method 2.3 The Erdos-Ko-Rado Theorem 2.3.1 Definition.A family F of sets is intersecting if for all A,BF, A∩B≠0. 2.3.2 Theorem (The Erdos-Ko-Rado Theorem).If X]=n,n 2k, and F is an intersecting family of k-element subsets of X,then s) Clearly,this is tight,because a family of all the k-element subsets containing a particular point is intersecting and the number of such subsets is().(This configuration is sometimes called a sunflower and the theorem is referred to as the Sunflower Theorem.) 2.3.3 Lemma.Consider X ={0,1,...,n-1)with addition modulo n and define A.={s,s +1,...,s+k-1)X for 0ss n.Then for n z 2k,any intersecting family F()contains at most k of the sets A.. Proof.If Ai E F,then any other A.F must be one of the set only one set from each pair can appear in F. Proof of the theorem.We can assume that X={0,1,...,n-1}andF() is an intersecting family.For a permutation o:X-X,we define (As)={a(s,a(s+1),(8+k-1), by the permut by the lemma at mos are inTherefore,if we choose random s and a independently po(A,)∈刀≤ (the underlying probability space here is the product n]x S with the uniform measure,where S is the set of all permutations on In)).But this choice of (A)is equivalent to a random choice of a k-element subset of X,so P(4)∈刀=只 and 15 2. The Probabilistic Method 2.3 The Erd˝os–Ko–Rado Theorem 2.3.1 Definition. A family F of sets is intersecting if for all A, B ∈ F, A ∩ B 6= ∅. 2.3.2 Theorem (The Erd˝os–Ko–Rado Theorem). If |X| = n, n ≥ 2k, and F is an intersecting family of k-element subsets of X, then |F| ≤ n − 1 k − 1 ! . Clearly, this is tight, because a family of all the k-element subsets containing a particular point is intersecting and the number of such subsets is ￾n−1 k−1
. (This configuration is sometimes called a sunflower and the theorem is referred to as the Sunflower Theorem.) 2.3.3 Lemma. Consider X = {0, 1, . . . , n − 1} with addition modulo n and define As = {s, s + 1, . . . , s + k − 1} ⊆ X for 0 ≤ s < n. Then for n ≥ 2k, any intersecting family F ⊆ ￾X k
contains at most k of the sets As. Proof. If Ai ∈ F, then any other As ∈ F must be one of the sets Ai−k+1, . . . , Ai−1 or Ai+1, . . . , Ai+k−1. These are 2k − 2 sets, which can be di￾vided into k − 1 pairs of the form (As, As+k). As n ≥ 2k, As ∩ As+k = ∅, and only one set from each pair can appear in F. ✷ Proof of the theorem. We can assume that X = {0, 1, . . . , n−1} and F ⊆ ￾X k
is an intersecting family. For a permutation σ: X → X, we define σ(As) = {σ(s), σ(s + 1), . . . , σ(s + k − 1)}, addition again modulo n. The sets σ(As) are just like those in the lemma, only with the elements relabeled by the permutation σ, so by the lemma at most k of these n sets are in F. Therefore, if we choose random s and σ independently and uniformly, P[σ(As) ∈ F] ≤ k n (the underlying probability space here is the product [n] × Sn with the uniform measure, where Sn is the set of all permutations on [n]). But this choice of σ(As) is equivalent to a random choice of a k-element subset of X, so P[σ(As) ∈ F] = |F| ￾n k
and |F| = n k ! P[σ(As) ∈ F] ≤ n k ! k n = n − 1 k − 1 ! . ✷