Triangle removal 引理 (3-1)

掌握 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

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

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。