第二节：更一般的容器定理

引言：通用的超图容器引理

在深入探讨具体应用之前，本节的核心工具——通用的超图容器引理。这个引理为各种组合对象（如图、整数集等）的计数和结构分析提供了统一的框架。

超图容器引理 (The Hypergraph Container Lemma)

对于任意 $k \in \mathbb{N}, c > 0$，存在 $\delta > 0$ 使得如下命题成立：
设 $\mathcal{H}$ 是一个 $k$-一致超图，且参数 $\tau \in (0,1)$ 满足：
 $ \Delta_\ell(\mathcal{H}) \le c \cdot \tau^{\ell-1} \frac{e(\mathcal{H})}{v(\mathcal{H})}, \quad \forall 1 \le \ell \le k$
（即超图的各阶度数是“良好分布”的）。
则存在一个 $V(\mathcal{H})$ 子集的集合 $\mathcal{C}$（称为容器集合），以及一个函数 $f: \mathcal{P}(V(\mathcal{H})) \to \mathcal{C}$，满足：

(a) 对于 $\mathcal{H}$ 中任意一个独立集 $I \in \mathcal{I}(\mathcal{H})$，都存在一个小的“指纹”子集 $S \subset I$，满足 $|S| \le \tau \cdot v(\mathcal{H})$，且 $I \subset f(S)$。

(b) 对于任意一个容器 $C \in \mathcal{C}$，它所含的超边数量很少，即 $e(\mathcal{H}[C]) \le (1-\delta)e(\mathcal{H})$。（注：讲义中给出的结论是 $|C| \le (1-\delta)v(\mathcal{H})$，两者在特定条件下等价，都表明容器不是“满”的）。

核心思想：任何一个没有特定结构的组合对象（即超图中的一个独立集），都可以被一个“几乎”没有该结构（即包含的超边很少）的、更大的“容器”所包含。并且，这样的容器数量相对较少，可以被有效控制。

---

一、$k$项等差数列问题

容器方法的第一个经典应用是解决数论中的组合问题，例如，一个整数子集中不含特定模式（如等差数列）的数量。

定理21

对于任意 $\beta > 0, k \in \mathbb{N}$，存在常数 $C$ 使得以下命题成立：
对于每个足够大的 $n \in \mathbb{N}$，如果 $m \ge C n^{1 - 1/(k-1)}$，那么在集合 $\{1, \dots, n\}$ 中，不包含 $k$ 项等差数列的 $m$ 元子集，其数量至多为 ${\beta n \choose m}$。
直观理解：一个足够大的整数子集，如果它不含 $k$-AP，那它是一种非常“罕见”的结构。

推论22

对于任意 $\epsilon > 0$，存在 $C > 0$ 使得如果 $p \ge Cn^{-1/(k-1)}$，那么以极高概率，随机子集 $[n]_p$ 中任意一个大小超过 $\epsilon pn$ 的子集 $A$，都必然包含一个 $k$ 项等差数列。

这两个结论的证明，依赖于一个关于等差数列的超饱和定理。

定理23 (Szemerédi 定理的超饱和版本)

对于任意 $\epsilon > 0, k \in [n]$，存在 $\delta > 0$ 使得以下命题成立：
任何一个大小超过 $\epsilon n$ 的子集 $A \subset [n]$，都必然包含大量（至少 $\delta n^2$ 个）的 $k$ 项等差数列。

证明思路:

1. 编码: 将 $k$-AP 编码成一个 $k$-一致超图 $\mathcal{H}$，其顶点集是 $[n]$，超边是所有 $k$-AP。
2. 迭代应用容器引理:
   • 从一个不含 $k$-AP 的集合 $B$ 开始，它对应 $\mathcal{H}$ 的一个独立集。
   • 反复应用超图容器引理。在每一步，如果当前容器 $C_t$ 仍然很大（$|C_t| > \epsilon n$），那么根据 Theorem 23，它必然包含大量的 $k$-AP，因此其诱导超图 $\mathcal{H}[C_t]$ 是稠密的，满足再次应用容器引理的条件。
   • 由于每次应用容器引理都会使容器大小按比例缩小，经过常数次迭代后，必然会得到一个大小不超过 $\epsilon n$ 的最终容器。
3. 计数: 我们证明了每个不含 $k$-AP 的集合 $B$ 都可以被一个大小不超过 $\epsilon n$ 的容器所包含。因此，不含 $k$-AP 的 $m$ 元子集的总数，可以通过对所有可能的小指纹 $S$ 和小容器 $C$ 进行求和来估计。通过标准的组合不等式放缩，可以证明这个总数远小于总的 $m$ 元子集数量，得到 Theorem 21 的结论。推论22 则是通过马尔可夫不等式直接得出。

---

二、不含特定$H$子图的图 (Containers for $H$-free graphs)

这部分内容将容器方法应用到经典的图论极值问题中，旨在刻画那些不含特定子图 $H$ 的图的典型结构和数量。

首先引入几个要用到的概念：

• 色数 $\chi(H)$：对图 $H$ 的所有顶点进行染色，使得任意两个相邻顶点颜色不同所需的最少颜色数。
• $k$-部图 ($k$-partite graph)：一个图的顶点集可以被分割为 $k$ 个独立的子集 $V_1, \dots, V_k$（称为“部”），使得所有边都只连接不同子集中的顶点（即任何一个 $V_i$ 内部都没有边）。
• $m_2(H)$：一个与图 $H$ 密度相关的参数，定义为 $m_2(H) = \max \left\{ \frac{e(F)-1}{v(F)-2} : F \subset H, v(F) \ge 3 \right\}$。它决定了在随机图中找到 $H$ 的概率阈值。
• $\epsilon$-接近 $k$-部图：一个图的顶点集可以被划分成 $k$ 个部分，使得那些“错误”的边（即连接同一个部分内部两点的边）的总数非常少。

接下来是本节的三个核心定理：

定理24 (极值数定理的随机版本)

对于任意满足 $\Delta(H) \ge 2$ 的图 $H$ 和任意 $\epsilon > 0$，存在常数 $C>0$。如果 $p \ge Cn^{-1/m_2(H)}$，则有很高的概率：
 $ ex(G(n,p), H) \le \left(1 - \frac{1}{\chi(H)-1} + \epsilon\right) p \binom{n}{2} $
直观理解：随机图 $G(n,p)$ 中不含 $H$ 的最大子图，其边数不会比图兰定理预测的“最优”结构（即 $(\chi(H)-1)$-部图）的边数多太多。

定理25 (稳定性定理)

对于任意满足 $\Delta(H) \ge 2$ 的图 $H$ 和任意 $\epsilon > 0$，存在常数 $C>0, \delta>0$。如果 $p \ge Cn^{-1/m_2(H)}$，则下述命题以极高概率成立：
任何一个不含 $H$ 的子图 $G \subset G(n,p)$，只要它的边数足够多（即 $e(G) \ge \left(1 - \frac{1}{\chi(H)-1} - \delta\right) p \binom{n}{2}$），那么它就必然“长得像”一个 $(\chi(H)-1)$-部图（即以 $\epsilon pn^2$ 的代价可变为 $(\chi(H)-1)$-部图）。

定理26 (计数稳定性定理)

对于任意满足 $\chi(H) \ge 3$ 的图 $H$ 和任意 $\epsilon > 0$，存在常数 $C>0$。如果 $m \ge Cn^{2-1/m_2(H)}$，那么几乎所有（在所有 $m$ 条边的图中占 $1-o(1)$ 的比例）不含 $H$ 的 $n$ 顶点、$m$ 边图都“长得像”一个 $(\chi(H)-1)$-部图（即以 $\epsilon m$ 的代价可变为 $(\chi(H)-1)$-部图）。

这三个定理的证明都依赖于一个核心的容器定理 (Theorem 28)，而该定理的证明又需要一个超饱和定理 (Theorem 27)。

定理27 (Erdős-Simonovits 稳定性定理的超饱和版本)

对于任意图 $H$ 和任意 $\epsilon > 0$，存在 $\delta > 0$ 使得对所有 $n \in \mathbb{N}$，下述命题成立：
如果一个 $n$ 顶点的图 $G$ 的边数足够多，即 $e(G) > \left(1 - \frac{1}{\chi(H)-1} - \delta\right) \binom{n}{2}$，那么 $G$ 只有两种可能：
(1) $G$ 是 $\epsilon n^2$-接近 $(\chi(H)-1)$-部图的；
(2) $G$ 包含大量（至少 $\epsilon n^{v(H)}$ 个）的 $H$ 副本。
核心思想：一个稠密的、但又不像 $(\chi(H)-1)$-部图的图，必然会“超饱和”地包含 $H$。

有了这个工具，我们就可以证明本节的基石：

定理28 (无-$H$图的容器定理)

对于任意图 $H$ 和任意 $\epsilon>0$，存在 $\delta>0, C>0$ 使得以下命题成立。存在一个图的集合 $\mathcal{G}$ 和一个函数 $f: \mathcal{P}(E(K_n)) \to \mathcal{G}$ 使得：
(a) 对任意 $G \in \mathcal{G}$，它只有两种可能：
(1) $e(G) \le \left(1 - \frac{1}{\chi(H)-1} - \delta\right) \binom{n}{2}$ (边数较少)；
(2) $G$ 是 $\epsilon n^2$-接近 $(\chi(H)-1)$-部图的 (结构稳定)。
(b) 对于每个不含 $H$ 的 $n$ 顶点图 $I$，都存在一个小的“指纹”子图 $S \subset I$，满足 $e(S) \le Cn^{2-1/m_2(H)}$ 且 $I \subset f(S)$。

证明思路:
证明采用了迭代方法。

1. 编码: 将 $H$ 的副本编码成一个 $e(H)$-一致超图 $\mathcal{H}$，其顶点集是 $E(K_n)$。不含 $H$ 的图就是 $\mathcal{H}$ 的独立集。
2. 启动: 对任意一个不含 $H$ 的图 $I$，首次应用超图容器引理（取 $\tau=n^{-1/m_2(H)}$），得到一个指纹 $S_1$ 和一个比 $K_n$ 小的容器 $C_1$。
3. 迭代: 对容器 $C_t$ 进行检查。
   • 如果 $C_t$ 已经满足(a)中的两种情况之一，则迭代终止，将其放入最终的集合 $\mathcal{G}$。
   • 否则，根据 Theorem 27，$C_t$ 必然包含大量的 $H$ 副本。这意味着其对应的诱导超图 $\mathcal{H}[C_t]$ 是稠密的，满足再次应用容器引理的条件。
4. 收敛: 每次迭代，容器的大小 $e(C_t)$ 都会按比例缩小。因此，经过常数次迭代后，容器必然会缩小到满足条件(a)的程度。

有了 Theorem 28 这个强大的结构性结论，定理24、25、26 就可以通过标准的概率论证（如Chernoff界）和组合计数推导出来。

---

三、随机图的拉姆齐理论 (Ramsey properties of random graphs)

这部分展示了容器方法如何解决随机环境下的拉姆齐问题，即在一个随机图 $G(n,p)$ 中寻找单色子结构。

定义30 ([r]-染色图)

一个 [r]-染色图 是一个图 $G$ 配上一个染色函数 $c: E(G) \to \mathcal{P}([r]) \setminus \{\emptyset\}$，它为每条边赋予一个或多个来自集合 $\{1, \dots, r\}$ 的颜色。我们称这样的图是无单色$H$的，如果不存在一个 $H$ 的副本，其所有边的颜色集合的交集非空。

定理29 (Rödl–Ruciński, 1995)

对于任意图 $H$ 和任意 $r \in \mathbb{N}$，如果 $p \gg n^{-1/m_2(H)}$，那么以高概率，对 $G(n,p)$ 的边进行任意的 $r$-染色，都必然会产生一个单色的 $H$ 副本。
核心思想：一旦随机图的密度 $p$ 越过某个由 $m_2(H)$ 决定的阈值，它就不仅包含 $H$，而且是“Ramsey饱和”的，无法通过染色来避免单色的 $H$。

证明同样需要一个超饱和定理和一个容器定理。

定理31 (拉姆齐定理的超饱和版本)

对于任意图 $H$ 和 $r \in \mathbb{N}$，存在 $\delta > 0$ 使得对于所有足够大的 $n$：如果图 $G$ 的边数足够多（即 $e(G) > (1/2 - \delta)n^2$），那么对 $G$ 的任意 $[r]$-染色方案都包含大量（至少 $\delta n^{v(H)}$ 个）的单色 $H$。

定理32 (无单色$H$染色图的容器定理)

对于任意图 $H, r \in \mathbb{N}, \epsilon>0$，存在 $\delta>0, C>0$ 使得对于任意 $n \in \mathbb{N}$，存在一个 $[r]$-染色图的集合 $\mathcal{G}$ 和一个函数 $f: \mathcal{P}(E(K_n))^r \to \mathcal{G}$ 使得：
(a) 对任意 $G \in \mathcal{G}$，其边数至多为 $(1-\delta)\binom{n}{2}$。
(b) 对于每个无单色$H$的 $n$ 顶点 $[r]$-染色图 $I$，都存在一个小的“指纹”子染色 $S \subset I$，满足 $e(S) \le Cn^{2-1/m_2(H)}$ 且 $I \subset f(S)$。

定理29的证明思路:

1. 构造超图: 构造一个超图 $\mathcal{H}$，其顶点是所有可能的“颜色-边”对（共 $r\binom{n}{2}$ 个顶点），超边对应 $K_n$ 中所有可能的单色 $H$ 副本。一个无单色$H$的染色图就对应 $\mathcal{H}$ 中的一个独立集。
2. 应用容器定理: 利用 Theorem 31 作为超饱和工具，通过与前面类似的迭代过程，可以证明 Theorem 32。
3. 概率论证: 假设 $G(n,p)$ 中存在一个无单色$H$的 $r$-染色 $I$。根据 Theorem 32，这个 $I$ 必须被某个容器 $G \in \mathcal{G}$ 包含。这意味着 $I$ 的指纹 $S$ 必须是 $G(n,p)$ 的子图，并且 $G(n,p)$ 的所有边都必须在 $G$ 中。
4. 联合界: 对所有可能的指纹 $S$ 使用联合界（Union Bound）。
   $ P(\text{坏事件}) \le \sum_{S} P(S \subset G(n,p) \text{ and } G(n,p) \subset G(S)) $
   由于 $G(S)$ 的边数比 $\binom{n}{2}$ 少一个正比例，而 $G(n,p)$ 的期望边数很大，事件 $G(n,p) \subset G(S)$ 发生的概率极小（指数级小）。将这个极小的概率与所有可能指纹的数量相乘，只要 $p$ 足够大，最终结果将趋向于0。