特殊篇章（数学定理）二 (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），接着再看更方便。