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

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

相关小说

妖娆夫君个个宠 连载中
妖娆夫君个个宠
幽兰溪谷
【已签约,已完结】《女帝篇》她堂堂白氏家族的继承人,遭人算计……再次醒来居然成了六岁孩童,还是一国长公主……从此以后开启了她的异世之旅………......
28.5万字9个月前
粮仓(多种CP) 连载中
粮仓(多种CP)
彤彤1532
美英
0.2万字9个月前
天蛇白矖 连载中
天蛇白矖
牛奶炖榴莲
天蛇白矖(xi,三声)明明记得自己已经亲手被“墨圣禹”杀死!醒来却身在人界,还是香士世家,白家的大小姐?莫不是被别人用重魄灯重塑肉身?只是,......
15.5万字9个月前
迷途茶馆 连载中
迷途茶馆
御眠
“踏入迷途便是你我有缘,说出你的故事与我达成交易。”——顾楠曦
11.5万字9个月前
时黎:你是我的神之救赎 连载中
时黎:你是我的神之救赎
雪辞瑶
时字开头黎字结尾,时黎是意料之外可却不是意难平,她是御王的偏爱与底线更是神,他是时希的唯一,是她的爱人更是救赎
2.1万字9个月前
使魔大人请上座 连载中
使魔大人请上座
该用户已注销
努力不一定会获得成功,但不努力你一定是条咸鱼!作为圣魔道学院召唤系最没资质、也没什么背景,召唤六百多次却一直失败的废材学员,花间神月仍不言败......
12.8万字9个月前