Combinatorics (Fall 2010)/Extremal set theory

2010-12-05T07:53:38Z

172.21.15.93: /* First proof (shadows) */

== Sperner system ==
A set family <math>\mathcal{F}\subseteq 2^X</math> with the relation <math>\subseteq</math> define a poset. Thus, a '''chain''' is a sequence <math>S_1\subseteq S_2\subseteq\cdots\subseteq S_k</math>.

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

The <math>k</math>-uniform <math>{X\choose k}</math> is an antichain. Let <math>n=|X|</math>. The size of <math>{X\choose k}</math> is maximized when <math>k=\lfloor n/2\rfloor</math>. We wonder whether this is also the largest possible size of any antichain <math>\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|Theorem (Sperner 1928)|
:Let <math>\mathcal{F}\subseteq 2^X</math> where <math>|X|=n</math>. If <math>\mathcal{F}</math> is an antichain, then
::<math>|\mathcal{F}|\le{n\choose \lfloor n/2\rfloor}</math>.
}}

=== First proof (shadows)===
We first introduce the original proof by Sperner, which uses concepts called '''shadows''' and '''shades''' of set systems.

{{Theorem|Definition|
:Let <math>|X|=n\,</math> and <math>\mathcal{F}\subseteq {X\choose k}</math>, <math>k<n\,</math>.
:The '''shade''' of <math>\mathcal{F}</math> is defined to be
::<math>\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>\nabla\mathcal{F}</math> of <math>\mathcal{F}</math> consists of all subsets of <math>X</math> which can be obtained by adding an element to a set in <math>\mathcal{F}</math>.
:Similarly, the '''shadow''' of <math>\mathcal{F}</math> is defined to be
::<math>\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>\Delta\mathcal{F}</math> of <math>\mathcal{F}</math> consists of all subsets of <math>X</math> which can be obtained by removing an element from a set in <math>\mathcal{F}</math>.
}}

Next lemma bounds the effects of shadows and shades on the sizes of set systems.

{{Theorem|Lemma (Sperner)|
:Let <math>|X|=n\,</math> and <math>\mathcal{F}\subseteq {X\choose k}</math>. Then
::<math>
\begin{align}
&|\nabla\mathcal{F}|\ge\frac{n-k}{k+1}|\mathcal{F}| &\text{ if } k<n\\
&|\Delta\mathcal{F}|\ge\frac{k}{n-k+1}|\mathcal{F}| &\text{ if } k>0.
\end{align}
</math>
}}

{{Proof|
The lemma is proved by double counting. We prove the inequality of <math>|\nabla\mathcal{F}|</math>. Assume that <math>0\le k<n</math>.

Define
:<math>\mathcal{R}=\{(S,T)\mid S\in\mathcal{F}, T\in\nabla\mathcal{F}, S\subset T\}</math>.
We estimate <math>|\mathcal{R}|</math> in two ways.

For each <math>S\in\mathcal{F}</math>, there are <math>n-k</math> different <math>T\in\nabla\mathcal{F}</math> that <math>S\subset T</math>.
:<math>|\mathcal{R}|=(n-k)|\mathcal{F}|</math>.
For each <math>T\in\nabla\mathcal{F}</math>, there are <math>k+1</math> ways to choose an <math>S\subset T</math> with <math>|S|=k</math>, some of which may not be in <math>\mathcal{F}</math>.
:<math>|\mathcal{R}|\le (k+1)|\nabla\mathcal{F}|</math>.

Altogether, we show that <math>|\nabla\mathcal{F}|\ge\frac{n-k}{k+1}|\mathcal{F}|</math>.

The inequality of <math>|\Delta\mathcal{F}|</math> can be proved in the same way.
}}

An immediate corollary of the previous lemma is as follows.

{{Theorem|Proposition 1|
:If <math>k\le \frac{n-1}{2}</math>, then <math>|\nabla\mathcal{F}|\ge|\mathcal{F}|</math>.
:If <math>k\ge \frac{n-1}{2}</math>, then <math>|\Delta\mathcal{F}|\ge|\mathcal{F}|</math>.
}}

The idea of Sperner's proof is pretty clear:
* we "push up" all the sets in <math>\mathcal{F}</math> of size <math><\frac{n-1}{2}</math> replacing them by their shades;
* and also "push down" all the sets in <math>\mathcal{F}</math> of size <math>\ge\frac{n+1}{2}</math> replacing them by their shadows.
Repeat this process we end up with a set system <math>\mathcal{F}\subseteq{X\choose \lfloor n/2\rfloor}</math>. We need to show that this process does not decrease the size of <math>\mathcal{F}</math>.

{{Theorem|Proposition 2|
:Suppose that <math>\mathcal{F}\subseteq2^X</math> where <math>|X|=n</math>. Let <math>k_\min</math> be the smallest <math>k</math> that <math>|\mathcal{F}_k|>0</math>, and let
::<math>
\mathcal{F}'=\begin{cases}
\mathcal{F}\setminus\mathcal{F}_k\cup \nabla\mathcal{F}_k & \mbox{if }k_\min<\frac{n-1}{2},\\
\mathcal{F} & \mbox{otherwise.}
\end{cases}
</math>
:Similarly, let <math>k_\max</math> be the largest <math>k</math> that <math>|\mathcal{F}_k|>0</math>, and let
::<math>
\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>\mathcal{F}</math> is an antichain, <math>\mathcal{F}'</math> and <math>\mathcal{F}''</math> are antichains, and we have <math>|\mathcal{F}'|\ge|\mathcal{F}|</math> and <math>|\mathcal{F}''|\ge|\mathcal{F}|</math>.
}}
{{Proof|
We show that <math>\mathcal{F}'</math> is an antichain and <math>|\mathcal{F}'|\ge|\mathcal{F}|</math>.

First, observe that <math>\nabla\mathcal{F}_k\cap\mathcal{F}=\emptyset</math>, otherwise <math>\mathcal{F}</math> cannot be an antichain, and due to Proposition 1, <math>|\nabla\mathcal{F}_k|\ge|\mathcal{F}_k|</math> when <math>k\le \frac{n-1}{2}</math>, so <math>|\mathcal{F}'|=|\mathcal{F}|-|\mathcal{F}_k|+|\nabla\mathcal{F}_k|\ge |\mathcal{F}|</math>.

Now we prove that <math>\mathcal{F}'</math> is an antichain . By contradiction, assume that there are <math>S, T\in \mathcal{F}'</math>, such that <math>S\subset T</math>. One of the <math>S,T</math> must be in <math>\nabla\mathcal{F}_k</math>, or otherwise <math>\mathcal{F}</math> cannot be an antichain. Recall that <math>k_\min</math> is the smallest <math>k</math> that <math>|\mathcal{F}_k|>0</math>, thus it must be <math>S\in \nabla\mathcal{F}_k</math>, and <math>T\in\mathcal{F}</math>. This implies that there is an <math>R\in \mathcal{F}_k\subseteq \mathcal{F}</math> such that <math>R\subset S\subset T</math>, which contradicts that <math>\mathcal{F}</math> is an antichain.

The statement for <math>\mathcal{F}''</math> can be proved in the same way.
}}

Applying the above process, we prove the Sperner's theorem.
{{Prooftitle|Proof of Sperner's theorem | (original proof of Sperner)
Let <math>\mathcal{F}_k=\{S\in\mathcal{F}\mid |S|=k\}</math>, where <math>0\le k\le n</math>.

We change <math>\mathcal{F}</math> as follows:
* for the smallest <math>k</math> that <math>|\mathcal{F}_k|>0</math>, if <math>k<\frac{n-1}{2}</math>, replace <math>\mathcal{F}_k</math> by <math>\nabla\mathcal{F}_k</math>.

Due to Proposition 2, this procedure preserves <math>\mathcal{F}</math> as an antichain and does not decrease <math>|\mathcal{F}|</math>. Repeat this procedure, until <math>|\mathcal{F}_k|=0</math> for all <math>k<\frac{n-1}{2}</math>, that is, there is no member set of <math>\mathcal{F}</math> has size less than <math>\frac{n-1}{2}</math>.

We then define another symmetric procedure:
* for the largest <math>k</math> that <math>|\mathcal{F}_k|>0</math>, if <math>k\ge\frac{n+1}{2}</math>, replace <math>\mathcal{F}_k</math> by <math>\Delta\mathcal{F}_k</math>.
Also due to Proposition 2, this procedure preserves <math>\mathcal{F}</math> as an antichain and does not decrease <math>|\mathcal{F}|</math>. After repeatedly applying this procedure, <math>|\mathcal{F}_k|=0</math> for all <math>k\ge\frac{n+1}{2}</math>.

The resulting <math>\mathcal{F}</math> has <math>\mathcal{F}\subseteq{X\choose \lfloor n/2\rfloor}</math>, and since <math>|\mathcal{F}|</math> is never decreased, for the original <math>\mathcal{F}</math>, we have
:<math>|\mathcal{F}|\le {n\choose \lfloor n/2\rfloor}</math>.
}}

=== Second proof (counting)===
We now introduce an elegant proof due to Lubell. The proof uses a counting argument, and tells more information than just the size of the set system.

{{Prooftitle|Proof of Sperner's theorem | (Lubell 1966)
Let <math>\pi</math> be a permutation of <math>X</math>. We say that an <math>S\subseteq X</math> '''prefixes''' <math>\pi</math>, if <math>S=\{\pi_1,\pi_2,\ldots, \pi_{|S|}\}</math>, that is, <math>S</math> is precisely the set of the first <math>|S|</math> elements in the permutation <math>\pi</math>.

Fix an <math>S\subseteq X</math>. It is easy to see that the number of permutations <math>\pi</math> of <math>X</math> prefixed by <math>S</math> is <math>|S|!(n-|S|)!</math>. Also, since <math>\mathcal{F}</math> is an antichain, no permutation <math>\pi</math> of <math>X</math> can be prefixed by more than one members of <math>\mathcal{F}</math>, otherwise one of the member sets must contain the other, which contradicts that <math>\mathcal{F}</math> is an antichain. Thus, the number of permutations <math>\pi</math> prefixed by some <math>S\in\mathcal{F}</math> is
:<math>\sum_{S\in\mathcal{F}}|S|!(n-|S|)!</math>,
which cannot be larger than the total number of permutations, <math>n!</math>, therefore,
:<math>\sum_{S\in\mathcal{F}}|S|!(n-|S|)!\le n!</math>.
Dividing both sides by <math>n!</math>, we have
:<math>\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>{n\choose |S|}\le {n\choose \lfloor n/2\rfloor}</math>, so
:<math>\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.
}}

=== The LYM inequality ===
Lubell's proof proves the following inequality:
:<math>\sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le 1</math>
which is actually stronger than Sperner's original statement that <math>|\mathcal{F}|\le{n\choose \lfloor n/2\rfloor}</math>.

This inequality is independently discovered by Lubell-Yamamoto, Meschalkin, and Bollobás, and is called the LYM inequality today.

{{Theorem|Theorem (Lubell, Yamamoto 1954; Meschalkin 1963)|
:Let <math>\mathcal{F}\subseteq 2^X</math> where <math>|X|=n</math>. If <math>\mathcal{F}</math> is an antichain, then
::<math>\sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le 1</math>.
}}

In Lubell's counting argument proves the LYM inequality, which implies the Sperner's theorem. Here we give another proof of the LYM inequality by the probabilistic method, due to Noga Alon.

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

The Sperner's theorem is an immediate consequence of the LYM inequality.

{{Theorem|Proposition|
:<math>\sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le 1</math> implies that <math>|\mathcal{F}|\le{n\choose \lfloor n/2\rfloor}</math>.
}}
{{Proof|
It holds that <math>{n\choose k}\le {n\choose \lfloor n/2\rfloor}</math> for any <math>k</math>. Thus,
:<math>1\ge \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\ge \frac{|\mathcal{F}|}{{n\choose \lfloor n/2\rfloor}}</math>,
which implies that <math>|\mathcal{F}|\le {n\choose \lfloor n/2\rfloor}</math>.
}}

== Sunflowers ==
An set system is a '''sunflower''' if all its member sets intersect at the same set of elements.
{{Theorem|Definition (sunflower)|
: A set family <math>\mathcal{F}\subseteq 2^X</math> is a '''sunflower''' of size <math>r</math> with a '''core''' <math>C\subseteq X</math> if
::<math>\forall S,T\in\mathcal{F}</math> that <math>S\neq T</math>, <math>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>\emptyset</math>).

The next result due to Erdős and Rado, called the sunflower lemma, is a famous result in extremal set theory, and has some important applications in Boolean circuit complexity.
{{Theorem|Sunflower Lemma (Erdős-Rado)|
:Let <math>\mathcal{F}\subseteq {X\choose k}</math>. If <math>|\mathcal{F}|>k!(r-1)^k</math>, then <math>\mathcal{F}</math> contains a sunflower of size <math>r</math>.
}}
{{Proof|
We proceed by induction on <math>k</math>. For <math>k=1</math>, <math>\mathcal{F}\subseteq{X\choose 1}</math>, thus all sets in <math>\mathcal{F}</math> are disjoint. And since <math>|\mathcal{F}|>r-1</math>, we can choose <math>r</math> of these sets and form a sunflower.

Now let <math>k\ge 2</math> and assume the lemma holds for all smaller <math>k</math>. Take a maximal family <math>\mathcal{G}\subseteq \mathcal{F}</math> whose members are disjoint, i.e. for any <math>S,T\in \mathcal{G}</math> that <math>S\neq T</math>, <math>S\cap T=\emptyset</math>.

If <math>|\mathcal{G}|\ge r</math>, then <math>\mathcal{G}</math> is a sunflower of size at least <math>r</math> and we are done.

Assume that <math>|\mathcal{G}|\le r-1</math>, and let <math>Y=\bigcup_{S\in\mathcal{G}}S</math>. Then <math>|Y|=k|\mathcal{G}|\le k(r-1)</math> (since all members of <math>\mathcal{G}</math>) are disjoint). We claim that <math>Y</math> intersets all members of <math>\mathcal{F}</math>, since if otherwise, there exists an <math>S\in\mathcal{F}</math> such that <math>S\cap Y=\emptyset</math>, then we can enlarge <math>\mathcal{G}</math> by adding <math>S</math> into <math>\mathcal{G}</math> and still have all members of <math>\mathcal{G}</math> disjoint, which contradicts the assumption that <math>\mathcal{G}</math> is the maximum of such families.

By the pigeonhole principle, some elements <math>y\in Y</math> must contained in at least
:<math>\frac{|\mathcal{F}|}{|Y|}>\frac{k!(r-1)^k}{k(r-1)}=(k-1)!(r-1)^{k-1}</math>
members of <math>\mathcal{F}</math>. We delete this <math>y</math> from these sets and consider the family
:<math>\mathcal{H}=\{S\setminus\{y\}\mid S\in\mathcal{F}\wedge y\in S\}</math>.
We have <math>\mathcal{H}\subseteq {X\choose k-1}</math> and <math>|\mathcal{H}|>(k-1)!(r-1)^{k-1}</math>, thus by the induction hypothesis, <math>\mathcal{H}</math>contains a sunflower of size <math>r</math>. Adding <math>y</math> to the members of this sunflower, we get the desired sunflower in the original family <math>\mathcal{F}</math>.
}}

==The Erdős–Ko–Rado Theorem ==
A set family <math>\mathcal{F}\subseteq 2^X</math> is called '''intersecting''', if for any <math>S,T\in\mathcal{F}</math>, <math>S\cap T\neq\emptyset</math>. A natural question of extremal favor is: "how large can an intersecting family be?"

Assume <math>|X|=n</math>. When <math>n<2k</math>, every pair of <math>k</math>-subsets of <math>X</math> intersects. So the non-trivial case is when <math>n\le 2k</math>. The famous Erdős–Ko–Rado theorem gives the largest possible cardinality of a nontrivially intersecting family.

According to Erdős, the theorem itself was proved in 1938, but was not published until 23 years later.
{{Theorem|Erdős–Ko–Rado theorem (proved in 1938, published in 1961)|
:Let <math>\mathcal{F}\subseteq {X\choose k}</math> where <math>|X|=n</math> and <math>n\ge 2k</math>. If <math>\mathcal{F}</math> is intersecting, then
::<math>|\mathcal{F}|\le{n-1\choose k-1}</math>.
}}

=== Katona's proof ===
We first introduce a proof discovered by Katona in 1972. The proof uses double counting.

Let <math>\pi</math> be a '''cyclic permutation''' of <math>X</math>, that is, we think of assigning <math>X</math> in a circle and ignore the rotations of the circle. It is easy to see that there are <math>(n-1)!</math> cyclic permutations of an <math>n</math>-set (each cyclic permutation corresponds to <math>n</math> permutations).
Let
:<math>\mathcal{G}_\pi=\{\{\pi_{(i+j)\bmod n}\mid j\in[k]\}\mid i\in [n]\}</math>.

The next lemma states the following observation: in a circle of <math>n</math> points, supposed <math>n\ge 2k</math>, there can be at most <math>k</math> arcs, each consisting of <math>k</math> points, such that every pair of arcs share at least one point.
{{Theorem|Lemma|
:Let <math>\mathcal{F}\subseteq {X\choose k}</math> where <math>|X|=n</math> and <math>n\ge 2k</math>. If <math>\mathcal{F}</math> is intersecting, then for any cyclic permutation <math>\pi</math> of <math>X</math>, it holds that <math>|\mathcal{G}_\pi\cap\mathcal{F}|\le k</math>.
}}
{{Proof|
Fix a cyclic permutation <math>\pi</math> of <math>X</math>. Let <math>A_i=\{\pi_{(i+j+n)\bmod n}\mid j\in[k]\}</math>. Then <math>\mathcal{G}_\pi</math> can be written as <math>\mathcal{G}_\pi=\{A_i\mid i\in [n]\}</math>.

Suppose that <math>A_t\in\mathcal{F}</math>. Since <math>\mathcal{F}</math> is intersecting, the only sets <math>A_i</math> that can be in <math>\mathcal{F}</math> other than <math>A_t</math> itself are the <math>2k-2</math> sets <math>A_i</math> with <math>t-(k-1)\le i\le t+k-1, i\neq t</math>. We partition these sets into <math>k-1</math> pairs <math>\{A_i,A_{i+k}\}</math>, where <math>t-(k-1)\le i\le t-1</math>.

Note that for <math>n\ge 2k</math>, it holds that <math>A_i\cap C_{i+k}=\emptyset</math>. Since <math>\mathcal{F}</math> is intersecting, <math>\mathcal{F}</math> can contain at most one set of each such pair. The lemma follows.
}}

The Katona's proof of Erdős–Ko–Rado theorem is done by counting in two ways the pairs of member <math>S</math> of <math>\mathcal{F}</math> and cyclic permutation <math>\pi</math> which contain <math>S</math> as a continuous path on the circle (i.e., an arc).

{{Prooftitle|Katona's proof of Erdős–Ko–Rado theorem|(double counting)
Let
:<math>\mathcal{R}=\{(S,\pi)\mid \pi \text{ is a cyclic permutation of }X, \text{and }S\in\mathcal{F}\cap\mathcal{G}_\pi\}</math>.
We count <math>\mathcal{R}</math> in two ways.

First, due to the lemma, <math>|\mathcal{F}\cap\mathcal{G}_\pi|\le k</math> for any cyclic permutation <math>\pi</math>. There are <math>(n-1)!</math> cyclic permutations in total. Thus,
:<math>|\mathcal{R}|=\sum_{\text{cyclic }\pi}|\mathcal{F}\cap\mathcal{G}_\pi|\le k(n-1)!</math>.

Next, for each <math>S\in\mathcal{F}</math>, the number of cyclic permutations <math>\pi</math> in which <math>S</math> is continuous is <math>|S|!(n-|S|)!=k!(n-k)!</math>. Thus,
:<math>|\mathcal{R}|=\sum_{S\in\mathcal{F}}k!(n-k)!=|\mathcal{F}|k!(n-k)!</math>.

Altogether, we have
:<math>|\mathcal{F}|\le\frac{k(n-1)!}{k!(n-k)!}=\frac{(n-1)!}{(k-1)!(n-k)!}={n-1\choose k-1}</math>.
}}

=== Erdős' shifting technique ===
We now introduce the original proof of the Erdős–Ko–Rado theorem, which uses a technique called '''shifting''' (originally called '''compression''').

Without loss of generality, we assume <math>X=[n]</math>, and restate the Erdős–Ko–Rado theorem as follows.
{{Theorem|Erdős–Ko–Rado theorem|
:Let <math>\mathcal{F}\subseteq {[n]\choose k}</math> and <math>n\ge 2k</math>. If <math>\mathcal{F}</math> is intersecting, then <math>|\mathcal{F}|\le{n-1\choose k-1}</math>.
}}

We define a '''shift operator''' for the set family.
{{Theorem|Definition (shift operator)|
: Assume <math>\mathcal{F}\subseteq 2^{[n]}</math>, and <math>0\le i<j\le n-1</math>. Define the '''<math>(i,j)</math>-shift''' <math>S_{ij}</math> as an operator on <math>\mathcal{F}</math> as follows:
:*for each <math>T\in\mathcal{F}</math>, write <math>T_{ij}=(T\setminus\{j\})\cup\{i\} </math>, and let
::<math>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>S_{ij}(\mathcal{F})=\{S_{ij}(T)\mid T\in \mathcal{F}\}</math>.
}}

It is easy to verify the following propositions of shifts.

{{Theorem|Proposition|
# <math>|S_{ij}(T)|=|T|\,</math> and <math>|S_{ij}(\mathcal{F})|=\mathcal{F}</math>;
# if <math>\mathcal{F}</math> is intersecting, then so is <math>S_{ij}(\mathcal{F})</math>.
}}
{{Proof|
(1) is immediate. Now we prove (2).

Let <math>A,B\in\mathcal{F}</math>. All the cases are easy to dealt with except when <math>A\cap B=\{j\}</math>, <math>i\in A</math>, and <math>i\not\in B</math>. Denote <math>A_{ij}=A\setminus\{j\}\cup\{i\}</math>. It holds that <math>A_{ij}\cap B=(A\cap B)\setminus\{j\}=\emptyset</math>. Since <math>\mathcal{F}</math> is intersecting, it must hold that <math>A_{ij}\not\in\mathcal{F}</math>. Thus, <math>S_{ij}(A)=A_{ij}</math> and clearly <math>S_{ij}(B)=B_{ij}=B\setminus\{j\}\cup\{i\}</math>. Therefore, <math>i\in S_{ij}(A)\cap S_{ij}(B)</math> thus <math>S_{ij}(A)\cap S_{ij}(B)\neq \emptyset</math>.
}}

Repeatedly applying <math>S_{ij}(\mathcal{F})</math> for any <math>0\le i<j\le n-1</math>, since we only replace elements by smaller elements, eventually <math>\mathcal{F}</math> will stop changing, that is, <math>S_{ij}(\mathcal{F})=\mathcal{F}</math> for all <math>0\le i<j\le n-1</math>. We call such an <math>\mathcal{F}</math> '''shifted'''.

The idea behind the shifting technique is very natural: by applying shifting, all intersecting families are transformed to some ''special forms'', and we only need to prove the theorem for these special form of intersecting families.

{{Prooftitle|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>\mathcal{F}</math>. We assume that <math>\mathcal{F}</math> is shifted.

First, it is trivial to see that the theorem holds for <math>k=1</math> (no matter whether shifted).

Next, we show that the theorem holds when <math>n=2k</math> (no matter whether shifted). For any <math>S\in{X\choose k}</math>, both <math>S</math> and <math>X\setminus S</math> are in <math>{X\choose k}</math>, but at most one of them can be in <math>\mathcal{F}</math>. Thus,
:<math>|\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>n</math>. For <math>n> 2k</math>, the induction hypothesis is stated as:
* the Erdős-Ko-Rado theorem holds for any smaller <math>n</math>.
Define
:<math>\mathcal{F}_0=\{S\in\mathcal{F}\mid n\not\in S\}</math> and <math>\mathcal{F}_1=\{S\in\mathcal{F}\mid n\in S\}</math>.
Clearly, <math>\mathcal{F}_0\subseteq{[n-1]\choose k}</math> and <math>\mathcal{F}_0</math> is intersecting. Due to the induction hypothesis, <math>|\mathcal{F}_0|\le{n-2\choose k-1}</math>.

In order to apply the induction, we let
:<math>\mathcal{F}_1'=\{S\setminus\{n\}\mid S\in\mathcal{F}_1\}</math>.
Clearly, <math>\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>\mathcal{F}_1'</math> is not intersecting. Then there must exist <math>A,B\in\mathcal{F}</math> such that <math>A\cap B=\{n\}</math>, which means that <math>|A\cup B|\le 2k-1<n-1</math>. Thus, there is some <math>0\le i\le n-1</math> such that <math>i\not\in A\cup B</math>. Since <math>\mathcal{F}</math> is shifted, <math>A_{in}=A\setminus\{n\}\cup\{i\}\in\mathcal{F}</math>. On the other hand it can be verified that <math>A_{in}\cap B=\emptyset</math>, which contradicts that <math>\mathcal{F}</math> is intersecting.

Thus, <math>\mathcal{F}_1'\subseteq{[n-1]\choose k-1}</math> and <math>\mathcal{F}_1'</math> is intersecting. Due to the induction hypothesis, <math>|\mathcal{F}_1'|\le{n-2\choose k-2}</math>.

Combining these together,
:<math>|\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>.
}}

== References ==
:('''声明:''' 资料受版权保护, 仅用于教学.)
:('''Disclaimer:''' The following copyrighted materials are meant for educational uses only.)

* van Lin and Wilson. ''A course in combinatorics.'' Cambridge Press. Chapter 6.
* Aigner and Ziegler. ''Proofs from THE BOOK, 4th Edition.'' Springer-Verlag. [[media:PFTB_chap27.pdf| Chapter 27]].

TCS Wiki - User contributions [en]

Combinatorics (Fall 2010)/Extremal set theory