Triangle removal 引理-拓崇最新章节-免费小说-全文免费阅读-拓崇作品-话本小说网

掌握 Szemerédi regularity lemma 以后我们来看如何使用它，如何用它来证明 triangle removal lemma

这篇我们学习在 Rusza-Szemerédi 的1978文章里的两个命题，证明的思路都差不多，两相对比正好可以体会 Szemerédi regularity lemma 的使用方法，证明的写法来自Additive Combinatorics

本篇中提及的图都指n 点图 G＝G(V，E)

Triangle removal lemma

命题对于任何给定 ε＞0 都存在一个 δ＞0 使得对任何图 G 如果至多包含 δn³ 个三角形，那可以移除 εn² 条边之后令 G 中无三角形

命题从直观上可以理解为当图比较稠密的时候，随机的来讲一条边可能会参与O(n) 数量级的三角形

如果我们可以把原图通过正则性引理划分，消除那些的不好的边以后剩余的部分是高度正则的，高度正则意味着一旦有一个三角形存在就会有数量多于 δn³ 的三角形，所以如果不好的边的数量级被 εn² 控制，而三角形数量不超过 δn³ 的话，它们一定会被消除掉

证明

粗略地说，G 的三个子集 X，Y，Z 间的边的密度分别是 dxʏ，dʏᴢ，dᴢx 的话，它们之间构成的三角形数量大约是 dxʏ dʏᴢ dᴢx |X||Y||Z|

精确的说，如果三个子集两两都是ε 正则，同时假设边的密度 dxʏ，dʏᴢ，dᴢx 至少都达到 2ε 的话，至少构成 (1–2ε)(dxʏ–ε)(dʏᴢ–ε)(dᴢx–ε)|X||Y||Z| 个三角形

用 Szemerédi regularity lemma 对图 G 做 ε/4 正则划分 V₁∪. . . ∪Vₖ

我们主要的想法是移除那些非正则划分的连接、低密度划分的连接、以及比较小的划分内的连接，它们都称为坏边，再利用剩余部分的高度正则性构造出很多的三角形

坏边 e 是

• e 连接某非 ε/4 正则对 (Vᵢ，Vj)

• e 连接某对 (Vᵢ，Vj) 满足 d(Vᵢ，Vj)≤ε/2

• e 连接某对 (Vᵢ，Vj) 满足 |Vᵢ|≤εn/4k 或者 |Vj|≤εn/4k

最多移除的边数

ε n² k ε n² εn n

(─k² • ─＋( ) • ─ ─＋k² • ─ ─)≤εn²

4 k² 2 2 k² 4k k

如果移除以后还存在某个三角形顶点分处于Vᵢ，Vj，Vₖ 的话， Vᵢ × Vj × Vₖ 会构成的三角形数量为

ε ε ε n

(1– ─) (─)³ (─ • ─)³

2 4 4 k

此时我们选择

ε ε ε

δ＜(1– ─) (─)³ (─)³

2 4 4k

也即只要总的三角形数量不超过

ε ε ε

(1– ─) (─)³ (─)³ n³我们总可以通过移除

2 4 4k

那些坏边消除所有的三角形，否则如果无法消除的话，剩余的数量都会超过

命题证完

关于配对的命题

如果图G 的一组边 {e₁，. . .，eₖ}两两不共点，而且这些顶点在图中不相连，它们被称为一个配对

命题如果图 G 的边是 n 个配对的并集，那么 |E|＝ᴏₙ→∞(n²)

配对里面的那些点相互之间最多一个连接，说明它们是稀疏的，或者很不随机

这个命题直观上说的是，如果图 G 的边可以分成 n 个配对，说明单个的配对是比较大的，而 |E|＝oₙ→∞(n²) 不成立则意味着图稠密，稠密的图中是不可能存在大范围的配对的，它们的顶点一定会被连起来

为了证明这一点我们需要把这个稠密图通过正则性引理划分，然后消除那些不好的边，让剩余的部分高度正则，如果某个配对还留在里面，那一定会导致矛盾

证明

假设命题不成立，对于某个固定的ε＞0 只要大图 G 至少有 εn² 条边，它都可以分解为 n 个配对的并集

用 Szemerédi regularity lemma 对图 G 做 ε/6 正则划分 V₁∪. . .∪Vₖ

具体的做法是移除那些非正则划分的边、低密度划分的边、以及所有划分内的边，这些称为坏边，剩余的部分高度正则，如果它们在某个配对当中也不少，那它们的随机属性将与配对的系数属性相矛盾

坏边 e 是

• e连接某非 ε/6 正则对 (Vᵢ，Vj)

• e连接某对 (Vᵢ，Vj) 满足 d(Vᵢ，Vj)≤ε/3

• e在某 Vᵢ 中

去除的坏边总数为

ε k n² ε n² n/k ε

(─ ( ) ─＋─k² ─＋k( ))≤ ─n²

3 2 k² 6 k² 2 2

我们当然可以控制 k 足够大使得 1/k 相对 ε 足够小满足不等式

剩余好边≥εn²/2 ，故至少有一个配对 F 包含至少 εn²/2n＝εn/2 条好边

那些至少包含F 中 ε|Vᵢ|/3 个点的划分集 Vᵢ 称作糟糕的集合，我们如果删去所有糟糕的 Vᵢ 在 F 中的部分连同边，最多删去 Σᵢ ε|Vᵢ|/3＝εn/3 条边，所以 F 至少还剩一条边，由定义这条边会连接两个不糟糕的集合 Vᵢ，Vj ，这两个集合满足 d(Vᵢ，Vj)≥ε/3 同时是 ε/6 正则的，令 Vᵢ，ғ＝Vᵢ∩F，Vj，ғ＝Vj∩F 于是

ε ε

d(Vᵢ，ғ，Vj，ғ)≥d(Vᵢ，Vj)– ─ ≥ ─

6 6

• 一方面，因为 F 是配对，所以 Vᵢ，ғ 和 Vj，ғ 的边数不能超过 |Vᵢ，ғ| ，所以 d(Vᵢ，ғ，Vj，ғ) 1

≤──于是可知

|Vj，ғ|

|Vj，ғ|≤6/ε

• 另一方面，由定义 |Vj，ғ|≥ε|Vj|/3 而且 |Vj|＝n/k＋O(1) 于是可知 n＝Oε，ₖ(1)＝Oε(1) 这个与 n 可以任意大相矛盾

命题证完

Roth's Theorem

用rₖ(A) 表示 A 当中不包含长度为 k 的等差数列的最大的子集的长度，于是 Roth's Theorem 说的是 r₃(ℤɴ)＝oɴ→∞(N) ，它后来有个推广说的是对奇数阶的有限加群 Z 来说 r₃(Z)＝o|ᴢ|→∞(|Z|)，这个结论对偶数阶的群是不成立的，有反例

证明

不妨就设一个固定的奇数阶的有限加群Z ，它的子集 A 不包含任何三项以上的等差数列，我们需要证明 |A|＝o|ᴢ|→∞(|Z|)

构造个二分图G ，两边的点分别是 Z × {1} 和 Z × {2}，对所有的 α∈Z，r∈A 连接点 (α＋r，1) 和 (α＋2r，2) ，我们可以观察到对于所有的 r∈A 构成一个配对，这是因为如果还有一条从 (α＋r，1) 和 (α＋2s，2) 的连接的话，可以知道 2s–r∈A ，于是有一个 A 中的等差数列是 {r，s，2s–r} ，矛盾

奇数阶的条件令2为可逆

这样一来G 可以看成是 |Z| 个配对的并，根据上面的命题边数等于 o|ᴢ|→∞(|Z|²) ，同时我们知道边数为 |A||Z| ，于是有 |A|＝o|ᴢ|→∞(|Z|)

命题证完

注解

我们现在已经看到了从 Szemerédi regularity lemma 到 triangle removal lemma 再到 Roth's Theorem 的过程

从一个看似杂乱无章的图里面，正则化以后再清洗掉一些零零碎碎的部分，最后的结构很容易计算操作，真的令人叹为观止

这个过程还可以继续推广，不过这个过程花了不少的年头，从普通的图推广到所谓 hypergraph 以后，问题变得更复杂一些，可以导致 Szemerédi Theorem