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

特殊篇章(数学定理)二 (6-1)

介绍:Balog-Szemerédi-Gowers 定理

我喜欢这个定理的证明,只用到基本的图论做一些简单的估计,但是这个定理用处很大,它可以把关于两个加集 A 和 B 的部分和/差的控制加之于两个子集 A′⊂A,B′⊂B 的完全和/差上去,而代价仅是对 A,B 常数级别的缩减

考虑二分图 G=G(A,B,E) ,它的边集 E 定义了一个所谓部分和集合 A ᴳ+B ,当且仅当 (α,b)∈E 的时候, α+b∈G ,其中 α∈A,b∈B

Balog-Szemerédi 在1994年证明了这样的结果,如果 |A|=|B|=n ,并且 |E|≥n²/K 同时 |A ᴳ+B|≤K′n ,其中 K,K′ 都是常数,那么可以找到子集 A′⊂A,B′⊂B 使得 |A′|,|B′|,|A′+B′|=Θᴋ,ᴋ′(n)

Gowers 后来的结果可以把 Θᴋ,ᴋ′(n) 中的系数取做 K,K′ 的多项式,甚至 K,K′ 都可以取做 nϵ ,这里 ϵ>0

我们可以把 Balog-Szemerédi-Gowers 定理看作是关于稠密二分图的,如果一个二分图 G(A,B,E) 有足够多的边的话,将有很多的 α∈A,b∈B 被长度为一的 1 路径连接,继而就有很多的 α,α′∈A 被长度为二的 2 路径连接,继而就有很多的 α∈A,b∈B 被长度为三的 3 路径连接,等等,这是关于Balog-Szemerédi-Gowers 的直观

证明需要分别对图中的 2 路径和 3 路径做估计

引理1 2 路径的估计

给定 |E|≥|A||B|/K, K≥1 的二分图 G(A,B,E) ,对于任何 0≤ϵ≤1 都能找到 A′⊆A 使得 |A′|≥|A|

──

√2K

并且至少有 1−ϵ 比例的配对 α,α′∈A′ 被至少

ϵ

──

2K²|B| 条 G 中的 2 路径相连

证明

首先不妨减小 K 以后我们就假设 |E|=|A||B|/K ,考虑恒等式

N(b) N(α) |E| 1

── ── ── ─

• 𝔼b∈B |A|=𝔼α∈A |B|= |A||B|=K

无非是从 B 和 A 的角度计算 |E|/|A||B|而已

|N(b)|²

──

• 𝔼b∈B |A|²

|N(α)∩N(α′)|

───────

=𝔼α,α′∈A |B|

两边都是计算 2 路径 (α,b),(b,α′) 的个数

使用 Cauchy-Schwarz 我们可以得到 𝔼α,α′∈A |N(α)∩N(α′)| 1

──────≥ ─

|B| K²

考察配对 α,α′∈A 的集合 Ω ,它们的连接比较弱 |N(α)∩N(α′) ϵ

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

相关小说

是梦还是?我已陷入 连载中
是梦还是?我已陷入
程捷_69473298369067015
一个对自己所在城市失去希望的人,因为一次偶然发现另一个世界。在这她有会遇到什么?
0.2万字4周前
半生烟火一生迷离 连载中
半生烟火一生迷离
徐熙亦悠
双胞胎姐妹从十岁那年被两个首领分别带入自己的领地培养,两姐妹命运就从这里开始。他们从接手时的目的一致,把她们培养成全世界最厉害的人为己所用,......
36.8万字4周前
神主手下留情 连载中
神主手下留情
谢落雕花
作为一个震慑四方的神却被一个人类给迷住了,接下来他将会如何行动呢?
0.7万字4周前
狂妃在上:腹黑帝尊日夜宠 连载中
狂妃在上:腹黑帝尊日夜宠
墨倾屿
夜澜默:“染儿,抱抱”苏染漓:“有这么黏人的老公怎么办?”
14.7万字4周前
爱无限制 连载中
爱无限制
洛莹*
沙雕轻松日常,女主是腐女,带头嗑CP,强強,作者学生党,请轻喷,更新不定时
6.8万字4周前
精灵梦叶罗丽之希月之星辰 连载中
精灵梦叶罗丽之希月之星辰
星辰柔汐颜
有一个与人类世界平行的童话世界,叶罗丽仙境。莹月和时希还有灵公主在一次偶然中成为了很好的朋友,仙境大战突如其来,很多仙子都选择了自己的立场,......
0.5万字4周前