Triangle removal 引理 (3-2)

ε ε ε

(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

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