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