Triangle removal 引理 (3-3)

≤──于是可知

|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

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