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

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

相关小说

快穿:前女友靠生子恩宠一生 连载中
快穿:前女友靠生子恩宠一生
林悸柠
【甜宠+1VN】
0.2万字9个月前
某屑作者因玩changed玩抽风了写了个文 连载中
某屑作者因玩changed玩抽风了写了个文
抽象问世
标题旁白写的(确信)
2.9万字9个月前
唯一的知情人 连载中
唯一的知情人
仿古雀鸟
陈小梦以月冰的身份,诞生了这个充满灵力的庸俗设定岛屿中,能力规则都懂,唯一对自己的身份抱有谜题,从碎碎念到默不作声(包含搞笑成分并且前几章,......
6.6万字9个月前
我还爱着你1 连载中
我还爱着你1
聆旧忘
与你的点点滴滴
0.2万字9个月前
玄梦空间 连载中
玄梦空间
林夕租橙梦
前世情人找上门✔男主全洁且双标✔武斗情节✔[你已征服了我,为何还不属于我?]“我也不想脚踏这么多船啊,关键是他们怎么甩都甩不掉啊!”“哎,没......
14.8万字9个月前
半路夭途 连载中
半路夭途
泠月兮
半路偶遇一个“盲人”寒夜,修炼千年的狐妖枫泠发现这人类的灵魂格外的诱人,可偏偏天上有一个天道看着,怎么办呢?枫泠一路跟着,却发现这人并不简单......
4.5万字9个月前