LYM inequality와 Sperner's theorem

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

이걸 조사하면서 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$$

---

임의의 $A \in F$에 대해, 다음의 집합열 $\{S_i\}$을 $A$-chain이라 하자. 단, $|S_i| = i$이다.

$$\emptyset = S_0 \subset S_1 \subset S_2 \subset \cdots \subset S_{|A|}=A \subset \cdots \subset S_n = [n]$$

이 때 가능한 $A$-chain의 개수는 $|A|!(n-|A|)!$개이다. 

- $S_1 \dots S_{|A|}$까지, $S_{i-1}$로부터 $S_i$를 만들면서 추가되는 원소 $a_i$를 배열하는 방법이 $|A|!$가지.

- $S_{|A|+1} \dots S_n$까지도 비슷하게 $(n-|A|)!$가지이기 때문이다.

또, 각각의 $A \in F$가 만들어내는 chain들은 모두 다르다! 만약 서로 다른 $A, B \in F$에서 완전히 동일한 chain이 하나라도 생긴다면 $A \subset B$ 또는 $B \subset A$가 성립하여 Sperner family의 정의와 모순되기 때문이다.

따라서 $F$의 모든 원소를 이용하여 만들 수 있는 chain의 개수는 다음과 같다.

$$\sum_{A \in F} |A|! (n - |A|)! = \sum_{k = 0}^{n} f_{k} \cdot k! (n-k)!$$

하지만 이 chain들은 모두 $[n]$-chain에 포함된다. 따라서 위 식은 $[n]$-chain의 개수인 $n!$보다 작거

나 같고, 부등식을 세운 뒤 양변을 $n!$으로 나누면 우리가 원하는 식을 얻는다. $\blacksquare$

---

여기서부터는 $\left\lfloor \frac{n}{2} \right\rfloor$를 그냥 $n/2$로 표기하기로 한다. 타이핑 피곤해;

임의의 $n,k$에 대해 $\begin{pmatrix} n \\ k \end{pmatrix} \le \begin{pmatrix} n \\ n/2 \end{pmatrix}$가 성립한다.

뒤는 lemma에 의해 자연스럽게 성립한다.

$$1 \ge \sum_{k=0}^{n} \frac{f_k}{\begin{pmatrix} n \\ k \end{pmatrix}} \ge \frac{1}{\begin{pmatrix} n \\ n/2 \end{pmatrix}} \cdot \sum_{k=0}^{n} f_{k} = \frac{|F|}{\begin{pmatrix} n \\ n/2 \end{pmatrix}} \quad \blacksquare$$

---

등호는 $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가 된다.