[随笔260807] Sunflower, Sperner, LYM, Kruskal-Katona-三亩地-编程学习日记

设集族 \(\mathcal{F} \subseteq \mathcal{P}([n])\)。

1. Sperner 定理

条件：\(\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)} \]

定义：对 \(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) \]

定义：\(\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{ 个花瓣)} \]