建站实战干货

设集族 \(\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{ 个花瓣)} \]