设集族 \(\mathcal{F} \subseteq \mathcal{P}([n])\)。
1. Sperner 定理
- 条件：\(\forall A, B \in \mathcal{F}, A \not\subseteq B\)
- 结论：\(|\mathcal{F}| \le \binom{n}{\lfloor n/2 \rfloor}\)
2. LYM 不等式
-
条件：\(\forall A, B \in \mathcal{F}, A \not\subseteq B\)
-
公式：\(\sum_{A \in \mathcal{F}} \frac{1}{\binom{n}{|A|}} \le 1\)
\[\mathbb{P}(\text{全排列链交 } A) = \frac{1}{\binom{n}{|A|}} \xrightarrow{\text{事件互斥}} \sum_{A \in \mathcal{F}} \mathbb{P} \le 1 \implies |\mathcal{F}| \le \binom{n}{\lfloor n/2 \rfloor} \text{ (Sperner)} \]
3. Kruskal-Katona 定理
-
定义：对 \(k\)-集族 \(\mathcal{F} \subseteq \binom{[n]}{k}\)，阴影 \(\partial \mathcal{F} = \{ B \in \binom{[n]}{k-1} \mid \exists A \in \mathcal{F}, B \subset A \}\)
-
分解：唯一表示 \(|\mathcal{F}| = \binom{a_k}{k} + \binom{a_{k-1}}{k-1} + \dots + \binom{a_t}{t}\) (\(a_k > a_{k-1} > \dots > a_t \ge t \ge 1\))
\[|\partial \mathcal{F}| \ge \binom{a_k}{k-1} + \binom{a_{k-1}}{k-2} + \dots + \binom{a_t}{t-1} \]\[\left(\mathcal{F} \text{ 取字典序前 } |\mathcal{F}| \text{ 个集合时等号成立 } \implies |\partial \mathcal{F}| \text{ 最小}\right) \]
4. Sunflower 定理
-
定义：\(\mathcal{S}\) 为向日葵 \(\iff \exists S, \forall A, B \in \mathcal{S} (A \neq B), A \cap B = S\)
\[\mathcal{F} \subseteq \binom{[n]}{k}, \quad |\mathcal{F}| > (r-1)^k k! \implies \exists \mathcal{S} \subseteq \mathcal{F}, \ |\mathcal{S}| = r \text{ (含 } r \text{ 个花瓣)} \]