Sperner's Theorem
유한집합의 반사슬의 최대 크기에 대한 정리이다. 집합족
\mathscr{F}에 대하여
\mathscr{F}의 임의의 두 집합이 포함관계가 아닐 때
\mathscr{F}를 반사슬이라고 한다.
목차
1. 진술
2. 증명
3. LYM 부등식
3.1. 증명
N=\{1,2,\cdots,n\}의 부분집합들로 이루어진 반사슬의 최대 크기는 \binom{n}{[n/2]}이다.
사슬을 C_0 \subset C_1 \subset \cdots \subset C_n,\ \forall i\ C_i \subset N,\ \mid C_i \mid = i라 하자. 이 때 사슬의 총 개수는 n!개 이다 (N의 원소들을 나열하여 앞에서부터 i개를 C_i의 원소로 하면 사슬 하나에 대응시킬 수 있다).
반사슬 \mathscr{F}의 집합 중 원소의 개수가 i개인 집합의 개수를 m_i라 하자. 그러면 \mathscr{F}가 반사슬이므로 임의의 두 집합은 같은 사슬에 포함될 수 없다. \mathscr{F}의 한 집합 A의 원소의 개수가 i개이면 A가 포함된 사슬의 개수는 i!(n-i)!개이다 (A가 포함된 사슬을 위에서와 같이 N의 원소를 나열한 것으로 대응시킨다면 앞의 i개 수는 A의 원소들로 이미 정해져 있으므로 앞의 i개 원소를 순서대로 나열하고 뒤의 n-i개 수를 순서대로 나열하여 총 i!(n-i)!개 사슬을 얻는다). \mathscr{F}의 원소 중 하나를 포함하는 사슬의 총 개수는 전체 사슬의 개수를 넘어서지 못하므로 다음 부등식을 얻을 수 있다.
\sum_{i=1}^{n}m_i i!(n-i)! \leq n!
1 \geq \sum_{i=1}^{n}m_i \frac{i!(n-i)!}{n!} \geq \sum_{i=1}^{n}m_i \binom{n}{i}^{-1} \geq \sum_{i=1}^{n}m_i \binom{n}{[n/2]}^{-1} = \mid \mathscr{F} \mid \binom{n}{[n/2]}^{-1}
\therefore \mid \mathscr{F} \mid \leq \binom{n}{[n/2]}
실례로는 크기가 [n/2]인 N의 부분집합들을 모아놓은 집합족이 존재한다.
3. LYM 부등식 ✎
Lubell–Yamamoto–Meshalkin inequality, LYM inequality
다음 부등식을 말한다.
슈페르너 족 \mathcal F\subset2^{[n]}에 대해 \displaystyle \sum_{A\in\mathcal F}1/\binom n{|A|}\le1이다.
슈페르너의 정리는 이에서 자명하게 유도된다.
|\mathcal F|/\binom n{[n/2]}\le\sum_{A\in\mathcal F}1/\binom n{[n/2]}\le\sum_{A\in\mathcal F}1/\binom n{|A|}\le1.
(
\mathcal S_n은
[n]에 대한
대칭군이다.)
각
A\in\mathcal F에 대해
S(A)=\{\sigma\in\mathcal S_n\mid\{\sigma(1),\dots,\sigma(|A|)\}=|A|\}로 정의하자.
슈페르너 족의 정의에 의해
A,A'\in\mathcal F일 때
A\not\subset A',A'\not\subset A이므로
S(A)\cap S(A')=\emptyset이 된다. 따라서
\left|\bigcup_{A\in\mathcal F}S(A)\right|=\sum_{A\in\mathcal F}|S(A)|.\bigcup_{A\in\mathcal F}S(A)\subset\mathcal S_n에서
\text{LHS}\le n!이고,
\text{RHS}=\sum_{A\in\mathcal F}|A|!(n-|A|)!이므로, 원하는 식을 얻는다.
