第一节：当你的一阶矩方法失效时，该怎么办？

1. 核心问题与经典方法的局限性

核心思想: 在许多“自然”的超图中，其（大的）独立集并非随机分布，而是呈现出“扎堆”或“聚集”的结构化特征。
(注意本节中一切讨论未涉及超图，还是基于图（随机图）在进行讨论)

定义1 The extremal number of a graph $H$:

在一个有n个顶点的图中，不包含$H$作为子图的前提下，所能拥有的最大边数。记作$ex(n,H)$。

简单来说，$ex(n,H)$回答了：为了确保子图中一定出现一个$H$，至少需要多少条边？
答案是$ex(n,H)+1$。

本节我们将要证明以下理论：
定理2 [Frankl and Rodl]:

如果$p \gg 1/\sqrt{n}$，那么$ex(G(n,p),K_3)=\Big(\frac{1}{4}+o(1)\Big)pn^2$。当$n$趋向无穷大时，上述等式以极高的概率成立。

• 要求图$G$不能太稀疏。
• 在确定的$n$顶点图中，不含三角形的图最多有约$n^2/4$条边（图兰定理）。

当我们想要证明以上定理时，第一个想法是利用概率论中的一阶矩方法：

• 思路：定义一个随机变量$X$，表示$G(n,p)$ 中大小为$m$的无三角形子图的数量。然后计算它的期望值$E[X]$。如果$E[X]=o(1)$，那么根据马尔可夫不等式，大小为$m$的无三角形子图存在的概率就趋近于$0$，即有很高的概率$ex(G(n,p),K_3)\leq m$。
• 问题：讲义中指出，当你去计算这个期望值时，会发现它爆炸了，即$E[X]$非常大，远不趋近于 $0$。所以该方法失效。

经典一阶矩方法失效原因大致可以理解为无三角形图本身是“扎堆”或“聚集”的。许多无三角形图都非常相似（比如，都接近于同一个二分图），这导致它们在$G(n,p)$中出现的事件之间存在强烈的正相关性。这种正相关性使得简单的期望计算失效。

2. 容器方法的核心思想与应用

既然经典方式走不通，就要采用一种新的策略来处理这种聚类现象，这个策略就是容器方法。
核心思想变化是这次我们不再一个个地数无三角形图，而是先把它们分装到一些容器里，然后再去处理这些容器。这些容器由定理3来保证存在。

定理3 无三角形图容器定理 (The container theorem for triangle-free graphs):

对于$n$个顶点的图，存在一个图的集合$\mathcal{G}$（我们称之为“容器集合”），它满足以下三个性质：
(a) 容器数量很少: $|\mathcal{G}|$的规模相对很小，满足 $|\mathcal{G}|\leq n^{O(n^{3/2})}$。
(b) 容器自身很“干净”: $\mathcal{G}$中的每个图$G$只包含$o(n^3)$个三角形。
(c) 所有目标都被装下了: 每个不含三角形的图，都必然是$\mathcal{G}$中某个容器图$G$的子图。

直观理解：平面上有无数个苹果（代表所有无三角形图）。我们想证明这些苹果的总重量不大。直接一个个称重很麻烦。容器方法告诉我们，我们可以找到少数几个大篮子（性质a），这些篮子本身都很轻（性质b），并且所有苹果都在这些篮子里面（性质c）。

接下来使用容器的思想来证明定理2：
首先需要引入一个关键工具：
定理4 三角形超饱和定理 (Supersaturation for triangles):

对于任何 $\epsilon>0$，存在 $\delta > 0$。如果一个$n$顶点图的边数$e(G) \ge (1/4 + \epsilon)n^2$，那么$G$包含的至少$\delta n^3$个三角形。

这个定理的逆否命题很有用：如果一个有$n$个顶点的图的三角形数为$o(n^3)$，则该图至多只有$(1/4+o(1))n^2$条边。

现在可以使用容器方法证明定理2了。（注：此处原文为定理3，根据上下文应为证明定理2）
回顾定理2的内容，我们需要证明在$G(n,p)$随机图中，不可能存在一个边数超过$(1/4+\epsilon)pn^2$的无三角形子图$H$。考虑使用反证法，先假设存在一个这样的坏图$H$，然后推导出一个概率极小、几乎不可能发生的结论，从而证明假设错误。

1. 假设：存在坏图$H$同时满足以下两个条件：
   • $H$是无三角形的；
   • $e(H) > (1/4+\epsilon)pn^2$。
2. 装入容器：由容器定理（定理3），必然存在一个容器图$G$，满足$H \subset G$。
3. 分析容器 $G$ 的属性：
   • 由容器定理性质(b)：容器$G$所含三角形数很少，只有$o(n^3)$个。
   • 由超饱和定理（定理4）的逆否命题知：$e(G) \le (1/4+o(1))n^2$条边。

4. 概率论证：现在我们有一个确定的容器图$G$，和一个随机的图$G(n,p)$，假设的坏图$H$是$G$和$G(n,p)$的公共子图。将$e(G)$看作$e(G)$次独立试验：对于容器$G$的每个边位置，这条边是否出现在$G(n,p)$中是一个独立的概率为$p$的事件，所以“$G$从$G(n,p)$中捕获的边数”这个随机变量，服从二项分布$B(e(G),p)$。已知$e(G) \approx n^2/4$，所以这个二项分布的数学期望大约为$p(n^2/4)$。但我们假设捕获的边数$m > (1/4+\epsilon)pn^2$，远大于期望值。
   Chernoff’s Inequality：

   设 $X_1, X_2, \dots, X_N$是一系列独立的伯努利随机变量，令 $X = \sum X_i$，其期望值为$ \mu = E[X]$。对于任何$ \delta > 0$，有：
   $P(X \ge (1+\delta)\mu) \le e^{-\delta^2\mu/3}, \quad \text{for } 0 < \delta \le 1$

   使用Chernoff不等式得到发生这种大偏差事件的概率是$e^{-\Omega(pn^2)}$。所以对于任何一个特定的容器$G$，它能“捕获”到我们假设的那个超级大的$H$的概率，小到可以忽略不计。

5. 联合界：上面的讨论证明了单个容器捕获到$H$的概率是很小的，但当容器不止一个的时候，是否所有容器捕捉到$H$的概率之和仍然很小？
   • 定义坏容器（即捕获了至少$m$条边的容器）的数量为$Y_m$。我们想计算$P(Y_m \ge 1)$，即“至少存在一个坏容器”的概率。
   • 根据联合界，这个概率小于等于所有容器成为坏容器的概率之和，也就是：
     $P(Y_m \ge 1) \le E[Y_m] = \sum_{G\in \mathcal{G}} P(e(G\cap G(n,p))\ge m) \le |\mathcal{G}| \times e^{-\Omega(pn^2)} = n^{O(n^{3/2})}e^{-\Omega(pn^2)}$。
     比较这两项的大小只需要取对数，而后得到当$p \gg \log n/\sqrt{n}$时，该概率趋向于0，可以证明得到定理2的结论（但这里对于$p$取值的要求稍微强于原定理）。

结论：以极高的概率，$G(n,p)$中不可能存在边数超过$(1/4+o(1))pn^2$的无三角形子图。

3. 超图容器引理及其证明

为了证明定理3，需要将问题上升到更普适的3-一致超图（3-uniform hypergraphs）中。

定义5 编码三角形的超图 (the hypergraph encoding triangles in $K_n$):

构造一个$3$-一致超图$\mathcal{H}$，满足：

• 顶点集 $V(\mathcal{H})=E(K_n)$ 是完全图$K_n$的所有边。
• 超边集 $E(\mathcal{H})$ 是$K_n$中所有构成三角形的三条边的集合。
  $E(\mathcal{H})=\{\{f_1,f_2,f_3\}\subset E(K_n):\{f_1,f_2,f_3\}=E(K_3)\}$。

在这个构造下，$\mathcal{H}$的一个独立集（不包含任何超边的顶点集）就等价于$K_n$中一个不含三角形的边集，也就是一个无三角形图。

对于一个超图$\mathcal{H}$，定义$\Delta_\ell(\mathcal{H})=\max\{d_{\mathcal{H}}(A):A\subset V(\mathcal{H}),|A|=\ell\}$。其中$d_{\mathcal{H}}(A)=|\{B\in E(\mathcal{H}):A\subset B\}|$，用$\mathcal{I}(\mathcal{H})$表示$\mathcal{H}$中所有独立集的集合。

$3$-一致超图的容器引理:

对于一个$3$-一致超图$\mathcal{H}$，如果其平均度$d$足够大使得$\tau:=1/\sqrt{d}\leq\delta$，且$\Delta_1(\mathcal{H})\leq c\cdot d,\ \Delta_2(\mathcal{H})\leq c\cdot\sqrt{d}$，那么存在一个由$V(\mathcal{H})$的子集构成的容器集合$\mathcal{C}$，具有以下性质：
(a) 覆盖性: 对于任意独立集$I\in \mathcal{I}(\mathcal{H})$，均存在某个容器$C\in \mathcal{C}$使得$I\subset C$。
(b) 容器更小: $|C| \le (1-\delta)v(\mathcal{H}),\forall C\in \mathcal{C}$（即比原顶点集小一个常数比例）。
(c) 容器个数上界：$|\mathcal{C}|\le {v(\mathcal{H})\choose \tau\cdot v(\mathcal{H})}$。

4. 定理3的证明

现在回到由$K_n$编码三角形的超图$\mathcal{H}$。
注意图$\mathcal{H}$的性质：$v(\mathcal{H})={n\choose 2},\ d_{\mathcal{H}}(v)=n-2,\forall\ v\in V(\mathcal{H})$。
而后考虑$\Delta_2(\mathcal{H})$的计算，任取$\mathcal{H}$中的两个顶点构成的点集$\mathcal{A}$，$\mathcal{H}$中的两点对应的$K_n$中的两条边有以下两种可能情况：

• 两边在$K_n$没有公共点，则两边无法与第三条边构成三角形，因而在$\mathcal{H}$中$d_{\mathcal{H}}(\mathcal{A})=0$。
• 两边在$K_n$中有公共点，则这两条边会与唯一一条边一起构成一个$K_n$中的三角形，从而在$\mathcal{H}$中$d_{\mathcal{H}}(\mathcal{A})=1$。
  于是得到：$\Delta_2(\mathcal{H})=1$。

令$c=1$，对$\mathcal{H}$应用3-一致超图容器引理，得到$E(K_n)$的容器集合$\mathcal{C}_0$。
因为$\tau=\Theta(1/\sqrt{n})$，由引理(c)及不等式${n\choose k}\leq\Big(\frac{en}{k}\Big)^k$得到$|\mathcal{C}_0|\leq n^{O(n^{3/2})}$。
于是定理3中数量少的要求已经被满足。接下来利用迭代思想构造一个“结构好”的容器集合$\mathcal{G}$。

(1) 初始化: 将上面得到的$\mathcal{C}$记为$\mathcal{C}_0$。$\mathcal{C}_0$中可能有很多坏容器（包含的三角形数太多了）。

(2) 迭代提纯: 在第$i$步，对容器集合$\mathcal{C}_{i-1}$中的每一个容器$C$进行检查：

• 好容器: 若$t(C) < \epsilon n^3$，则$C$达标，放入最终集合$\mathcal{G}$。
• 坏容器: 若$t(C) \ge \epsilon n^3$，则$C$需要被分解。对$C$构造诱导子超图$\mathcal{H}[C]$。
  检查$\mathcal{H}[C]$的平均度数：$v(\mathcal{H}[C]) = |C| = O(n^2), e(\mathcal{H}[C]) = t(C) \ge \epsilon n^3$，所以$d(\mathcal{H}[C]) = 3 e(\mathcal{H}[C]) / v(\mathcal{H}[C]) \ge 3\epsilon n$。
  这个平均度足够大，我们可以令$c=1/\epsilon$，在$\mathcal{H}[C]$上再次应用超图容器引理，得到一个新的、更小的容器集合$\mathcal{C}’(C)$。

(3) 更新: 用这个新的、更小的容器集合$\mathcal{C}’(C)$来替换原来的那个坏容器$C$。

(4) 迭代终止: 每次分解，新容器的大小（边数）都会以$(1-\delta)$的比例缩小。经过有限步（大约$O(\log n)$步）后，所有容器都会因为不断变小而最终变成好容器。

(5) 最终结论:
当迭代终止时，我们得到的最终集合$\mathcal{G}$满足定理3的所有条件：

• 结构好: $\mathcal{G}$中的每个容器的三角形数量都小于$\epsilon n^3$（即$o(n^3)$）。
• 覆盖性: 任何一个无三角形图$I$在每次迭代中都会被新的子容器覆盖，所以最终一定被某个好容器覆盖。
• 数量少: 虽然每一步都会增加容器数量，但迭代步数有限。总容器数量仍然在$n^{O(n^{3/2})}$的量级，是极小的。

这样，通过迭代提纯的过程，我们就成功地构造出了满足定理3要求的容器集合。

5. 图的容器引理及其证明

为了证明超图容器引理，我们先考虑一个简化版——图的容器引理。

图的容器引理 (The Graph Container Lemma):

对任意$c>0$，存在$\delta>0$使得以下条件成立：对于一个平均度为$d$且$\Delta(G)\leq c\cdot d$的图$G$，取$\tau:=2\delta/d$。可以找到一个$V(G)$的子集集合$\mathcal{C}$，满足：

1. 覆盖性：对于任意独立集$I\in \mathcal{I}(G)$，存在容器$C\in \mathcal{C}$使得$I\subset C$。
2. 容器更小：$|C|\leq(1-\delta)v(G),\forall C\in\mathcal{C}$。
3. 容器数量有限：$|\mathcal{C}|\leq{v(G)\choose \lceil\tau\cdot v(G)\rceil}$。

定义6 (最大度顺序):

图$G$顶点的最大度排序是指将$V(G)$中的点排列为$(v_1,v_2,\dots,v_n)$，使得$\forall i\in [n]$，$v_i$是$G[\{v_i,\dots,v_n\}]$中度数最高的点。

图的容器算法:
给定图$G$以及一个独立集$I\in\mathcal{I}(G)$，维护一个对$V(G)$的划分$V(G)=A\cup S\cup X$。

• $A$: 活跃点集
• $S$：当前的指纹集
• $X$：被排除的点集

初始化$A=V(G),\ S=X=\emptyset$。当$|X|\leq\delta v(G)$时，重复：

1. 按最大度顺序，找到第一个属于$I$的顶点$v$。
2. 将$v$移入$S$。
3. 将$v$的邻居$N(v)$和所有排在$v$之前的顶点移入$X$。
4. 从$A$中移除新加入$S$和$X$的顶点。

引理证明思路:

• 覆盖性: 对于给定的独立集$I$，算法生成的排除集$X$中的点都确定不在$I$中，因此$I$必然被包含在$C(S) = V(G) \setminus X$中。
• 容器更小: 算法循环结束条件是$|X| > \delta v(G)$，这直接保证了$|C(S)| \le (1-\delta)v(G)$。
• 数量可控: 关键在于证明指纹集$S$足够小，即$|S(I)| \le \lceil\tau \cdot v(G)\rceil$。这通过证明“每向$S$中加入一个点，至少有$d/2$个点被加入到$X$”来实现。
  • 这一步利用了$\Delta(G) \le c \cdot d$的条件和反证法。假设某一步加入$S$的顶点$u$不能为$X$贡献足够多的新成员，那么可以推导出在当前的活跃子图$G[A]$中，平均度数仍然很高。因此，作为度数最高的顶点，$u$的度数必然很大，这与“不能为$X$贡献足够多成员”的假设矛盾。

6. 3-一致超图容器引理证明

该证明将图容器算法的思想推广到超图。算法维护一个指纹$S$、一个可用的超图$A$和一个禁用对图$G$。

核心循环:

1. 在可用超图$A$中按最大度顺序找到第一个属于独立集$I$的顶点$u$。
2. 将$u$加入指纹$S$。
3. 对于每条包含$u$的超边$\{u, v, w\}$，在$G$中添加一条边$\{v,w\}$，表示$v,w$不能共存。
4. 将$u$和所有排在$u$前面的顶点从$A$中移除。
5. 将$G$中度数过高的顶点从$A$中移除（为Plan A做准备）。
6. 将包含$G$中边的超边从$A$中移除（强化约束）。

证明思路 (Plan A / Plan B策略):
对于任意独立集$I$，算法运行后，必然落入以下两种情况之一：

• Plan A: 禁用对图$G$非常稠密
  $e(G(S_2)) \ge \frac{\sqrt{d}\cdot v(H)}{8c}$ 且 $\Delta(G(S_2)) \le 2c\sqrt{d}$。
  此时，我们得到了一个稠密且最大度有界的普通图$G(S_2)$。由于$I$在其中也是独立集，我们可以对$G(S_2)$应用图的容器算法，找到一个小的图指纹$S_1$，从而生成一个满足条件的小容器$C$。
• Plan B: 禁用对图$G$不够稠密
  $e(G(S_2)) < \frac{\sqrt{d}\cdot v(H)}{8c}$。
  此时，算法在生成“禁用对”方面不成功。通过反证法可以证明，这种情况的发生，必然是因为在算法的某个步骤中，有大量的顶点（至少$v(H)/16c$个）因为度数排序（第4步）或度数过高（第5步）而被移出$A$。这些被移除的顶点都不在$I$中（除了$S_2$中的少量成员）。因此，我们直接定义容器为 $C = V(\mathcal{H}) \setminus (\text{这些被移除的顶点})$，这个容器也满足大小要求。

两种情况都导向了小容器的生成，从而完成了证明。

7. 加强版3-一致超图容器引理与应用

加强版3-一致超图容器引理:

对于任意$c>0$，存在$\delta>0$。如果3-一致超图$\mathcal{H}$的平均度数为$d$，令$\tau:=1/\sqrt{d}$并假设$\tau\leq\delta$，且$\Delta_1(\mathcal{H})\leq c\cdot d,\ \Delta_2(\mathcal{H})\leq c\cdot \sqrt{d}$，则存在一个$V(\mathcal{H})$的容器集合$\mathcal{C}$以及一个函数$f:\mathcal{P}(V(\mathcal{H}))\rightarrow \mathcal{C}$使得：
(a) 对于任意$I\in\mathcal{I}(\mathcal{H})$，存在$S \subset I$满足$|S|\leq\tau\cdot v(\mathcal{H})$，且$I\subset f(S)$。
(b) $|C|\leq(1-\delta)v(\mathcal{H}),\forall C\in \mathcal{C}$。

与原版的区别: 主要在于结论(a)，它更明确地指出了“指纹”$S$是独立集$I$的子集，并且容器$f(S)$完全由这个指纹决定。

应用: 加强版引理的一个很有效的应用就是将定理2中$p$的约束条件从$p \gg \log n/\sqrt{n}$优化到了$p \gg 1/\sqrt{n}$。
这是因为在最终的概率计算中，我们不再需要对所有可能的容器求和，而是对所有可能的小指纹$S$求和。由于指纹$S$是$G(n,p)$的子图，它的出现本身就带有一个$p^{|S|}$的概率。这使得最终的联合界计算更加精细，从而放宽了对$p$的要求。