THE PROBABILISTIC LENS: The Erdos-Ko-Rado Theorem AfamilyFof sets is called intersecting if A.BimpliesB Suppose n>2k and let be an intersecting family of k-element subsets of an n-set,for definiteness (0,...,n-1).The Erdos-Ko-Rado Theorem is thatF(). This is achievable by taking the family of k-sets containing a particular point.We give a short proof due to Katona(1972). Lemma1For0≤s≤n-1 set As={s,&+1,…,s+k-l}where addition is modulo n.Then F can contain at most k of the sets As. aA. disjoint.The result follows,sinceFcan contain at most one member of each pair. Now we prove the Erdos-Ko-Rado Theorem.Let a permutation o of [0,...,n- 1}and if0,...,n-1}be chosen randomly,uniformly and independently and set A is uniformly chosen from all k-sets so and ≤份）=(-) 13THE PROBABILISTIC LENS: The Erdós-Ko-Rado Theorem A family J7 of sets is called intersecting \f A,B G T implies A n B ^ 0. Suppose n > 2k and let T be an intersecting family of fc-element subsets of an n-set, for definiteness {0,... ,n — 1}. The Erdós-Ko-Rado Theorem is that \T\ < (%Z\)- This is achievable by taking the family of fc-sets containing a particular point. We give a short proof due to Katona (1972). Lemma 1 For 0 < s < n — 1 set As — {s, s + 1,..., s + k — 1} where addition is modulo n. Then T can contain at most k ofthe sets As . Proof. Fix some As e T. All other sets At that intersect As can be partitioned into k — 1 pairs {^4S_¿, As+fc_¿}, (1 < i < k — 1), and the members of each such pairare disjoint. The result follows, since T can contain at most one member of each pair. • Now we prove the Erdós-Ko-Rado Theorem. Let a permutation a of {0,..., n - 1} and i G {0,..., n — 1} be chosen randomly, uniformly and independently and set A — {a(i),a(i + 1),..., a(i + k — 1)}, addition again modulo n. Conditioning on any choice of a the lemma gives Pr [A G !F] < k/n. Henee Pr [A G T\ < k/n. But A is uniformly chosen from all fc-sets so and , „,. k ín\ (n — \ 13