(+)분류 : 가져온 문서/오메가
Sperner's Theorem
유한집합의 반사슬의 최대 크기에 대한 정리이다. 집합족 \\mathscr{F}에 대하여 \\mathscr{F}의 임의의 두 집합이 포함관계가 아닐 때 \\mathscr{F}를 반사슬이라고 한다.
1. 진술 ✎ ⊖
N=\\{1,2,\\cdots,n\\}의 부분집합들로 이루어진 반사슬의 최대 크기는 \\binom{n}{[n/2]}이다.
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의 부분집합들을 모아놓은 집합족이 존재한다.
반사슬 \\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.
3.1. 증명 ✎ ⊖
(\\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|)!이므로, 원하는 식을 얻는다.
각 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|)!이므로, 원하는 식을 얻는다.
