슈페르너의 정리 (편집)

[[분류:가져온 문서/오메가]]
[[외부:https://pbs.twimg.com/media/E7fYezRX0AAqlbj.jpg|width=400]]
Sperner's Theorem

유한집합의 반사슬의 최대 크기에 대한 정리이다. 집합족 [math(\mathscr{F})]에 대하여 [math(\mathscr{F})]의 임의의 두 집합이 포함관계가 아닐 때 [math(\mathscr{F})]를 반사슬이라고 한다.

== 진술 ==
[math(N=\{1,2,\cdots,n\})]의 부분집합들로 이루어진 반사슬의 최대 크기는 [math(\binom{n}{[n/2]})]이다.

== 증명 ==
사슬을 [math(C_0 \subset C_1 \subset \cdots \subset C_n,\ \forall i\ C_i \subset N,\ \mid C_i \mid = i)]라 하자. 이 때 사슬의 총 개수는 [math(n!)]개 이다 ([math(N)]의 원소들을 나열하여 앞에서부터 [math(i)]개를 [math(C_i)]의 원소로 하면 사슬 하나에 대응시킬 수 있다).

반사슬 [math(\mathscr{F})]의 집합 중 원소의 개수가 [math(i)]개인 집합의 개수를 [math(m_i)]라 하자. 그러면 [math(\mathscr{F})]가 반사슬이므로 임의의 두 집합은 같은 사슬에 포함될 수 없다. [math(\mathscr{F})]의 한 집합 [math(A)]의 원소의 개수가 [math(i)]개이면 [math(A)]가 포함된 사슬의 개수는 [math(i!(n-i)!)]개이다 ([math(A)]가 포함된 사슬을 위에서와 같이 [math(N)]의 원소를 나열한 것으로 대응시킨다면 앞의 [math(i)]개 수는 [math(A)]의 원소들로 이미 정해져 있으므로 앞의 [math(i)]개 원소를 순서대로 나열하고 뒤의 [math(n-i)]개 수를 순서대로 나열하여 총 [math(i!(n-i)!)]개 사슬을 얻는다). [math(\mathscr{F})]의 원소 중 하나를 포함하는 사슬의 총 개수는 전체 사슬의 개수를 넘어서지 못하므로 다음 부등식을 얻을 수 있다.

[math(\sum_{i=1}^{n}m_i i!(n-i)! \leq n!)]
[math(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})]
[math(\therefore \mid \mathscr{F} \mid \leq \binom{n}{[n/2]})]

실례로는 크기가 [math([n/2])]인 [math(N)]의 부분집합들을 모아놓은 집합족이 존재한다.

== LYM 부등식 ==
Lubell–Yamamoto–Meshalkin inequality, LYM inequality

다음 부등식을 말한다.

> 슈페르너 족 [math(\mathcal F\subset2^{[n]})]에 대해 [math(\displaystyle \sum_{A\in\mathcal F}1/\binom n{|A|}\le1)]이다.

슈페르너의 정리는 이에서 자명하게 유도된다.

><math>|\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.</math>

===증명===
([math(\mathcal S_n)]은 [math([n])]에 대한 [[대칭군]]이다.)

각 [math(A\in\mathcal F)]에 대해 [math(S(A)=\{\sigma\in\mathcal S_n\mid\{\sigma(1),\dots,\sigma(|A|)\}=|A|\})]로 정의하자.

슈페르너 족의 정의에 의해 [math(A,A'\in\mathcal F)]일 때 [math(A\not\subset A',A'\not\subset A)]이므로 [math(S(A)\cap S(A')=\emptyset)]이 된다. 따라서

<math>\left|\bigcup_{A\in\mathcal F}S(A)\right|=\sum_{A\in\mathcal F}|S(A)|.</math>

[math(\bigcup_{A\in\mathcal F}S(A)\subset\mathcal S_n)]에서 [math(\text{LHS}\le n!)]이고, [math(\text{RHS}=\sum_{A\in\mathcal F}|A|!(n-|A|)!)]이므로, 원하는 식을 얻는다.

[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]

(임시 저장) (임시 저장 불러오기)

(↪️) (💎) (🛠️) (추가)