2. 三角形记数和删除引理

Szemerédi 的正则性引理是解决极值图论和加性组合问题的强大工具. 在本节中, 我们应用正则性引理来证明定理 2.3, 即 Roth 的 3 项等差数列定理. 我们首先介绍三角形计数引理, 它提供了一种从规则划分中提取信息的方法, 然后我们用这个结果来证明三角形删除引理, 从而证明 Roth 定理. 正如我们在上一节中提到的, 如果图 $G$ 顶点的两个子集是 $ϵ$ -正则的, 那么直观地讲, 这些子集之间的二部图表现得像误差为 $ϵ$ 的 “类似随机”. 对 “类似随机” 的一种解释是, “小图案” 的副本数应大致等于我们在具有相同边密度的随机图中看到的计数. 通常, 这些图案对应于固定的子图, 例如三角形.

如果具有顶点子集 $X, Y, Z$ 的图 $G$ 是随机的, 三元组 $(x, y, z) \in X \times Y \times Z$ 表示 $x, y, z$ 在 $G$ 中构成的三角形, 我们希望三元组的数量大致为

$d (X, Y) d (X, Z) d (Y, Z) \cdot ∣ X ∣∣ Y ∣∣ Z ∣$ (2.1)

笔记 2.1. 请注意, 集合 $X, Y, Z$ 不一定是不相交的.

三角形计数引理确保了这种直觉是对的.

定理 2.2 (三角形计数引理).

设 $X, Y, Z$ 为图 $G$ 的顶点的子集, 满足 $(X, Y), (Y, Z), (Z, X)$ 都是 $ϵ -$ 正则对, $ϵ > 0$ . 让 $d_{X Y}, d_{XZ}, d_{Y Z}$ 分别表示边缘密度 $d (X, Y), d (X, Z), d (Y, Z)$ . 若 $d_{X Y}, d_{XZ}, d_{Y Z} \geq 2 ϵ$ , 则使 $x, y, z$ 在 $G$ 中形成一个三角形的三元组 $(x, y, z) \in X \times Y \times Z$ 的数量至少是 $(1 - 2 ϵ) (d_{X Y} - ϵ) (d_{XZ} - ϵ) (d_{Y Z} - ϵ) \cdot ∣ X ∣∣ Y ∣∣ Z ∣$

笔记 2.3. 定理中给出的三角形 $X \times Y \times Z$ 中的三元组数量的下界类似于 2.1 中的表达式, 但由于图不是完全随机的, 我们引入了依赖于 $ϵ$ 的附加误差项.

证明. 根据假设, $(X, Y)$ 是一个 $ϵ$ -正则对. $X$ 中满足如下条件的顶点数少于 $ϵ ∣ X ∣$ : 该顶点在 $Y$ 中的邻点数少于 $(d_{X Y} - ϵ) ∣ Y ∣$ . 如果不成立, 那么 $Y$ 与满足条件的 $X$ 顶点构成的子集可以见证 $(X, Y)$ 非正则性, 这与我们的假设相矛盾. 直观地说, 这一上界是合理的, 因为如果 $X$ 和 $Y$ 之间的边是随机的, 我们会希望 $X$ 中的大多数顶点在 $Y$ 中有大约个 $d_{X Y} ∣ Y ∣$ 邻点, 这也意味着 $X$ 中没有太多顶点可以在 $Y$ 中具有很小的度.

我们对 $ϵ$ -正则对 $(X, Z)$ 应用相同的证明方法得到了类似的结果, 即在 $Z$ 有少于 $(d_{XZ} - ϵ) ∣ Z ∣$ 个邻点的 $X$ 的顶点数量少于 $ϵ ∣ X ∣$ . 结合这两个结果, 我们可以找到大小至少为 $(1 - 2 ϵ) ∣ X ∣$ 的 $X$ 的子集 $X^{'}$ , 满足所有 $x \in X^{'}$ 至少与 $Y$ 中 $(d_{X Y} - ϵ) ∣ Y ∣$ 个元素和 $Z$ 中 $(d_{XZ} - ϵ) ∣ Z ∣$ 个元素相邻. 根据假设 $d_{X Y}, d_{XZ} \geq 2 ϵ$ 以及 $(Y, Z)$ 是 $ϵ$ -正则的事实, 我们看到对于任何 $x \in X^{'}$ , $Y$ 和 $Z$ 中 $x$ 的邻域之间的边密度至少为 $(d_{Y Z} - ϵ)$ .

现在, 对于

X^{'}

中的每个顶点

x

,

Y

中

x

的邻域和

Z

中

x

的邻域之间的边的数量至少为

(d_{X Y} - ϵ) (d_{XZ} - ϵ) (d_{Y Z} - ϵ) ∣ Y ∣∣ Z ∣

, 我们在

G

中得到一个唯一确定的

(X, Y, Z)

-三角形. 注意到

X^{'}

的大小至少为

(1 - 2 ϵ) ∣ X ∣

, 因此, 这种三角形的数量至少是

(1 - 2 ϵ) (d_{X Y} - ϵ) (d_{XZ} - ϵ) (d_{Y Z} - ϵ) \cdot ∣ X ∣∣ Y ∣∣ Z ∣

这是我们想要的.

$□$

我们的下一步是使用定理 2.2 来证明三角形删除引理, 它指出我们可以通过去除 “少量” 边使具有 “很少” 三角形的图变成 triangle-free 的.

定理 2.4 (三角形删除引理).

对于任意 $ϵ > 0$ , 存在 $δ > 0$ 使得任何三角形数量小于等于 $δ n^{3}$ 的 $n$ 顶点图都可以通过删除至多 $ϵ n^{2}$ 边变成 $triangle - free$ 图.

笔记 2.5. 一种等效但偷懒的三角形删除引理的表述是说,

任何带有 $o (n^{3})$ 个三角形的 $n$ 顶点图都可以通过删除 $o (n^{2})$ 条边变成无三角形的.

这一表述是考虑定理 2.4 的一种有用方式, 但由于使用了渐近符号, 因此有些模糊. 一种更细致的表述是,

对于任何函数 $f (n) = o (n^{3})$ , 存在一个函数 $g (n) = o (n^{2})$ 使得每当 $n$ 顶点图具有小于或等于 $f (n)$ 的三角形时, 我们最多可以删除 $g (n)$ 边以使图变成 $triangle - free$ 的.

另一种形式的陈述是将其视为关于图序列的结论,

给定一系列图 ${G_{n}}$ , 其性质是对于每个自然数 $n$ , 图 $G_{n}$ 具有 $n$ 个顶点和 $o (n^{3})$ 三角形, 我们可以通过从每个图 $G_{n}$ 中删除 $o (n^{2})$ 条边来使序列中的所有图都是 $triangle - free$ 的.

定理 2.4 的证明使用了 Szemerédi 正则性引理, 并很好地演示了通常情况下我们如何应用正则引理. 我们使用正则引理的方法主要分以下三步进行.

1.	通过应用定理 1.1.5 来划分图的顶点以获得 $ϵ$ -正则划分, $ϵ > 0$ .
2.	去除在正则引理的结构中表现不佳的边. 具体来说, 去除非正则对、边密度低的对和某一端点在小块的对. 此步骤中移除的边总数很小.
3.	计算清洁后图中特定图案的副本数, 应用计数引理 (例如, 当图案为三角形时, 定理 2.2) 得到副本数.

定理 2.4.

假设我们有一个 $n$ 顶点图, 其中三角形副本数少于 $δ n^{3}$ , 参数 $δ$ 我们稍后会选择. 首先对图进行 $ϵ /4$ -正则划分, 划分结果为 $V_{1}, V_{2}, \dots, V_{M}$ . 接下来, 对于每对有序对 $(V_{i}, V_{j})$ , 删除 $V_{i}$ 和 $V_{j}$ 之间的所有边, 如果下面几种情况之一

1.	$(V_{i}, V_{j})$ 是非正则对,
2.	密度 $d (V_{i}, V_{j})$ 小于 $ϵ /2$ ,
3.	$V_{i}$ 或 $V_{j}$ 最多有 $(ϵ /4 M) n$ 个顶点.

我们考虑在这个过程中一共去除了多少边? 由于我们采用了 $ϵ /4$ -正则划分, 根据定义 $( V _{i} , V _{j} ) not ϵ /4 - regular i , j \sum ∣ V_{i} ∣ ∣ V_{j} ∣ \leq \frac{ϵ}{4} n^{2}$ 所以至多 $(ϵ /4) n^{2}$ 条边在 (a) 中被移除. (b) 中移除的边数为 $d ( V _{i} , V _{j} ) < ϵ /2 i , j \sum d (V_{i}, V_{j}) ∣ V_{i} ∣ ∣ V_{j} ∣ \leq \frac{ϵ}{2} i, j \sum ∣ V_{i} ∣ ∣ V_{j} ∣ = \frac{ϵ}{2} n^{2}$ (c) 中去除的边数最多为 $n \cdot \frac{ϵ}{4 M} n \cdot M = \frac{ϵ}{4} n^{2}$ 这是因为 $n$ 顶点中每个顶点最多与 $(ϵ /4 M) n$ 个 “小” 块中的顶点相邻, 并且最多有 $M$ 个 “小” 的块.

我们看到, 通过删除 “表现不佳” 的对之间的边来清理图并不会删除太多边. 我们声称在这个过程之后, 对于某些 $δ$ , 该图是 $triangle - free$ 的. 删除引理和该声明相恰, 因为前一步从图中删除的边数小于 $ϵ n^{2}$ .

我们假设在遵循上述过程并 (可能) 移除一些边后, 得到的图中仍然有三角形. 然后我们可以找到包含这个三角形的每个顶点所在的块

V_{i}, V_{j}, V_{k}

(不一定是不同的) . 因为 (a) 和 (b) 中描述的对之间的边被删除,

V_{i}, V_{j}, V_{k}

满足三角形计数引理的假设. 将定理 2.2 应用于这三组子集, 该图仍然至少有

(1 - \frac{ϵ}{2}) (\frac{ϵ}{4})^{3} \cdot ∣ V_{i} ∥ V_{j} ∥ V_{k} ∣

个三角形. 通过 (c) 知, 这些区域中的每一个的大小都至少为

(ϵ /4 M) n

, 所以实际上

(V_{i}, V_{j}, V_{k})

是三角形的数量至少是

(1 - \frac{ϵ}{2}) (\frac{ϵ}{4})^{3} (\frac{ϵ}{4 M})^{3} \cdot n^{3}

然后通过选择正的

δ < \frac{1}{6} (1 - \frac{ϵ}{2}) (\frac{ϵ}{4})^{3} (\frac{ϵ}{4 M})^{3}

我们得到了一个矛盾, 因为根据假设, 原始图有少于

δ n^{3}

个三角形, 但是三角形计数引理表明, 在删除图中的一些边后, 图中严格地多于这么多三角形. 此处存在

1/6

的系数用来处理可能发生的重复计数 (例如, 当

V_{i} = V_{j} = V_{k}

时) . 因此假设不成立. 由于

δ

仅取决于

ϵ

和定理 1.1.5 中的常数

M

, 这就完成了证明.

$□$

笔记 2.6.

在上述证明中, $δ$ 取决于 $M$ , 即定理 1.1.5 中的常数. 如定理 1.1.12 所述, 常数 $M$ 的增长是迅速的. 我们的证明仅表明我们可以选择 $δ$ 使得 $1/ δ$ 被高度为 $ϵ^{- O (1)}$ 的 2 的迭代幂次控制. 事实上, 只要我们选择 $δ$ 使得 $1/ δ$ 被一个高度为 $O (lo g (1/ ϵ))$ 的 2 的迭代幂次控制, 三角形删除引理成立. 相比之下, 在本文中最著名的 “下界” 结果是, 如果 $δ$ 满足定理 2.4 的条件, 则 $1/ δ$ 的上界为 $ϵ^{- O (l o g (1/ ϵ))}$ (这个上界来自我们很快将讨论到的 $3 - A P - free$ 集的构造) . 这些上界和下界之间的差距很大, 缩小这个差距是图论中的一个主要的开放性问题.

从历史上看, 证明定理 2.4 的一个主要动机是该引理与 Roth 定理的联系. 这种联系来自于前面在问题 3.0.3 中提到的一种特殊类型的图. 三角形删除引理的以下推论有助于研究此类图.

推论 2.7. $G$ 是一个 $n$ 顶点图, 且 $G$ 的每条边都位于一个唯一的三角形中, 则 $G$ 有 $o (n^{2})$ 条边.

证明. 假设 $G$ 有 $m$ 条边. 因为每条边都在一个三角形中, 所以 $G$ 中的三角形数是 $m /3$ . 由于 $m < n^{2}$ , 所以 $G$ 有 $o (n^{3})$ 个三角形. 通过备注 2.5, 我们可以删除 $o (n^{2})$ 条边, 使 $G$ 变成 $triangle - free$ 图. 但是根据假设, 删除一条边最多从图中删除一个三角形, 因此在此过程中删除的边数至少为 $m /3$ . 因此 $m = o (n^{2})$ .

$□$

名字空间

视图

2. 三角形记数和删除引理