5. 图嵌入、计数和删除引理

如三角形删除引理定理 2.0.4 的证明所展示的, 删除引理的一个关键前奏是计数引理. 因此, 我们想将三角形计数引理推广到一般图形. 为了实现我们的目标, 我们有两种策略: 一种是将计数图的顶点一个一个嵌入, 使待嵌入的顶点有很多选择; 另一种是分析一次删除一条边.

定理 5.1 (图嵌入引理). 令 $H$ 为顶点度不超过 $Δ$ 的 $r$ 部图. 在图 $G$ 中, 令 $V_{1}, \dots, V_{r} \subseteq V (G)$ 是大小至少为 $\frac{1}{ϵ} v (H)$ 的顶点集. 如果每对 $(V_{i}, V_{j})$ 是 $ϵ$ -正则的并且密度 $d (V_{i}, V_{j}) ⩾ 2 ϵ^{1/Δ}$ , 则 $G$ 包含 $H$ 的副本.

笔记 5.2. 定理中的顶点集 $V_{1}, \dots, V_{r}$ 不需要不相交甚至不需要不同.

我们将介绍证明的一些想法, 省略细节. 定理 5.1 的证明是定理 2.0.2 证明的扩展.

假设我们试图嵌入

H = K_{4}

, 其中

K_{4}

的每个顶点都进入到自己的块, 其中四个块是两两之间是

ϵ

-正则的且边密度不太小. 我们按顺序嵌入顶点, 大多数第一个顶点的选择不会将剩余顶点的可能性减少一个比基于边密度的预期的要多得多的因子. 第一个顶点已经嵌入后, 我们继续第二个顶点, 再次选择一个嵌入, 以便为第三个和第四个顶点保留较多的可能性, 依此类推.

[H](...) 嵌入

H = K_{4}

的示意图接下来, 我们使用我们的第二个策略来证明计数引理.

定理 5.3 (图计数引理).

令 $H$ 是一个 $V (H) = [k]$ 的图, 令 $ϵ > 0$ . 令 $G$ 是一个 $n$ 顶点图, 顶点子集 $V_{1} \dots, V_{k} \subseteq V (G)$ 对于任意 ${i, j} \in E (H)$ , $(V_{i}, V_{j})$ 是 $ϵ$ -正则的. 则元组 $(v_{1}, \dots, v_{k}) \in V_{1} \times \dots \times V_{k}$ 的数量大约为 $⎝ ⎛ {i, j} \in E (H) \prod d (V_{i}, V_{j}) ⎠ ⎞ (i = 1 \prod k ∣ V_{i} ∣)$ 且最大相差 $e (H) ϵ ∣ V_{1} ∣ 内时 \dots ∣ V_{k} ∣$ . 其中, 元组 $(v_{1}, \dots, v_{k})$ 满足对于所有的 ${i, j} \in E (H)$ , ${v_{i}, v_{j}} \in E (G)$ .

笔记 5.4. 该定理可以改写为以下概率形式: 均匀随机且独立地选择 $v_{1} \in V_{1}, \dots, v_{k} \in V_{k}$ . 则, $∣ ∣ P ({v_{i}, v_{j}} \in E (G) for all {i, j} \in E (H)) - {i, j} \in E (H) \prod d (V_{i}, V_{j}) ∣ ∣ ⩽ e (H) ϵ$ (5.1)

证明. 我们可以假设 ${1, 2}$ 是 $H$ 的边 (如果不是可以通过对顶点重新标号实现) . 为了简化符号, 记 $P = P ({v_{i}, v_{j}} \in E (G) for all {i, j} \in E (H))$ 我们将证明

$∣ P - d (V_{1}, V_{2}) P ({v_{i}, v_{j}} \in E (G) for all {i, j} \in E (H) \ {{1, 2}}) ∣ ⩽ ϵ$ (5.2)合并两个选择 $v_{i}$ 的随机过程, 我们证明当 $v_{3} 、 \dots 、 v_{k}$ 是任意给定的并且只有 $v_{1}$ 和 $v_{2}$ 是随机时 (5.2) 成立即可. 定义 $A_{1} := {v_{1} \in V_{1} : {v_{1}, v_{i}} \in E (G) whenever i \in N_{H} (1) \ {2}} A_{2} := {v_{2} \in V_{2} : {v_{2}, v_{i}} \in E (G) whenever i \in N_{H} (2) \ {1}}$ 如果 $∣ A_{1} ∣ ⩽ ϵ ∣ V_{1} ∣$ 或者 $∣ A_{2} ∣ ⩽ ϵ ∣ V_{2} ∣$ , 则 $\frac{e ( A _{1} , A _{2} )}{∣ V _{1} ∣ ∣ V _{2} ∣} ⩽ \frac{∣ A _{1} ∣ ∣ A _{2} ∣}{∣ V _{1} ∣ ∣ V _{2} ∣} ⩽ ϵ$ 显然有 $d (V_{1}, V_{2}) \frac{∣ A _{1} ∣ ∣ A _{2} ∣}{∣ V _{1} ∣ ∣ V _{2} ∣} ⩽ ϵ$ 所以 $∣ ∣ \frac{e ( A _{1} , A _{2} )}{∣ V _{1} ∣ ∣ V _{2} ∣} - d (V_{1}, V_{2}) \frac{∣ A _{1} ∣ ∣ A _{2} ∣}{∣ V _{1} ∣ ∣ V _{2} ∣} ∣ ∣ ⩽ ϵ$ 否则, 如果 $∣ A_{1} ∣ > ϵ ∣ V_{1} ∣$ 且 $∣ A_{2} ∣ > ϵ ∣ V_{2} ∣$ , 则由 $(V_{1}, V_{2})$ 的 $ϵ$ -正则性, 我们也有

$∣ ∣ \frac{e ( A _{1} , A _{2} )}{∣ V _{1} ∣ ∣ V _{2} ∣} - d (V_{1}, V_{2}) \frac{∣ A _{1} ∣ ∣ A _{2} ∣}{∣ V _{1} ∣ ∣ V _{2} ∣} ∣ ∣$ $= ∣ ∣ \frac{e ( A _{1} , A _{2} )}{∣ A _{1} ∣ ∣ A _{2} ∣} - d (V_{1}, V_{2}) ∣ ∣ \cdot \frac{∣ A _{1} ∣ ∣ A _{2} ∣}{∣ V _{1} ∣ ∣ V _{2} ∣} < ϵ$ 因此, 无论哪种情况, 当 $v_{3} 、 \dots 、 v_{k}$ 分别被视为 $V_{3} 、 \dots 、 V_{k}$ 中的固定顶点时, (5.2) 都成立.

为了完成计数引理的证明, 我们对

e (H)

进行归纳. 令

H^{'}

表示从

H

中去除边

{1, 2}

得到的图, 并假设当

H

被

H^{'}

代替时 (5.1) 始终成立. 然后,

∣ ∣ P ⩽ ⩽ ⩽ - {i, j} \in E (H) \prod d (V_{i}, V_{j}) ∣ ∣ d (V_{1}, V_{2}) ∣ ∣ P ({v_{i}, v_{j}} \in E (G) for all {i, j} \in E (H^{'})) - {i, j} \in E (H^{'}) \prod d (V_{i}, V_{j}) ∣ ∣ + ∣ ∣ P - d (V_{1}, V_{2}) P ({v_{i}, v_{j}} \in E (G) for all {i, j} \in E (H^{'})) ∣ ∣ d (V_{1}, V_{2}) e (H^{'}) ϵ + ϵ (e (H^{'}) + 1) ϵ = e (H) ϵ

第一个不等号成立是因为

∣ a - b ∣ \leq ∣ a - c ∣ + ∣ c - b ∣

.

$□$

定理 5.5 (图删除引理).

对于任意图 $H$ 和任意常数 $ϵ > 0$ , 存在一个常数 $δ > 0$ , 使得每个 $H$ 副本数小于 $δ n^{v (H)}$ 的 $n$ 顶点图 $G$ 可以通过删除不超过 $ϵ n^{2}$ 条边, 变成 $H - free$ 图.

图删除引理的证明和定理 2.0.4 的证明是类似的, 思路如下:

•	使用图正则性引理划分顶点集.
•	删除边密度低的对、非正则对和其中一个块较小的对之间的所有边.
•	计算剩余边的数量, 并证明如果图中仍然包含 $H$ 的副本, 那么它将包含非常多的 $H$ 的副本, 从而得出矛盾.

我们现在准备证明定理 4.4, 我们先来回顾一下该定理.

定理 5.6 (Erdös-Stone-Simonovits). 对于任何给定的图 $H$ , 我们有 $ex (n, H) = (1 - \frac{1}{χ ( H ) - 1} + o (1)) \frac{n ^{2}}{2}$

证明.

固定常数 $ϵ > 0$ . 令 $r + 1$ 表示 $H$ 的色数, $G$ 是任意具有至少 $(1 - \frac{1}{r} + ϵ) \frac{n ^{2}}{2}$ 条边的 $n$ 顶点图. 我们断言如果 $n = n (ϵ, H)$ 足够大, 则 $G$ 中一定包含 $H$ 的副本. 令 $V (G) = V_{1} ⊔ \dots ⊔ V_{m}$ 是图 $G$ 顶点集的 $η$ -正则划分, 其中 $η := \frac{1}{2 e ( H )} (\frac{ϵ}{8})^{e (H)}$ . 我们移除一条边 $(x, y) \in V_{i} \times V_{j}$ 如果满足以下任一条件:

1.	$(V_{i}, V_{j})$ 不是 $η$ -正则的
2.	$d (V_{i}, V_{j}) < \frac{ϵ}{8}$
3.	$∣ V_{i} ∣$ 或 $∣ V_{j} ∣$ 小于 $\frac{ϵ}{8 m} n$

落入情况 (a) 的边数不超过 $η n^{2}$ , 落入情况 (b) 的边数不超过 $\frac{ϵ}{8} n^{2}$ , 且落入情况 (c) 的边数不超过 $mn \frac{ϵ}{8 m} n = \frac{ϵ}{8} n^{2}$ . 因此, 删除的边总数不超过 $η n^{2} + \frac{ϵ}{8} n^{2} + \frac{ϵ}{8} n^{2} ⩽ \frac{3 ϵ}{8} n^{2}$ . 所以, 删完之后的图 $G^{'}$ 具有最少 $(1 - \frac{1}{r} + \frac{ϵ}{4}) \frac{n ^{2}}{2}$ 条边. 根据图兰定理, 我们知道 $G^{'}$ 一定包含一个 $K_{r + 1}$ 的副本. 我们用数字 $1, 2, \dots, r + 1$ 标记这个 $K_{r + 1}$ 副本的顶点. 假设 $K_{r + 1}$ 的顶点分别位于 $V_{i_{1}}, \dots, V_{i_{r + 1}}$ 中, 下标为 $i_{1}, \dots, i_{r + 1}$ 可能重复. 注意到, 每对 $(V_{i_{r}}, V_{i_{s}})$ 都是 $η$ -正则的. 由于 $χ (H) = r + 1$ , 因此存在正确的着色 $c$ : $V (H) = [k] \to [r + 1]$ . 对于每个 $j \in [k]$ , 令 $\tilde{V}_{j} := V_{c (j)}$ . 然后, 我们可以应用图计数引理 (定理 5.3) 到 ${\tilde{V}_{j} : j \in [k]}$ , 并发现从 $H$ 到 $G^{'}$ 的图同态数至少是

$(\prod_{{i, j} \in E (H)} d (\tilde{V}_{i}, \tilde{V}_{j})) (\prod_{i = 1}^{k} ∣ ∣ \tilde{V}_{i} ∣ ∣) - e (H) η (\prod_{i = 1}^{k} ∣ ∣ \tilde{V}_{i} ∣ ∣) ⩾ ((\frac{ϵ}{8})^{e (H)} - e (H) η) (\frac{ϵ n}{8 m})^{v (H)}$ 鉴于只有 $O_{H} (n^{v (H) - 1})$ 个非单射的映射 $V (H) \to V (G)$ (多个 $H$ 中的点映射到 $G$ 中同一个点的情况) . 因此对于足够大的 $n$ , $G$ 包含 $H$ 的副本.

$□$

名字空间

视图

5. 图嵌入、计数和删除引理