Combinatorics (Fall 2010)/Extremal set theory

Sperner system

A set family [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] with the relation [math]\displaystyle{ \subseteq }[/math] define a poset. Thus, a chain is a sequence [math]\displaystyle{ S_1\subseteq S_2\subseteq\cdots\subseteq S_k }[/math].

A set family [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] is an antichain (also called a Sperner system) if for all [math]\displaystyle{ S,T\in\mathcal{F} }[/math] that [math]\displaystyle{ S\neq T }[/math], we have [math]\displaystyle{ S\not\subseteq T }[/math].

The [math]\displaystyle{ k }[/math]-uniform [math]\displaystyle{ {X\choose k} }[/math] is an antichain. Let [math]\displaystyle{ n=|X| }[/math]. The size of [math]\displaystyle{ {X\choose k} }[/math] is maximized when [math]\displaystyle{ k=\lfloor n/2\rfloor }[/math]. We wonder whether this is also the largest possible size of any antichain [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math].

In 1928, Emanuel Sperner proved a theorem saying that it is indeed the largest possible antichain. This result, called Sperner's theorem today, initiated the studies of extremal set theory.

Theorem (Sperner 1928)

Let [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] where [math]\displaystyle{ |X|=n }[/math]. If [math]\displaystyle{ \mathcal{F} }[/math] is an antichain, then [math]\displaystyle{ |\mathcal{F}|\le{n\choose \lfloor n/2\rfloor} }[/math].

First proof (shadows)

Definition

Let [math]\displaystyle{ |X|=n\, }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math], [math]\displaystyle{ k\lt n\, }[/math]. The shade of [math]\displaystyle{ \mathcal{F} }[/math] is defined to be [math]\displaystyle{ \nabla\mathcal{F}=\left\{T\in {X\choose k+1}\,\,\bigg|\,\, \exists S\in\mathcal{F}\mbox{ such that } S\subset T\right\} }[/math]. Thus the shade [math]\displaystyle{ \nabla\mathcal{F} }[/math] of [math]\displaystyle{ \mathcal{F} }[/math] consists of all subsets of [math]\displaystyle{ X }[/math] which can be obtained by adding an element to a set in [math]\displaystyle{ \mathcal{F} }[/math]. Similarly, the shadow of [math]\displaystyle{ \mathcal{F} }[/math] is defined to be [math]\displaystyle{ \Delta\mathcal{F}=\left\{T\in {X\choose k-1}\,\,\bigg|\,\, \exists S\in\mathcal{F}\mbox{ such that } T\subset S\right\} }[/math]. Thus the shadow [math]\displaystyle{ \Delta\mathcal{F} }[/math] of [math]\displaystyle{ \mathcal{F} }[/math] consists of all subsets of [math]\displaystyle{ X }[/math] which can be obtained by removing an element from a set in [math]\displaystyle{ \mathcal{F} }[/math].

Lemma (Sperner)

Let [math]\displaystyle{ |X|=n\, }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math]. Then [math]\displaystyle{ \begin{align} &|\nabla\mathcal{F}|\ge\frac{n-k}{k+1}|\mathcal{F}| &\text{ if } k\lt n\\ &|\Delta\mathcal{F}|\ge\frac{k}{n-k+1}|\mathcal{F}| &\text{ if } k\gt 0. \end{align} }[/math]

Proof. The lemma is proved by double counting. We prove the inequality of [math]\displaystyle{ |\nabla\mathcal{F}| }[/math]. Assume that [math]\displaystyle{ 0\le k\lt n }[/math]. Define [math]\displaystyle{ \mathcal{R}=\{(S,T)\mid S\in\mathcal{F}, T\in\nabla\mathcal{F}, S\subset T\} }[/math]. We estimate [math]\displaystyle{ |\mathcal{R}| }[/math] in two ways. For each [math]\displaystyle{ S\in\mathcal{F} }[/math], there are [math]\displaystyle{ n-k }[/math] different [math]\displaystyle{ T\in\nabla\mathcal{F} }[/math] that [math]\displaystyle{ S\subset T }[/math]. [math]\displaystyle{ |\mathcal{R}|=(n-k)|\mathcal{F}| }[/math]. For each [math]\displaystyle{ T\in\nabla\mathcal{F} }[/math], there are [math]\displaystyle{ k+1 }[/math] ways to choose an [math]\displaystyle{ S\subset T }[/math] with [math]\displaystyle{ |S|=k }[/math], some of which may not be in [math]\displaystyle{ \mathcal{F} }[/math]. [math]\displaystyle{ |\mathcal{R}|\le k|\nabla\mathcal{F}| }[/math]. Altogether, we show that [math]\displaystyle{ |\nabla\mathcal{F}|\ge\frac{n-k}{k+1}|\mathcal{F}| }[/math]. The inequality of [math]\displaystyle{ |\Delta\mathcal{F}| }[/math] can be proved in the same way. [math]\displaystyle{ \square }[/math]

Proposition 1

If [math]\displaystyle{ k\le \frac{n-1}{2} }[/math], then [math]\displaystyle{ |\nabla\mathcal{F}|\ge|\mathcal{F}| }[/math]. If [math]\displaystyle{ k\ge \frac{n-1}{2} }[/math], then [math]\displaystyle{ |\Delta\mathcal{F}|\ge|\mathcal{F}| }[/math].

Proposition 2

Suppose that [math]\displaystyle{ \mathcal{F}\subseteq2^X }[/math] where [math]\displaystyle{ |X|=n }[/math]. Let [math]\displaystyle{ k_\min }[/math] be the smallest [math]\displaystyle{ k }[/math] that [math]\displaystyle{ |\mathcal{F}_k|\gt 0 }[/math], and let [math]\displaystyle{ \mathcal{F}'=\begin{cases} \mathcal{F}\setminus\mathcal{F}_k\cup \nabla\mathcal{F}_k & \mbox{if }k_\min\lt \frac{n-1}{2},\\ \mathcal{F} & \mbox{otherwise.} \end{cases} }[/math] Similarly, let [math]\displaystyle{ k_\max }[/math] be the largest [math]\displaystyle{ k }[/math] that [math]\displaystyle{ |\mathcal{F}_k|\gt 0 }[/math], and let [math]\displaystyle{ \mathcal{F}''=\begin{cases} \mathcal{F}\setminus\mathcal{F}_k\cup \Delta\mathcal{F}_k & \mbox{if }k_\max\ge\frac{n+1}{2},\\ \mathcal{F} & \mbox{otherwise.} \end{cases} }[/math] If [math]\displaystyle{ \mathcal{F} }[/math] is an antichain, [math]\displaystyle{ \mathcal{F}' }[/math] and [math]\displaystyle{ \mathcal{F}'' }[/math] are antichains, and we have [math]\displaystyle{ |\mathcal{F}'|\ge|\mathcal{F}| }[/math] and [math]\displaystyle{ |\mathcal{F}''|\ge|\mathcal{F}| }[/math].

Proof. We show that [math]\displaystyle{ \mathcal{F}' }[/math] is an antichain and [math]\displaystyle{ |\mathcal{F}'|\ge|\mathcal{F}| }[/math]. First, observe that [math]\displaystyle{ \nabla\mathcal{F}_k\cap\mathcal{F}=\emptyset }[/math], otherwise [math]\displaystyle{ \mathcal{F} }[/math] cannot be an antichain, and due to Proposition 1, [math]\displaystyle{ |\nabla\mathcal{F}_k|\ge|\mathcal{F}_k| }[/math] when [math]\displaystyle{ k\le \frac{n-1}{2} }[/math], so [math]\displaystyle{ |\mathcal{F}'|=|\mathcal{F}|-|\mathcal{F}_k|+|\nabla\mathcal{F}_k|\ge |\mathcal{F}| }[/math]. Now we prove that [math]\displaystyle{ \mathcal{F}' }[/math] is an antichain . By contradiction, assume that there are [math]\displaystyle{ S, T\in \mathcal{F}' }[/math], such that [math]\displaystyle{ S\subset T }[/math]. One of the [math]\displaystyle{ S,T }[/math] must be in [math]\displaystyle{ \nabla\mathcal{F}_k }[/math], or otherwise [math]\displaystyle{ \mathcal{F} }[/math] cannot be an antichain. Recall that [math]\displaystyle{ k_\min }[/math] is the smallest [math]\displaystyle{ k }[/math] that [math]\displaystyle{ |\mathcal{F}_k|\gt 0 }[/math], thus it must be [math]\displaystyle{ S\in \nabla\mathcal{F}_k }[/math], and [math]\displaystyle{ T\in\mathcal{F} }[/math]. This implies that there is an [math]\displaystyle{ R\in \mathcal{F}_k\subseteq \mathcal{F} }[/math] such that [math]\displaystyle{ R\subset S\subset T }[/math], which contradicts that [math]\displaystyle{ \mathcal{F} }[/math] is an antichain. The statement for [math]\displaystyle{ \mathcal{F}'' }[/math] can be proved in the same way. [math]\displaystyle{ \square }[/math]

Proof of Sperner's theorem (original proof of Sperner) Let [math]\displaystyle{ \mathcal{F}_k=\{S\in\mathcal{F}\mid |S|=k\} }[/math], where [math]\displaystyle{ 0\le k\le n }[/math]. We change [math]\displaystyle{ \mathcal{F} }[/math] as follows: for the smallest [math]\displaystyle{ k }[/math] that [math]\displaystyle{ |\mathcal{F}_k|\gt 0 }[/math], if [math]\displaystyle{ k\lt \frac{n-1}{2} }[/math], replace [math]\displaystyle{ \mathcal{F}_k }[/math] by [math]\displaystyle{ \nabla\mathcal{F}_k }[/math]. Due to Proposition 2, this procedure preserves [math]\displaystyle{ \mathcal{F} }[/math] as an antichain and does not decrease [math]\displaystyle{ |\mathcal{F}| }[/math]. Repeat this procedure, until [math]\displaystyle{ |\mathcal{F}_k|=0 }[/math] for all [math]\displaystyle{ k\lt \frac{n-1}{2} }[/math], that is, there is no member set of [math]\displaystyle{ \mathcal{F} }[/math] has size less than [math]\displaystyle{ \frac{n-1}{2} }[/math]. We then define another symmetric procedure: for the largest [math]\displaystyle{ k }[/math] that [math]\displaystyle{ |\mathcal{F}_k|\gt 0 }[/math], if [math]\displaystyle{ k\ge\frac{n+1}{2} }[/math], replace [math]\displaystyle{ \mathcal{F}_k }[/math] by [math]\displaystyle{ \Delta\mathcal{F}_k }[/math]. Also due to Proposition 2, this procedure preserves [math]\displaystyle{ \mathcal{F} }[/math] as an antichain and does not decrease [math]\displaystyle{ |\mathcal{F}| }[/math]. After repeatedly applying this procedure, [math]\displaystyle{ |\mathcal{F}_k|=0 }[/math] for all [math]\displaystyle{ k\ge\frac{n+1}{2} }[/math]. The resulting [math]\displaystyle{ \mathcal{F} }[/math] has [math]\displaystyle{ \mathcal{F}\subseteq{X\choose \lfloor n/2\rfloor} }[/math], and since [math]\displaystyle{ |\mathcal{F}| }[/math] is never decreased, for the original [math]\displaystyle{ \mathcal{F} }[/math], we have [math]\displaystyle{ |\mathcal{F}|\le {n\choose \lfloor n/2\rfloor} }[/math]. [math]\displaystyle{ \square }[/math]

Second proof (double counting)

Proof of Sperner's theorem (Lubell 1966) Let [math]\displaystyle{ \pi }[/math] be a permutation of [math]\displaystyle{ X }[/math]. We say that an [math]\displaystyle{ S\subseteq X }[/math] prefixes [math]\displaystyle{ \pi }[/math], if [math]\displaystyle{ S=\{\pi_1,\pi_2,\ldots, \pi_{|S|}\} }[/math], that is, [math]\displaystyle{ S }[/math] is precisely the set of the first [math]\displaystyle{ |S| }[/math] elements in the permutation [math]\displaystyle{ \pi }[/math]. Fix an [math]\displaystyle{ S\subseteq X }[/math]. It is easy to see that the number of permutations [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ X }[/math] prefixed by [math]\displaystyle{ S }[/math] is [math]\displaystyle{ |S|!(n-|S|)! }[/math]. Also, since [math]\displaystyle{ \mathcal{F} }[/math] is an antichain, no permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ X }[/math] can be prefixed by more than one members of [math]\displaystyle{ \mathcal{F} }[/math], otherwise one of the member sets must contain the other, which contradicts that [math]\displaystyle{ \mathcal{F} }[/math] is an antichain. Thus, the number of permutations [math]\displaystyle{ \pi }[/math] prefixed by some [math]\displaystyle{ S\in\mathcal{F} }[/math] is [math]\displaystyle{ \sum_{S\in\mathcal{F}}|S|!(n-|S|)! }[/math], which cannot be larger than the total number of permutations, [math]\displaystyle{ n! }[/math], therefore, [math]\displaystyle{ \sum_{S\in\mathcal{F}}|S|!(n-|S|)!\le n! }[/math]. Dividing both sides by [math]\displaystyle{ n! }[/math], we have [math]\displaystyle{ \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}=\sum_{S\in\mathcal{F}}\frac{|S|!(n-|S|)!}{n!}\le 1 }[/math], where [math]\displaystyle{ {n\choose |S|}\le {n\choose \lfloor n/2\rfloor} }[/math], so [math]\displaystyle{ \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\ge \frac{|\mathcal{F}|}{{n\choose \lfloor n/2\rfloor}} }[/math]. Combining this with the above inequality, we prove the Sperner's theorem. [math]\displaystyle{ \square }[/math]

The LYM inequality

Theorem (Lubell, Yamamoto 1954; Meschalkin 1963)

Let [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] where [math]\displaystyle{ |X|=n }[/math]. If [math]\displaystyle{ \mathcal{F} }[/math] is an antichain, then [math]\displaystyle{ \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le 1 }[/math].

Third proof (the probabilistic method) (Due to Alon.) Let [math]\displaystyle{ \pi }[/math] be a uniformly random permutation of [math]\displaystyle{ X }[/math]. Define a random maximal chain by [math]\displaystyle{ \mathcal{C}_\pi=\{\{\pi_i\mid 1\le i\le k\}\mid 0\le k\le n\} }[/math]. For any [math]\displaystyle{ S\in\mathcal{F} }[/math], let [math]\displaystyle{ X_S }[/math] be the 0-1 random variable which indicates whether [math]\displaystyle{ S\in\mathcal{C}_\pi }[/math], that is [math]\displaystyle{ X_S=\begin{cases} 1 & \mbox{if }S\in\mathcal{C}_\pi,\\ 0 & \mbox{otherwise.} \end{cases} }[/math] Note that for a uniformly random [math]\displaystyle{ \pi }[/math], [math]\displaystyle{ \mathcal{C}_\pi }[/math] has exact one member set of size [math]\displaystyle{ |S| }[/math], uniformly distributed over [math]\displaystyle{ {X\choose |S|} }[/math], thus [math]\displaystyle{ \mathbf{E}[X_S]=\Pr[S\in\mathcal{C}_\pi]=\frac{1}{{n\choose |S|}} }[/math]. Let [math]\displaystyle{ X=\sum_{S\in\mathcal{F}}X_S }[/math]. Note that [math]\displaystyle{ X=|\mathcal{F}\cap\mathcal{C}_\pi| }[/math]. By the linearity of expectation, [math]\displaystyle{ \mathbf{E}[X]=\sum_{S\in\mathcal{F}}\mathbf{E}[X_S]=\sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}} }[/math]. On the other hand, since [math]\displaystyle{ \mathcal{F} }[/math] is an antichain, it can never intersect a chain at more than one elements, thus we always have [math]\displaystyle{ X=|\mathcal{F}\cap\mathcal{C}_\pi|\le 1 }[/math]. Therefore, [math]\displaystyle{ \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le \mathbf{E}[X] \le 1 }[/math]. [math]\displaystyle{ \square }[/math]

Proposition

[math]\displaystyle{ \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le 1 }[/math] implies that [math]\displaystyle{ |\mathcal{F}|\le{n\choose \lfloor n/2\rfloor} }[/math].

Intersecting Families

A set family [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] is called intersecting, if for any [math]\displaystyle{ S,T\in\mathcal{F} }[/math], [math]\displaystyle{ S\cap T\neq\emptyset }[/math].

Sunflowers

Definition (sunflower)

A set family [math]\displaystyle{ \mathcal{F}\subseteq 2^X }[/math] is a sunflower of size [math]\displaystyle{ r }[/math] with a core [math]\displaystyle{ C\subseteq X }[/math] if [math]\displaystyle{ \forall S,T\in\mathcal{F} }[/math] that [math]\displaystyle{ S\neq T }[/math], [math]\displaystyle{ S\cap T=C }[/math].

Note that we do not require the core to be nonempty, thus a family of disjoint sets is also a sunflower (with the core [math]\displaystyle{ \emptyset }[/math]).

Sunflower Lemma

Let [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math]. If [math]\displaystyle{ |\mathcal{F}|\gt k!(r-1)^k }[/math], then [math]\displaystyle{ \mathcal{F} }[/math] contains a sunflower of size [math]\displaystyle{ r }[/math].

Proof. We proceed by induction on [math]\displaystyle{ k }[/math]. For [math]\displaystyle{ k=1 }[/math], [math]\displaystyle{ \mathcal{F}\subseteq{X\choose 1} }[/math], thus all sets in [math]\displaystyle{ \mathcal{F} }[/math] are disjoint. And since [math]\displaystyle{ |\mathcal{F}|\gt r-1 }[/math], we can choose [math]\displaystyle{ r }[/math] of these sets and form a sunflower. Now let [math]\displaystyle{ k\ge 2 }[/math] and assume the lemma holds for all smaller [math]\displaystyle{ k }[/math]. Take a maximal family [math]\displaystyle{ \mathcal{G}\subseteq \mathcal{F} }[/math] whose members are disjoint, i.e. for any [math]\displaystyle{ S,T\in \mathcal{G} }[/math] that [math]\displaystyle{ S\neq T }[/math], [math]\displaystyle{ S\cap T=\emptyset }[/math]. If [math]\displaystyle{ |\mathcal{G}|\ge r }[/math], then [math]\displaystyle{ \mathcal{G} }[/math] is a sunflower of size at least [math]\displaystyle{ r }[/math] and we are done. Assume that [math]\displaystyle{ |\mathcal{G}|\le r-1 }[/math], and let [math]\displaystyle{ Y=\bigcup_{S\in\mathcal{G}}S }[/math]. Then [math]\displaystyle{ |Y|=k|\mathcal{G}|\le k(r-1) }[/math] (since all members of [math]\displaystyle{ \mathcal{G} }[/math]) are disjoint). We claim that [math]\displaystyle{ Y }[/math] intersets all members of [math]\displaystyle{ \mathcal{F} }[/math], since if otherwise, there exists an [math]\displaystyle{ S\in\mathcal{F} }[/math] such that [math]\displaystyle{ S\cap Y=\emptyset }[/math], then we can enlarge [math]\displaystyle{ \mathcal{G} }[/math] by adding [math]\displaystyle{ S }[/math] into [math]\displaystyle{ \mathcal{G} }[/math] and still have all members of [math]\displaystyle{ \mathcal{G} }[/math] disjoint, which contradicts the assumption that [math]\displaystyle{ \mathcal{G} }[/math] is the maximum of such families. By the pigeonhole principle, some elements [math]\displaystyle{ y\in Y }[/math] must contained in at least [math]\displaystyle{ \frac{|\mathcal{F}|}{|Y|}\gt \frac{k!(r-1)^k}{k(r-1)}=(k-1)!(r-1)^{k-1} }[/math] members of [math]\displaystyle{ \mathcal{F} }[/math]. We delete this [math]\displaystyle{ y }[/math] from these sets and consider the family [math]\displaystyle{ \mathcal{H}=\{S\setminus\{y\}\mid S\in\mathcal{F}\wedge y\in S\} }[/math]. We have [math]\displaystyle{ \mathcal{H}\subseteq {X\choose k-1} }[/math] and [math]\displaystyle{ |\mathcal{H}|\gt (k-1)!(r-1)^{k-1} }[/math], thus by the induction hypothesis, [math]\displaystyle{ \mathcal{H} }[/math]contains a sunflower of size [math]\displaystyle{ r }[/math]. Adding [math]\displaystyle{ y }[/math] to the members of this sunflower, we get the desired sunflower in the original family [math]\displaystyle{ \mathcal{F} }[/math]. [math]\displaystyle{ \square }[/math]

Erdős–Ko–Rado theorem

Erdős–Ko–Rado theorem

Let [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math] where [math]\displaystyle{ |X|=n }[/math] and [math]\displaystyle{ n\ge 2k }[/math]. If for any [math]\displaystyle{ S,T\in\mathcal{F} }[/math], [math]\displaystyle{ S\cap T\neq\emptyset }[/math], then [math]\displaystyle{ |\mathcal{F}|\le{n-1\choose k-1} }[/math].

Katona's proof

Let [math]\displaystyle{ \pi }[/math] be a cyclic permutation of [math]\displaystyle{ X }[/math], that is, we think of assigning [math]\displaystyle{ X }[/math] in a circle and ignore the rotations of the circle. It is easy to see that there are [math]\displaystyle{ (n-1)! }[/math] cyclic permutations of an [math]\displaystyle{ n }[/math]-set (each cyclic permutation corresponds to [math]\displaystyle{ n }[/math] permutations). Let

[math]\displaystyle{ \mathcal{C}_\pi=\{\{\pi_{(i+j)\bmod n}\mid j\in[k]\}\mid i\in [n]\} }[/math].

Lemma

Let [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math] where [math]\displaystyle{ |X|=n }[/math] and [math]\displaystyle{ n\ge 2k }[/math]. If [math]\displaystyle{ \mathcal{F} }[/math] is intersecting, then for any cyclic permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ X }[/math], it holds that [math]\displaystyle{ |\mathcal{C}_\pi\cap\mathcal{F}|\le k }[/math].

Proof. Fix a cyclic permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ X }[/math]. Let [math]\displaystyle{ C_i=\{\pi_{(i+j+n)\bmod n}\mid j\in[k]\} }[/math]. Then [math]\displaystyle{ \mathcal{C}_\pi }[/math] can be written as [math]\displaystyle{ \mathcal{C}_\pi=\{C_i\mid i\in [n]\} }[/math]. Suppose that [math]\displaystyle{ C_t\in\mathcal{F} }[/math]. Since [math]\displaystyle{ \mathcal{F} }[/math] is intersecting, the only sets [math]\displaystyle{ C_i }[/math] that can be in [math]\displaystyle{ \mathcal{F} }[/math] other than [math]\displaystyle{ C_t }[/math] itself are the [math]\displaystyle{ 2k-2 }[/math] sets [math]\displaystyle{ C_i }[/math] with [math]\displaystyle{ t-(k-1)\le i\le t+k-1, i\neq t }[/math]. We partition these sets into [math]\displaystyle{ k-1 }[/math] pairs [math]\displaystyle{ \{C_i,C_{i+k}\} }[/math], where [math]\displaystyle{ t-(k-1)\le i\le t-1 }[/math]. Note that for [math]\displaystyle{ n\ge 2k }[/math], it holds that [math]\displaystyle{ C_i\cap C_{i+k}=\emptyset }[/math]. Since [math]\displaystyle{ \mathcal{F} }[/math] is intersecting, [math]\displaystyle{ \mathcal{F} }[/math] can contain at most one set of each such pair. The lemma follows. [math]\displaystyle{ \square }[/math]

Katona's proof of Erdős–Ko–Rado theorem (double counting) Let [math]\displaystyle{ \mathcal{R}=\{(S,\pi)\mid \pi \mbox{ is a cyclic permutation of }X, \text{and }S\in\mathcal{F}\cap\mathcal{C}_\pi\} }[/math]. We count [math]\displaystyle{ \mathcal{R} }[/math] in two ways. First, due to the lemma, [math]\displaystyle{ |\mathcal{F}\cap\mathcal{C}_\pi|\le k }[/math] for any cyclic permutation [math]\displaystyle{ \pi }[/math]. There are [math]\displaystyle{ (n-1)! }[/math] cyclic permutations in total. Thus, [math]\displaystyle{ \mathcal{R}=\sum_{\pi}|\mathcal{F}\cap\mathcal{C}_\pi|\le k(n-1)! }[/math]. Next, for each [math]\displaystyle{ S\in\mathcal{F} }[/math], the number of cyclic permutations [math]\displaystyle{ \pi }[/math] in which [math]\displaystyle{ S }[/math] is continuous is [math]\displaystyle{ |S|!(n-|S|)!=k!(n-k)! }[/math]. Thus, [math]\displaystyle{ \mathcal{R}=\sum_{S\in\mathcal{F}}k!(n-k)! }[/math]. Altogether, we have [math]\displaystyle{ |\mathcal{F}|\le\frac{k(n-1)!}{k!(n-k)!}=\frac{(n-1)!}{(k-1)!(n-k)!}={n-1\choose k-1} }[/math]. [math]\displaystyle{ \square }[/math]

Erdős' shifting technique

Erdős–Ko–Rado theorem

Let [math]\displaystyle{ \mathcal{F}\subseteq {[n]\choose k} }[/math] and [math]\displaystyle{ n\ge 2k }[/math]. If [math]\displaystyle{ \mathcal{F} }[/math] is intersecting, then [math]\displaystyle{ |\mathcal{F}|\le{n-1\choose k-1} }[/math].

Definition (shift operator)

Assume [math]\displaystyle{ \mathcal{F}\subseteq 2^{[n]} }[/math], and [math]\displaystyle{ 0\le i\lt j\le n-1 }[/math]. Define the [math]\displaystyle{ (i,j) }[/math]-shift [math]\displaystyle{ S_{ij} }[/math] as an operator on [math]\displaystyle{ \mathcal{F} }[/math] and the sets [math]\displaystyle{ T\in\mathcal{F} }[/math] as follows: for each [math]\displaystyle{ T\in\mathcal{F} }[/math], write [math]\displaystyle{ T_{ij}=(T\setminus\{j\})\cup\{i\} }[/math], and let [math]\displaystyle{ S_{ij}(T)= \begin{cases} T_{ij} & \mbox{if }j\in T, i\not\in T, \mbox{ and }T_{ij} \not\in\mathcal{F},\\ T & \mbox{otherwise;} \end{cases} }[/math] let [math]\displaystyle{ S_{ij}(\mathcal{F})=\{S_{ij}(T)\mid T\in \mathcal{F}\} }[/math].

Proposition

[math]\displaystyle{ |S_{ij}(T)|=|T|\, }[/math] and [math]\displaystyle{ |S_{ij}(\mathcal{F})|=\mathcal{F} }[/math]; if [math]\displaystyle{ \mathcal{F} }[/math] is intersecting, then so is [math]\displaystyle{ S_{ij}(\mathcal{F}) }[/math].

Proof. (1) is immediate. Now we prove (2). Let [math]\displaystyle{ A,B\in\mathcal{F} }[/math]. Case.1: [math]\displaystyle{ \exists r\in A\cap B }[/math] such that [math]\displaystyle{ r\neq j }[/math]. Then [math]\displaystyle{ r\in S_{ij}(A)\cap S_{ij}(B) }[/math] thus [math]\displaystyle{ S_{ij}(A)\cap S_{ij}(B)\neq \emptyset }[/math]. Case.2: [math]\displaystyle{ A\cap B=\{j\} }[/math]. Case.2.1: [math]\displaystyle{ i\in A\cap B }[/math] or [math]\displaystyle{ i\not\in A\cup B }[/math]. Then [math]\displaystyle{ i\in S_{ij}(A)\cap S_{ij}(B) }[/math] thus [math]\displaystyle{ S_{ij}(A)\cap S_{ij}(B)\neq \emptyset }[/math]. Case.2.2: [math]\displaystyle{ i\in A }[/math] but [math]\displaystyle{ i\not\in B }[/math]. Then [math]\displaystyle{ A_{ij}=A\setminus\{j\}\cup\{i\}\not\in\mathcal{F} }[/math], since if otherwise, [math]\displaystyle{ A_{ij}\cap B=\emptyset }[/math] contradicts that [math]\displaystyle{ \mathcal{F} }[/math] is intersecting. Thus, [math]\displaystyle{ S_{ij}(A)=A_{ij} }[/math] and [math]\displaystyle{ S_{ij}(B)=B_{ij}=B\setminus\{j\}\cup\{i\} }[/math]. Therefore, [math]\displaystyle{ i\in S_{ij}(A)\cap S_{ij}(B) }[/math] thus [math]\displaystyle{ S_{ij}(A)\cap S_{ij}(B)\neq \emptyset }[/math]. In all cases, the members of [math]\displaystyle{ S_{ij}(\mathcal{F}) }[/math] are intersecting. [math]\displaystyle{ \square }[/math]

Proof of Erdős-Ko-Rado theorem (The original proof of Erdős-Ko-Rado by shifting) By the above lemma, it is sufficient to prove the Erdős-Ko-Rado theorem holds for shifted [math]\displaystyle{ \mathcal{F} }[/math]. We assume that [math]\displaystyle{ \mathcal{F} }[/math] is shifted. First, it is trivial to see that the theorem holds for [math]\displaystyle{ k=1 }[/math] (no matter whether shifted). Next, we show that the theorem holds when [math]\displaystyle{ n=2k }[/math] (no matter whether shifted). For any [math]\displaystyle{ S\in{X\choose k} }[/math], both [math]\displaystyle{ S }[/math] and [math]\displaystyle{ X\setminus S }[/math] are in [math]\displaystyle{ {X\choose k} }[/math], but at most one of them can be in [math]\displaystyle{ \mathcal{F} }[/math]. Thus, [math]\displaystyle{ |\mathcal{F}|\le\frac{1}{2}{n\choose k}=\frac{n!}{2k!(n-k)!}=\frac{(n-1)|}{(k-1)!(n-k)!}={n-1\choose k-1} }[/math]. We then apply the induction on [math]\displaystyle{ n }[/math]. For [math]\displaystyle{ n\gt 2k }[/math], the induction hypothesis is stated as: the Erdős-Ko-Rado theorem holds for any smaller [math]\displaystyle{ n }[/math]. Define [math]\displaystyle{ \mathcal{F}_0=\{S\in\mathcal{F}\mid n\not\in S\} }[/math] and [math]\displaystyle{ \mathcal{F}_1=\{S\in\mathcal{F}\mid n\in S\} }[/math]. Clearly, [math]\displaystyle{ \mathcal{F}_0\subseteq{[n-1]\choose k} }[/math] and [math]\displaystyle{ \mathcal{F}_0 }[/math] is intersecting. Due to the induction hypothesis, [math]\displaystyle{ |\mathcal{F}_0|\le{n-2\choose k-1} }[/math]. In order to apply the induction, we let [math]\displaystyle{ \mathcal{F}_1'=\{S\setminus\{n\}\mid S\in\mathcal{F}_1\} }[/math]. Clearly, [math]\displaystyle{ \mathcal{F}_1'\subseteq{[n-1]\choose k-1} }[/math]. If only it is also intersecting, we can apply the induction hypothesis, and indeed it is. To see this, by contradiction we assume that [math]\displaystyle{ \mathcal{F}_1' }[/math] is not intersecting. Then there must exist [math]\displaystyle{ A,B\in\mathcal{F} }[/math] such that [math]\displaystyle{ A\cap B=\{n\} }[/math], which means that [math]\displaystyle{ |A\cup B|\le 2k-1\lt n-1 }[/math]. Thus, there is some [math]\displaystyle{ 0\le i\le n-1 }[/math] such that [math]\displaystyle{ i\not\in A\cup B }[/math]. Since [math]\displaystyle{ \mathcal{F} }[/math] is shifted, [math]\displaystyle{ A_{in}=A\setminus\{n\}\cup\{i\}\in\mathcal{F} }[/math]. On the other hand it can be verified that [math]\displaystyle{ A_{in}\cap B=\emptyset }[/math], which contradicts that [math]\displaystyle{ \mathcal{F} }[/math] is intersecting. Thus, [math]\displaystyle{ \mathcal{F}_1'\subseteq{[n-1]\choose k-1} }[/math] and [math]\displaystyle{ \mathcal{F}_1' }[/math] is intersecting. Due to the induction hypothesis, [math]\displaystyle{ |\mathcal{F}_1'|\le{n-2\choose k-2} }[/math]. Combining these together, [math]\displaystyle{ |\mathcal{F}|=|\mathcal{F}_0|+|\mathcal{F}_1|=|\mathcal{F}_0|+|\mathcal{F}_1'|\le {n-2\choose k-1}+{n-2\choose k-2}={n-1\choose k-1} }[/math]. [math]\displaystyle{ \square }[/math]