容器定理应用进阶

$K_{s,t}$-free 和 $C_{2k}$-free 图的计数

这一部分的目标是计算不含特定二部图（如 $K_{s,t}$ 或偶环 $C_{2k}$）的图的数量。这类问题的解决依赖于一个强大的组合：平衡超饱和定理 + 超图容器引理。

1. 主要结论

Theorem 46. (Balogh, Samotij, 2011)

对于任意固定的 $s, t$，不含 $K_{s,t}$ 的 $n$ 顶点图的数量至多为 $2^{O(n^{2 - 1/s})}$。

Theorem 47. (Morris, Saxton, 2016)

对于任意固定的 $k$，不含 $C_{2k}$ 的 $n$ 顶点图的数量至多为 $2^{O(n^{1 + 1/k})}$。

为了避免过于复杂的技术细节，本节以最简单但具有代表性的情况——$C_4$-free 图——为例来展示其证明方法。

2. $C_4$ 的平衡超饱和定理 (Theorem 48)

对于容器方法而言，仅仅知道一个图里有很多 $C_4$ 是不够的。我们还需要保证这些 $C_4$ 是“良好分布”的，即没有某条边或某对边参与了过多的 $C_4$。这正是“平衡超饱和”的含义。

Theorem 48.

存在常数 $\delta > 0$ 和 $k_0 \in \mathbb{N}$。对于任意 $k > k_0$ 和 $n \in \mathbb{N}$，给定一个有 $n$ 个顶点和 $kn^{3/2}$ 条边的图 $G$，存在一个 $G$ 中 $C_4$ 的集合 $\mathcal{H}$，满足：

(a) $|\mathcal{H}| > \delta^3 k^4 n^2$ (集合足够大)

(b) 每条边最多被用于 $\delta^2 k^3 \sqrt{n}$ 个 $\mathcal{H}$ 中的成员。(边的度数有上界)

(c) 每对边最多被用于 $\delta k \sqrt{n}$ 个 $\mathcal{H}$ 中的成员。(边的共度有上界)

证明思路:

这个证明采用迭代构造的方法。我们从一个空的集合 $\mathcal{H}$ 开始，在每一步都向其中添加一个“好”的 $C_4$，直到满足所有条件。

1. 识别瓶颈: 直接证明(c)很困难。其难点在于控制相邻边对（即长度为2的路径）参与形成的 $C_4$ 数量。

2. 强化条件 (引入(c’)): 为了解决这个瓶颈，作者引入了一个更强、更具体的技术条件(c’)。我们将 $C_4$（即 $K_{2,2}$）的四个顶点分成不相邻的两对，一对染成“红色”，另一对染成“蓝色”。

   • (c’) 每条以 $v$ 为中心的长度为2的路径，最多被用于:
     • $\delta k^2$ 个 $v$ 是红色的 $\mathcal{H}$ 成员中。
     • $\delta k \sqrt{n}$ 个 $v$ 是蓝色的 $\mathcal{H}$ 成员中。
       这个条件(c’)比(c)更强，只要满足了(c’)，原条件(c)也自然满足。

3. 核心论证 (Proof of Claim): 假设我们当前的集合 $\mathcal{H}$ 已经满足(b)和(c’)，但不满足(a)（即不够大）。我们要证明，此时一定能在图中找到一个“好”的 $C_4$ 添加到 $\mathcal{H}$ 中，使得新集合仍然满足(b)和(c’)。这个论证分两步计数：

   • 第一步：寻找大量“非饱和”的红心路径。
     我们先从 $G$ 中移除所有在 $\mathcal{H}$ 中已经“饱和”的边（即度数达到(b)中上界的边），得到新图 $G’$。由于 $\mathcal{H}$ 不够大，被移除的边数不多，$G’$ 仍然很稠密。
     在 $G’$ 中，我们寻找以某个顶点 $v$ 为中心（我们将 $v$ 染成红色）的长度为2的路径。一条路径如果已经参与了太多红心 $C_4$（达到(c’)中上界），就称之为“饱和路径”。
     通过简单的计数可以发现，饱和路径的总数并不多。因此，利用凸性 (convexity)（即詹森不等式），我们可以证明 $G’$ 中存在大量的非饱和红心路径：
     $ \frac{1}{2} \sum_{v \in V(G’)} d(v)(d(v) - 3\delta k \sqrt{n}) > \frac{1}{3n} \left(\sum_{v \in V(G’)} d(v)\right)^2 > \frac{k^2 n^2}{4} $
     这里 $3\delta k \sqrt{n}$ 是从饱和路径计数中得到的损失项。这保证了我们有至少 $\frac{k^4 n^2}{4}$ 这么多非饱和的红心路径。

   • 第二步：将这些路径配对成“好”的 $C_4$。
     现在，我们固定两个顶点 $u, w$（我们将它们染成蓝色），并考虑所有连接它们的非饱和红心路径。假设我们已经有了一条路径 $u-v-w$。我们要找另一条路径 $u-v’-w$ 与之配对形成一个 $C_4$。
     什么样的 $v’$ 是“坏”的？如果 $v’$ 导致新生成的 $C_4$ 违反了条件(c’)（即路径 $v-u-v’$ 或 $v-w-v’$ 是蓝心饱和的），那么它就是坏的。
     通过(b)中的上界，我们可以估算出“坏”的 $v’$ 的数量最多不超过 $3\delta k^2$ 个。
     我们有大约 $\frac{k^4}{4}$ 个路径连接任意一对 $\{u, w\}$。从中选择两个不同的路径来构成 $C_4$。同样，利用凸性，我们可以得到“好”的 $C_4$ 的数量下界：
     $ \frac{1}{2} \binom{n}{2} \binom{\text{平均公共邻居数}}{\text{2}} \approx \frac{1}{2} \binom{n}{2} \frac{k^4}{4} \left(\frac{k^4}{4} - 3\delta k^2\right) > 2\delta k^4 n^2 $
     这个数量远大于已经在 $\mathcal{H}$ 中的 $C_4$ 数量，所以一定存在新的、“好”的 $C_4$ 可以被添加。

这样，通过迭代添加，最终可以得到满足所有条件的集合 $\mathcal{H}$。

3. $C_4$-free图的容器定理 (Theorem 49)

这是利用Theorem 48作为工具，通过容器方法得到的最终结构性定理。

Theorem 49.

存在常数 $k_0 > 0, C > 0$。对于所有 $n \in \mathbb{N}$ 和满足 $k_0 \le k \le n^{1/6}/\log n$ 的 $k$，存在一个图的集合 $\mathcal{G}(n,k)$，它有如下性质：

• $|\mathcal{G}(n,k)| \le \exp\left( C \frac{\log k}{k} \cdot n^{3/2} \right)$ (集合很小)
• 对每个 $G \in \mathcal{G}(n,k)$，有 $e(G) \le k n^{3/2}$ (个体有界)
• 每个不含 $C_4$ 的图都是某个 $G \in \mathcal{G}(n,k)$ 的子图 (容器性)

证明思路 (Proof of Theorem 49):

这个证明是本文中迭代思想的集中体现。

1. 迭代框架:

   • 我们从 $\mathcal{C}_0 = \{K_n\}$ 开始。
   • 在第 $t$ 步，我们检查 $\mathcal{C}_t$ 中的每个图 $G$。如果 $e(G)$ 仍然很大（大于某个阈值），我们就对它进行“打碎”操作。
   • 这个阈值是动态变化的，由 $k(i) = \max\{(1-\varepsilon)^i\sqrt{n}, k_0\}$ 决定。

2. “打碎”一个容器 $G$ 的过程:

   • 假设 $G$ 有 $k’n^{3/2}$ 条边。我们应用 Theorem 48，在 $G$ 中找到一个平衡的 $C_4$ 超图 $\mathcal{H}$。
   • 然后对这个性质良好的 $\mathcal{H}$ 应用超图容器引理。关键是选择合适的参数 $\tau$。如上一问的分析，我们选择 $\tau = \max\{\frac{\delta}{(k’)^2}, \frac{1}{k’n^{1/6}}\}$ 来满足引理的度数条件。
   • 容器引理会生成一族新的、更小的容器（它们是 $G$ 的子图）。这一步生成的容器数量（即成本）由 $\tau$ 和 $v(\mathcal{H})$ 决定，其数量的对数（即指数部分）大致为：
     $ \text{成本(指数)} \approx n^{3/2} \varepsilon \cdot \max\left\{ \frac{\log k’}{k’}, \frac{\log n}{n^{1/6}} \right\} $

3. 累加总成本:

   • 总容器数是每一步“打碎”操作产生的容器数的乘积，所以总成本是所有指数的和。
   • 总指数 $\approx \sum_{i=1}^{m} \left( n^{3/2} \varepsilon \cdot \max\left\{ \frac{\log k(i)}{k(i)}, \frac{\log n}{n^{1/6}} \right\} \right)$
   • 由于 $k(i)$ 指数级下降，而函数 $\frac{\log x}{x}$ 在 $x$ 较大时递减，所以求和项 $\frac{\log k(i)}{k(i)}$ 是递增的。整个和由最后几项（当 $k(i)$ 接近常数 $k_0$ 时）主导。
   • 定理中 $k \le n^{1/6}/\log n$ 的条件保证了 $max$ 函数中总是第一项 $\frac{\log k(i)}{k(i)}$ 更大。
   • 经过仔细的计算，这个和的量级最终由 $O(\frac{\log k}{k})$ 决定，所以总容器数上界为 $\exp\left( C \frac{\log k}{k} n^{3/2} \right)$。

4. 应用

利用 Theorem 49，我们可以推导出关于随机图中 $C_4$-free 子图的结论。

Theorem 50.

对于 $p \ge n^{-1/3}(\log n)^3$，随机图 $G(n,p)$ 中最大的无 $C_4$ 子图的边数 $ex(G(n,p), C_4)$ 以高概率不超过 $p^{1/2} n^{3/2} \log n$。

证明思路:

1. 假设 $G(n,p)$ 中存在一个很大的无 $C_4$ 子图 $H$，其边数为 $m$。
2. 根据 Theorem 49，这个 $H$ 必然被包含在我们的某个容器 $G \in \mathcal{G}(n,k)$ 中。
3. 我们使用Union Bound：$P(\text{存在这样的} H) \le \sum_{G \in \mathcal{G}(n,k)} P(G \text{ 包含 } H \text{ 这样大的子图})$。
4. 对于单个容器 $G$，它在 $G(n,p)$ 中包含 $m$ 条边的概率极小，可以用 Chernoff 界得到，这个概率约为 $\exp(-\Omega(pn^2))$。
5. 将这个极小的概率乘以容器的总数 $|\mathcal{G}(n,k)|$。通过精细地选择参数 $k$ (使其满足 $\frac{\log k}{k^2} \approx p$)，可以证明最终的乘积依然趋向于0。

Theorem 51.

这个定理给出了 $ex(G(n,p), C_4)$ 在不同 $p$ 的取值范围下更精确的量级。其证明更为复杂，讲义中省略了。

---

Conjecture 52.
最后，作者提出了一个关于一般二部图 $H$ 的“平衡超饱和猜想”，并指出如果该猜想成立，将能证明不含 $H$ 的图的数量为 $2^{O(ex(n,H))}$。这为未来的研究指明了方向。