组合数学 (Spring 2014)/Extremal set theory
Sperner system
A set family Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X} with the relation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \subseteq} define a poset. Thus, a chain is a sequence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_1\subseteq S_2\subseteq\cdots\subseteq S_k} .
A set family Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X} is an antichain (also called a Sperner system) if for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S,T\in\mathcal{F}} that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\neq T} , we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\not\subseteq T} .
The Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} -uniform Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle {X\choose k}} is an antichain. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n=|X|} . The size of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle {X\choose k}} is maximized when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k=\lfloor n/2\rfloor} . We wonder whether this is also the largest possible size of any antichain Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X} .
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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X}
where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n}
. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}}
is an antichain, then
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|\le{n\choose \lfloor n/2\rfloor}} .
- Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X}
where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n}
. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}}
is an antichain, then
First proof (shadows)
We first introduce the original proof by Sperner, which uses concepts called shadows and shades of set systems.
Definition - Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n\,} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq {X\choose k}} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k<n\,} .
- The shade of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}}
is defined to be
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \nabla\mathcal{F}=\left\{T\in {X\choose k+1}\,\,\bigg|\,\, \exists S\in\mathcal{F}\mbox{ such that } S\subset T\right\}} .
- Thus the shade Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \nabla\mathcal{F}} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} consists of all subsets of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} which can be obtained by adding an element to a set in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} .
- Similarly, the shadow of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}}
is defined to be
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta\mathcal{F}=\left\{T\in {X\choose k-1}\,\,\bigg|\,\, \exists S\in\mathcal{F}\mbox{ such that } T\subset S\right\}} .
- Thus the shadow Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta\mathcal{F}} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} consists of all subsets of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} which can be obtained by removing an element from a set in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} .
Next lemma bounds the effects of shadows and shades on the sizes of set systems.
Lemma (Sperner) - Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n\,}
and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq {X\choose k}}
. Then
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \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} }
- Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n\,}
and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq {X\choose k}}
. Then
Proof. The lemma is proved by double counting. We prove the inequality of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\nabla\mathcal{F}|} . Assume that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 0\le k<n} .
Define
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{R}=\{(S,T)\mid S\in\mathcal{F}, T\in\nabla\mathcal{F}, S\subset T\}} .
We estimate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{R}|} in two ways.
For each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\in\mathcal{F}} , there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n-k} different Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle T\in\nabla\mathcal{F}} that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\subset T} .
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{R}|=(n-k)|\mathcal{F}|} .
For each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle T\in\nabla\mathcal{F}} , there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k+1} ways to choose an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\subset T} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |S|=k} , some of which may not be in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} .
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{R}|\le (k+1)|\nabla\mathcal{F}|} .
Altogether, we show that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\nabla\mathcal{F}|\ge\frac{n-k}{k+1}|\mathcal{F}|} .
The inequality of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\Delta\mathcal{F}|} can be proved in the same way.
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
An immediate corollary of the previous lemma is as follows.
Proposition 1 - If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k\le \frac{n-1}{2}} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\nabla\mathcal{F}|\ge|\mathcal{F}|} .
- If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k\ge \frac{n-1}{2}} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\Delta\mathcal{F}|\ge|\mathcal{F}|} .
The idea of Sperner's proof is pretty clear:
- we "push up" all the sets in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle <\frac{n-1}{2}} replacing them by their shades;
- and also "push down" all the sets in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \ge\frac{n+1}{2}} replacing them by their shadows.
Repeat this process we end up with a set system Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq{X\choose \lfloor n/2\rfloor}} . We need to show that this process does not decrease the size of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} .
Proposition 2 - Suppose that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq2^X}
where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n}
. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_k=\mathcal{F}\cap{X\choose k}}
. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k_\min}
be the smallest Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k}
that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}_k|>0}
, and let
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}'=\begin{cases} \mathcal{F}\setminus\mathcal{F}_{k_\min}\cup \nabla\mathcal{F}_{k_\min} & \mbox{if }k_\min<\frac{n-1}{2},\\ \mathcal{F} & \mbox{otherwise.} \end{cases} }
- Similarly, let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k_\max}
be the largest Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k}
that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}_k|>0}
, and let
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}''=\begin{cases} \mathcal{F}\setminus\mathcal{F}_{k_\max}\cup \Delta\mathcal{F}_{k_\max} & \mbox{if }k_\max\ge\frac{n+1}{2},\\ \mathcal{F} & \mbox{otherwise.} \end{cases} }
- If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is an antichain, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}'} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}''} are antichains, and we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}'|\ge|\mathcal{F}|} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}''|\ge|\mathcal{F}|} .
- Suppose that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq2^X}
where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n}
. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_k=\mathcal{F}\cap{X\choose k}}
. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k_\min}
be the smallest Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k}
that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}_k|>0}
, and let
Proof. We show that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}'} is an antichain and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}'|\ge|\mathcal{F}|} .
First, observe that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \nabla\mathcal{F}_k\cap\mathcal{F}=\emptyset} , otherwise Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} cannot be an antichain, and due to Proposition 1, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\nabla\mathcal{F}_k|\ge|\mathcal{F}_k|} when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k\le \frac{n-1}{2}} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}'|=|\mathcal{F}|-|\mathcal{F}_k|+|\nabla\mathcal{F}_k|\ge |\mathcal{F}|} .
Now we prove that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}'} is an antichain . By contradiction, assume that there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S, T\in \mathcal{F}'} , such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\subset T} . One of the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S,T} must be in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \nabla\mathcal{F}_{k_\min}} , or otherwise Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} cannot be an antichain. Recall that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k_\min} is the smallest Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}_k|>0} , thus it must be Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\in \nabla\mathcal{F}_{k_\min}} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle T\in\mathcal{F}} . This implies that there is an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R\in \mathcal{F}_{k_\min}\subseteq \mathcal{F}} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R\subset S\subset T} , which contradicts that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is an antichain.
The statement for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}''} can be proved in the same way.
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
Applying the above process, we prove the Sperner's theorem.
Proof of Sperner's theorem (original proof of Sperner) Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_k=\{S\in\mathcal{F}\mid |S|=k\}} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 0\le k\le n} .
We change Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} as follows:
- for the smallest Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}_k|>0} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k<\frac{n-1}{2}} , replace Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_k} by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \nabla\mathcal{F}_k} .
Due to Proposition 2, this procedure preserves Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} as an antichain and does not decrease Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|} . Repeat this procedure, until Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}_k|=0} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k<\frac{n-1}{2}} , that is, there is no member set of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} has size less than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \frac{n-1}{2}} .
We then define another symmetric procedure:
- for the largest Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}_k|>0} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k\ge\frac{n+1}{2}} , replace Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_k} by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Delta\mathcal{F}_k} .
Also due to Proposition 2, this procedure preserves Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} as an antichain and does not decrease Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|} . After repeatedly applying this procedure, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}_k|=0} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k\ge\frac{n+1}{2}} .
The resulting Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} has Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq{X\choose \lfloor n/2\rfloor}} , and since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|} is never decreased, for the original Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} , we have
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|\le {n\choose \lfloor n/2\rfloor}} .
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
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.
Proof of Sperner's theorem (Lubell 1966) Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} be a permutation of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} . We say that an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\subseteq X} prefixes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S=\{\pi_1,\pi_2,\ldots, \pi_{|S|}\}} , that is, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} is precisely the set of the first Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |S|} elements in the permutation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} .
Fix an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\subseteq X} . It is easy to see that the number of permutations Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} prefixed by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |S|!(n-|S|)!} . Also, since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is an antichain, no permutation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} can be prefixed by more than one members of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} , otherwise one of the member sets must contain the other, which contradicts that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is an antichain. Thus, the number of permutations Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} prefixed by some Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\in\mathcal{F}} is
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \sum_{S\in\mathcal{F}}|S|!(n-|S|)!} ,
which cannot be larger than the total number of permutations, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n!} , therefore,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \sum_{S\in\mathcal{F}}|S|!(n-|S|)!\le n!} .
Dividing both sides by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n!} , we have
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}=\sum_{S\in\mathcal{F}}\frac{|S|!(n-|S|)!}{n!}\le 1} ,
where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle {n\choose |S|}\le {n\choose \lfloor n/2\rfloor}} , so
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\ge \frac{|\mathcal{F}|}{{n\choose \lfloor n/2\rfloor}}} .
Combining this with the above inequality, we prove the Sperner's theorem.
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
The LYM inequality
Lubell's proof proves the following inequality:
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le 1}
which is actually stronger than Sperner's original statement that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|\le{n\choose \lfloor n/2\rfloor}} .
This inequality is independently discovered by Lubell-Yamamoto, Meschalkin, and Bollobás, and is called the LYM inequality today.
Theorem (Lubell, Yamamoto 1954; Meschalkin 1963) - Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X}
where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n}
. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}}
is an antichain, then
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le 1} .
- Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X}
where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n}
. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}}
is an antichain, then
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.
Third proof (the probabilistic method) (Due to Alon.) Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} be a uniformly random permutation of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} . Define a random maximal chain by
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{C}_\pi=\{\{\pi_i\mid 1\le i\le k\}\mid 0\le k\le n\}} .
For any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\in\mathcal{F}} , let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_S} be the 0-1 random variable which indicates whether Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\in\mathcal{C}_\pi} , that is
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_S=\begin{cases} 1 & \mbox{if }S\in\mathcal{C}_\pi,\\ 0 & \mbox{otherwise.} \end{cases} }
Note that for a uniformly random Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{C}_\pi} has exact one member set of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |S|} , uniformly distributed over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle {X\choose |S|}} , thus
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathbf{E}[X_S]=\Pr[S\in\mathcal{C}_\pi]=\frac{1}{{n\choose |S|}}} .
Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X=\sum_{S\in\mathcal{F}}X_S} . Note that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X=|\mathcal{F}\cap\mathcal{C}_\pi|} . By the linearity of expectation,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathbf{E}[X]=\sum_{S\in\mathcal{F}}\mathbf{E}[X_S]=\sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}} .
On the other hand, since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is an antichain, it can never intersect a chain at more than one elements, thus we always have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X=|\mathcal{F}\cap\mathcal{C}_\pi|\le 1} . Therefore,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le \mathbf{E}[X] \le 1} .
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
The Sperner's theorem is an immediate consequence of the LYM inequality.
Proposition - Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\le 1} implies that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|\le{n\choose \lfloor n/2\rfloor}} .
Proof. It holds that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle {n\choose k}\le {n\choose \lfloor n/2\rfloor}} for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} . Thus,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 1\ge \sum_{S\in\mathcal{F}}\frac{1}{{n\choose |S|}}\ge \frac{|\mathcal{F}|}{{n\choose \lfloor n/2\rfloor}}} ,
which implies that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|\le {n\choose \lfloor n/2\rfloor}} .
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
Sunflowers
An set system is a sunflower if all its member sets intersect at the same set of elements.
Definition (sunflower) - A set family Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X}
is a sunflower of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r}
with a core Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle C\subseteq X}
if
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \forall S,T\in\mathcal{F}} that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\neq T} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\cap T=C} .
- A set family Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X}
is a sunflower of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r}
with a core Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle C\subseteq X}
if
Note that we do not require the core to be nonempty, thus a family of disjoint sets is also a sunflower (with the core Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \emptyset} ).
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.
Sunflower Lemma (Erdős-Rado) - Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq {X\choose k}} . If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|>k!(r-1)^k} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} contains a sunflower of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r} .
Proof. We proceed by induction on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} . For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k=1} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq{X\choose 1}} , thus all sets in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} are disjoint. And since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|>r-1} , we can choose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r} of these sets and form a sunflower.
Now let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k\ge 2} and assume the lemma holds for all smaller Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} . Take a maximal family Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{G}\subseteq \mathcal{F}} whose members are disjoint, i.e. for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S,T\in \mathcal{G}} that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\neq T} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\cap T=\emptyset} .
If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{G}|\ge r} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{G}} is a sunflower of size at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r} and we are done.
Assume that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{G}|\le r-1} , and let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y=\bigcup_{S\in\mathcal{G}}S} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |Y|=k|\mathcal{G}|\le k(r-1)} (since all members of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{G}} ) are disjoint). We claim that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y} intersets all members of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} , since if otherwise, there exists an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\in\mathcal{F}} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\cap Y=\emptyset} , then we can enlarge Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{G}} by adding Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{G}} and still have all members of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{G}} disjoint, which contradicts the assumption that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{G}} is the maximum of such families.
By the pigeonhole principle, some elements Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle y\in Y} must contained in at least
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \frac{|\mathcal{F}|}{|Y|}>\frac{k!(r-1)^k}{k(r-1)}=(k-1)!(r-1)^{k-1}}
members of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} . We delete this Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle y} from these sets and consider the family
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{H}=\{S\setminus\{y\}\mid S\in\mathcal{F}\wedge y\in S\}} .
We have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{H}\subseteq {X\choose k-1}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{H}|>(k-1)!(r-1)^{k-1}} , thus by the induction hypothesis, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{H}} contains a sunflower of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle r} . Adding Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle y} to the members of this sunflower, we get the desired sunflower in the original family Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} .
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
The Erdős–Ko–Rado Theorem
A set family Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X} is called intersecting, if for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S,T\in\mathcal{F}} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\cap T\neq\emptyset} . A natural question of extremal favor is: "how large can an intersecting family be?"
Assume Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n} . When Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n<2k} , every pair of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} -subsets of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} intersects. So the non-trivial case is when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n\le 2k} . 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.
Erdős–Ko–Rado theorem (proved in 1938, published in 1961) - Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq {X\choose k}}
where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n}
and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n\ge 2k}
. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}}
is intersecting, then
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|\le{n-1\choose k-1}} .
- Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq {X\choose k}}
where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n}
and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n\ge 2k}
. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}}
is intersecting, then
Katona's proof
We first introduce a proof discovered by Katona in 1972. The proof uses double counting.
Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} be a cyclic permutation of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} , that is, we think of assigning Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} in a circle and ignore the rotations of the circle. It is easy to see that there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle (n-1)!} cyclic permutations of an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} -set (each cyclic permutation corresponds to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} permutations). Let
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{G}_\pi=\{\{\pi_{(i+j)\bmod n}\mid j\in[k]\}\mid i\in [n]\}} .
The next lemma states the following observation: in a circle of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} points, supposed Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n\ge 2k} , there can be at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} arcs, each consisting of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} points, such that every pair of arcs share at least one point.
Lemma - Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq {X\choose k}} where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n\ge 2k} . If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is intersecting, then for any cyclic permutation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} , it holds that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{G}_\pi\cap\mathcal{F}|\le k} .
Proof. Fix a cyclic permutation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X} . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_i=\{\pi_{(i+j+n)\bmod n}\mid j\in[k]\}} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{G}_\pi} can be written as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{G}_\pi=\{A_i\mid i\in [n]\}} .
Suppose that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_t\in\mathcal{F}} . Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is intersecting, the only sets Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_i} that can be in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} other than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_t} itself are the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 2k-2} sets Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_i} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle t-(k-1)\le i\le t+k-1, i\neq t} . We partition these sets into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k-1} pairs Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{A_i,A_{i+k}\}} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle t-(k-1)\le i\le t-1} .
Note that for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n\ge 2k} , it holds that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_i\cap C_{i+k}=\emptyset} . Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is intersecting, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} can contain at most one set of each such pair. The lemma follows.
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
The Katona's proof of Erdős–Ko–Rado theorem is done by counting in two ways the pairs of member Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} and cyclic permutation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} which contain Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} as a continuous path on the circle (i.e., an arc).
Katona's proof of Erdős–Ko–Rado theorem (double counting) Let
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{R}=\{(S,\pi)\mid \pi \text{ is a cyclic permutation of }X, \text{and }S\in\mathcal{F}\cap\mathcal{G}_\pi\}} .
We count Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{R}} in two ways.
First, due to the lemma, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}\cap\mathcal{G}_\pi|\le k} for any cyclic permutation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} . There are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle (n-1)!} cyclic permutations in total. Thus,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{R}|=\sum_{\text{cyclic }\pi}|\mathcal{F}\cap\mathcal{G}_\pi|\le k(n-1)!} .
Next, for each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\in\mathcal{F}} , the number of cyclic permutations Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \pi} in which Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} is continuous is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |S|!(n-|S|)!=k!(n-k)!} . Thus,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{R}|=\sum_{S\in\mathcal{F}}k!(n-k)!=|\mathcal{F}|k!(n-k)!} .
Altogether, we have
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|\le\frac{k(n-1)!}{k!(n-k)!}=\frac{(n-1)!}{(k-1)!(n-k)!}={n-1\choose k-1}} .
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X=[n]} , and restate the Erdős–Ko–Rado theorem as follows.
Erdős–Ko–Rado theorem - Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq {[n]\choose k}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n\ge 2k} . If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is intersecting, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|\le{n-1\choose k-1}} .
We define a shift operator for the set family.
Definition (shift operator) - Assume Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^{[n]}}
, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 0\le i<j\le n-1}
. Define the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle (i,j)}
-shift Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_{ij}}
as an operator on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}}
as follows:
- for each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle T\in\mathcal{F}} , write Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle T_{ij}=(T\setminus\{j\})\cup\{i\} } , and let
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\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}}
- let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_{ij}(\mathcal{F})=\{S_{ij}(T)\mid T\in \mathcal{F}\}} .
- Assume Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^{[n]}}
, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 0\le i<j\le n-1}
. Define the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle (i,j)}
-shift Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_{ij}}
as an operator on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}}
as follows:
It is easy to verify the following propositions of shifts.
Proposition - Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |S_{ij}(T)|=|T|\,} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |S_{ij}(\mathcal{F})|=\mathcal{F}} ;
- if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is intersecting, then so is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_{ij}(\mathcal{F})} .
Proof. (1) is quite obvious. Now we prove (2).
Consider any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A,B\in\mathcal{F}} . If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A\cap B} includes any element other than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle j} then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle B} are still intersecting after Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle (i,j)} -shift. Thus without loss of generality, we may consider the only unsafe case where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A\cap B=\{j\}} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle B} is successfully shifted to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle B_{ij}=(B\setminus\{j\})\cup\{i\}} but Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A} fails to shift to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_{ij}=(A\setminus\{j\})\cup\{i\}} .
Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle B} is successfully shifted to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle B_{ij}} , we know that it must hold that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\not\in B} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle B_{ij}\not\in\mathcal{F}} . And the only two reasons for which Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A} may fail to shift to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_{ij}} are: (1) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\in A} and (2) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\not\in A} but Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_{ij}\in\mathcal{F}} .
Case.1: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\in A} . In this case, since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\in B_{ij}} , we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_{ij}(A)\cap S_{ij}(B)=A\cap B_{ij}=\{i\}} , i.e. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle B} is still intersecting with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A} after shifting.
Case.2: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\not\in A} but Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_{ij}\in\mathcal{F}} . In this case, it is easy to verify that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_{ij}\cap B=(A\cap B)\setminus\{j\}=\emptyset} . Recall that we assume Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_{ij}\in\mathcal{F}} . This contradicts to that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is intersecting.
In conclusion, in all cases, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_{ij}(\mathcal{F})} remains intersecting.
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
Repeatedly applying Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_{ij}(\mathcal{F})} for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 0\le i<j\le n-1} , since we only replace elements by smaller elements, eventually Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} will stop changing, that is, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_{ij}(\mathcal{F})=\mathcal{F}} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 0\le i<j\le n-1} . We call such an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} 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.
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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} . We assume that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is shifted.
First, it is trivial to see that the theorem holds for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k=1} (no matter whether shifted).
Next, we show that the theorem holds when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n=2k} (no matter whether shifted). For any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\in{X\choose k}} , both Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X\setminus S} are in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle {X\choose k}} , but at most one of them can be in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} . Thus,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\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}} .
We then apply the induction on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} . For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n> 2k} , the induction hypothesis is stated as:
- the Erdős-Ko-Rado theorem holds for any smaller Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} .
Define
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_0=\{S\in\mathcal{F}\mid n\not\in S\}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_1=\{S\in\mathcal{F}\mid n\in S\}} .
Clearly, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_0\subseteq{[n-1]\choose k}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_0} is intersecting. Due to the induction hypothesis, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}_0|\le{n-2\choose k-1}} .
In order to apply the induction, we let
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_1'=\{S\setminus\{n\}\mid S\in\mathcal{F}_1\}} .
Clearly, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_1'\subseteq{[n-1]\choose k-1}} . If only it is also intersecting, we can apply the induction hypothesis, and indeed it is. To see this, by contradiction we assume that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_1'} is not intersecting. Then there must exist Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A,B\in\mathcal{F}} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A\cap B=\{n\}} , which means that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |A\cup B|\le 2k-1<n-1} . Thus, there is some Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 0\le i\le n-1} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\not\in A\cup B} . Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is shifted, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_{in}=A\setminus\{n\}\cup\{i\}\in\mathcal{F}} . On the other hand it can be verified that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle A_{in}\cap B=\emptyset} , which contradicts that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is intersecting.
Thus, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_1'\subseteq{[n-1]\choose k-1}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}_1'} is intersecting. Due to the induction hypothesis, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}_1'|\le{n-2\choose k-2}} .
Combining these together,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\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}} .
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
Sauer's lemma and VC-dimension
Shattering and the VC-dimension
Definition (shatter) - Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X}
be set family and let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R\subseteq X}
be a subset. The trace of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}}
on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R}
, denoted Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}|_R}
is defined as
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}|_R=\{S\cap R\mid S\in\mathcal{F}\}} .
- We say that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} shatters Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}|_R=2^R} , i.e. for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle T\subseteq R} , there exists an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\in\mathcal{F}} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle T=S\cap R} .
- Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X}
be set family and let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R\subseteq X}
be a subset. The trace of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}}
on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R}
, denoted Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}|_R}
is defined as
The VC dimension is defined by the power of a family to shatter a set.
Definition (VC-dimension) - The Vapnik–Chervonenkis dimension (VC-dimension) of a set family Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X} , denoted Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \text{VC-dim}(\mathcal{F})} , is the size of the largest Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R\subseteq X} shattered by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} .
It is a core concept in computational learning theory.
Each subset Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\subseteq X} can be equivalently represented by its characteristic function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle f_S:X\rightarrow\{0,1\}} , such that for each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x\in X} ,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle f_S(x)=\begin{cases} 1 & x\in S\\ 0 & x\not\in S. \end{cases}}
Then a set family Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq2^X} corresponds to a collection of boolean functions Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{f_S\mid S\in\mathcal{F}\}} , which is a subset of all Boolean functions in the form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle f:X\rightarrow\{0,1\}} . We wonder on how large a subdomain Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y\subseteq X} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} includes all the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle 2^{|Y|}} mappings Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y\rightarrow\{0,1\}} . The largest size of such subdomain is the VC-dimension. It measures how complicated a collection of boolean functions (or equivalently a set family) is.
Sauer's Lemma
The definition of the VC-dimension involves enumerating all subsets, thus is difficult to analyze in general. The following famous result state a very simple sufficient condition to lower bound the VC-dimension, regarding only the size of the family. The lemma is due to Sauer, and independently due to Shelah and Perles. A slightly weaker version is found by Vapnik and Chervonenkis, who use the framework to develop a theory of classifications.
Sauer's Lemma (Sauer; Shelah-Perles; Vapnik-Chervonenkis) - Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X} where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n} . If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|>\sum_{1\le i<k}{n\choose i}} , then there exists an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R\in{X\choose k}} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} shatters Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} .
In other words, for any set family Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|>\sum_{1\le i<k}{n\choose i}} , its VC-dimension Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \text{VC-dim}(\mathcal{F})\ge k} .
Hereditary family
We note the Sauer's lemma is especially easy to prove for a special type of set families, called the hereditary families.
Definition (hereditary family) - A set system Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X}
is said to be hereditary (also called an ideal or an abstract simplicial complex), if
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\subseteq T\in\mathcal{F}} implies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S\in\mathcal{F}} .
- A set system Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X}
is said to be hereditary (also called an ideal or an abstract simplicial complex), if
In other words, for a hereditary family Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R\in\mathcal{F}} , then all subsets of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} are also in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} . An immediate consequence is the following proposition.
Proposition - Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} be a hereditary family. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R\in\mathcal{F}} then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} shatters Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} .
Therefore, it is very easy to prove the Sauer's lemma for hereditary families:
Lemma - For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^X} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |X|=n} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is hereditary and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|>\sum_{1\le i<k}{n\choose i}} then there exists an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R\in{X\choose k}} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} shatters Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} .
Proof. Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is hereditary, we only need to show that there exists an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R\in\mathcal{F}} of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |R|\ge k} , which must be true, because if all members of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} are of sizes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle <k} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|\le\left|\bigcup_{1\le i<k}{X\choose k}\right|=\sum_{1\le i<k}{n\choose i}} , a contradiction.
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
To prove the Sauer's lemma for general non-hereditary families, we can use some way to reduce arbitrary families to hereditary families. Here we apply the shifting technique to achieve this.
Down-shifts
Note that we work on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq2^X} , instead of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq{X\choose k}} like in the Erdős–Ko–Rado theorem, so we do not need to preserve the size of member sets. Instead, we need to reduce an arbitrary family to a hereditary one, thus we use a shift operator which replaces a member set by a subset of it.
Definition (down-shifts) - Assume Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^{[n]}}
, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\in[n]}
. Define the down-shift operator Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_{i}}
as follows:
- for each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle T\in\mathcal{F}} , let
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_{i}(T)= \begin{cases} T\setminus\{i\} & \mbox{if }i\in T \mbox{ and }T\setminus\{i\} \not\in\mathcal{F},\\ T & \mbox{otherwise;} \end{cases}}
- let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_{i}(\mathcal{F})=\{S_{i}(T)\mid T\in \mathcal{F}\}} .
- Assume Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^{[n]}}
, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\in[n]}
. Define the down-shift operator Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_{i}}
as follows:
Repeatedly applying Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_i} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\in[n]} , due to the finiteness, eventually Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is not changed by any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_i} . We call such a family down-shifted. A family Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is down-shifted if and only if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_i(\mathcal{F})=\mathcal{F}} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\in[n]} . It is then easy to see that a down-shifted Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} must be hereditary.
Theorem - If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq2^X} is down-shifted, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} is hereditary.
In order to use down-shift to prove the Sauer's lemma, we need to make sure that down-shift does not decrease Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}|} and does not increase the VC-dimension Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \text{VC-dim}(\mathcal{F})} .
Proposition - Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |S_{i}(\mathcal{F})|=\mathcal{F}} ;
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |S_i(\mathcal{F})|_R|\le |\mathcal{F}|_R|} , thus if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_{i}(\mathcal{F})} shatters an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} , so does Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} .
Proof. (1) is immediate. To prove (2), it is sufficient to prove that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_i(\mathcal{F})|_R\subseteq S_i(\mathcal{F}|_R)} and then apply (1).
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}
- Proof of Sauer's lemma
Now we can prove the Sauer's lemma for arbitrary Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^{[n]}} .
For any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}\subseteq 2^{[n]}} , repeatedly apply Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_i} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i\in} till the family is down-shifted, which is denoted by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}'} . We have proved that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}'|=|\mathcal{F}|>\sum_{1\le i<k}{n\choose i}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}'} is hereditary, thus as argued before, here exists an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle k} shattered by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}'} . By the above proposition, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |\mathcal{F}'|_R|\le |\mathcal{F}|_R|} , thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathcal{F}} also shatters Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle R} . The lemma is proved.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \square}