LYM inequality와 Sperner's theorem

2018. 7. 23. 16:02수학 이론/이산수학

방청소를 하다가 영재고 대비 시절의 교재를 발견했다. 그 교재 마지막 장에 과하게 졸려보이는 글씨로(...) 이 정리와 증명이 쓰여 있길래 대충 재구성해본다.


이걸 조사하면서 Sperner를 슈페르너로 읽는다는 걸 처음 알았다. 지금까지 스퍼너로 읽었는데 ㅁㄴㅇㄹ


Definition. (Sperner Family)


\([n] := \{1,2,\cdots n\}\)이라 할 때, \(\mathcal{F} \subset 2^{[n]}\)가 임의의 두 원소 \(A, B \in \mathcal{F}\)에 대해 \(A \subset B \Leftrightarrow A = B\)를 만족할 때 \(\mathcal{F}\)를 \([n]\)의 Sperner Family라고 한다. 

즉 \(\subset\)을 순서관계로 생각했을 때의 antichain과 동치이다.




Theorem. (Sperner, 1928)


\([n]\)의 Sperner family의 크기는 최대 \( \begin{pmatrix} n \\ \left \lfloor n/2 \right \rfloor \end{pmatrix} \)이다.




Lemma. (Lubell, 1966), a.k.a. LYM ineq.


\([n]\)의 Sperner family \(F\)의 원소 중 크기가 \(k\)인 것의 개수를 \(f_k\)라고 하자. 다음 부등식이 성립한다.

$$ \sum_{k=0}^{n} \frac{f_k}{\begin{pmatrix} n \\  k  \end{pmatrix}} \le 1 $$













등호는 \(F\)가 \([n]\)의 \(\left\lfloor \frac{n}{2} \right\rfloor\)-subset들을 모두 모아놓은 집합, 즉 \(F = \begin{bmatrix} n \\ [n/2] \end{bmatrix}\)일 때 성립한다.


일반적으로 \([n]\)의 k-subset들을 모아놓은 family를 \(\begin{bmatrix} n \\ k \end{bmatrix}\)라고 표기하기도 하는 모양이다. 

개인적으로 


- \(\left|\begin{bmatrix} n \\ k \end{bmatrix}\right| = \begin{pmatrix} n \\ k \end{pmatrix}\).

- \(\bigcup\limits_{i=0}^{n} \begin{bmatrix} n \\ k \end{bmatrix} = 2^{[n]}\)


의 사실과 호환된다는 점에서 잘 만든 표기라고 생각한다.

사족으로, 모든 \(\begin{bmatrix} n \\ k \end{bmatrix}\)들은 자명히 Sperner family가 된다.