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가 된다.