数学联邦政治世界观
超小超大

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),接着再看更方便。

相关小说

轮回五:火海 连载中
轮回五:火海
酒生清栀
“我属于您。”有记忆的时候,这个人就如影随形地跟在身后。为此我被玩伴们在私下嬉笑了很多次,说“大小姐就是尊贵啊”。小时候和他置气过很多次,结......
1.5万字9个月前
ch综艺体?! 连载中
ch综艺体?!
客醉倚河桥,清光愁玉箫
等我更文(可能有cp出现?)
0.0万字9个月前
双生箭派 连载中
双生箭派
金梦兰
随机时段更新
10.8万字9个月前
四方食事 连载中
四方食事
鸽手云景
有人愿倾尽一生成就千古名肴,亦有人于寻常巷陌品味俗世烟火。“文手可以利用不同属性的魔法制作不同形态的食物。它们不仅具备最基本的色香味,也包含......
11.7万字9个月前
如果可以重来一次,你还愿意做我的姐姐吗?之紫薇重生 连载中
如果可以重来一次,你还愿意做我的姐姐吗?之紫薇重生
柠檬遇芃芃
紫薇重生
2.4万字9个月前
末世之论冰块如何撩妻 连载中
末世之论冰块如何撩妻
木乙殇
末世为皮,甜饼为馅“大冰块,别那么没有情趣嘛,本来就是在末世,再不看开点,要憋坏了。”言乐一脸坏笑的看着身边满脸写着生人勿近的封怀。但那个某......
7.3万字9个月前