本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 定义 / 引理 / 推论 / 定理 / 例 / 分步推演）与配图为面向高中生的详解，逐步把每一步的动机讲清楚，不用比喻。
本节目标设两个数集 \(A,B\) 之间只有“一部分”加法被允许（由一张二部图的边给出），并且这些被允许的和 \(a+b\) 只占很少的取值。本节要证明：一定能从 \(A,B\) 里各挖出一大块 \(A'\subseteq A,\,B'\subseteq B\)，使得它们之间的全部和 \(A'+B'\) 仍然很少。也就是说，“稀疏的和集结构”可以被升级成“稠密子集上的完整和集结构”。核心工具是二部图里长度为 2、长度为 3 的路径计数，再配上一个简单的代数恒等式。
从二部图说起：部分和集
设 \(A\) 与 \(B\) 是具有公共环绕群（common ambient group）的两个加性集合。设 \(G=G(A,B,E)\) 是一张二部图，它的两个颜色类（color classes）分别是 \(A\) 和 \(B\)，边集为 \(E\)（一条边是一对 \((a,b)\)，其中 \(a\in A\)、\(b\in B\)）。回忆部分和集（partial sum set）\(A\overset{G}{+}B\) 的定义：它是所有满足 \(a\in A,\ b\in B\) 且 \((a,b)\in E\) 的和 \(a+b\) 组成的集合。
关键定义：部分和集普通的和集 \(A+B=\{a+b:a\in A,\ b\in B\}\) 把每一对 \(a,b\) 都加起来。而部分和集 \(A\overset{G}{+}B\) 只把有边相连的那些对 \((a,b)\in E\) 加起来：
\[A\overset{G}{+}B=\{\,a+b:\ (a,b)\in E\,\}.\]
图 \(G\) 就是一张“哪些对允许相加”的清单。当 \(E\) 包含全部 \(|A||B|\) 条可能的边时，\(A\overset{G}{+}B\) 退化为普通和集 \(A+B\)。
二部图 \(G(A,B,E)\)：左列是 \(A\) 的点，右列是 \(B\) 的点，连线表示“这一对允许相加”。部分和集只收集连线两端的和。
Balog 与 Szemerédi [16] 证明了：若 \(A\) 与 \(B\) 是两个基数为 \(n\) 的集合，且 \(|E|\ge n^2/K\)，又 \(|A\overset{G}{+}B|\le K'n\)（其中 \(K,K'\) 是某两个常数），则可以找到 \(A'\subset A\) 与 \(B'\subset B\)，使得
\[|A'|,\ |B'|,\ |A'+B'|=\Theta_{K,K'}(n).\]
如所陈述的那样，上述定理只有在 \(K\) 与 \(K'\) 不依赖于 \(n\)（或随 \(n\) 极其缓慢增长）时才有用。Gowers [138] 用一个新证明强化了这一陈述，他证明了 \(\Theta_{K,K'}(\cdot)\) 记号中隐含的常数可以取成 \(K\) 与 \(K'\) 的多项式，从而即便 \(K,K'\) 大到 \(n^\varepsilon\)（\(\varepsilon>0\) 为某个绝对常数）时定理仍然有效；我们已在定理 2.29中陈述过这一结果。这在许多希望得到多项式型界的应用里极有价值，例如 Gowers 对 Szemerédi 定理的证明（尤见 11.3 节）。Gowers 证明里的多项式是隐式的，但沿着他的思路可以推出定理 2.29 中给出的显式版本。我们这里的处理基于 [340]。
为什么“多项式依赖”这么关键
假设 \(K\) 不大，比如 \(K=10\)。两种界的差别是：
- 若隐含常数是 \(K\) 的多项式（如 \(K^4\)），则约为 \(10^4=10000\)，可控。
- 若隐含常数是 \(K\) 的指数（如 \(2^K\)），则约为 \(2^{10}\approx 1000\)，看似也行；但一旦 \(K=n^\varepsilon\) 随 \(n\) 增长，指数型 \(2^{n^\varepsilon}\) 会爆炸，定理彻底失效，而多项式型 \((n^\varepsilon)^4=n^{4\varepsilon}\) 仍是 \(n\) 的小幂次，定理依旧好用。
正是这一点，让 Gowers 版本能嵌进对 Szemerédi 定理的证明里——那里必须允许 \(K\) 随规模缓慢增大。
核心视角：把它看成稠密二部图的命题
事实表明，可以把 Balog–Szemerédi–Gowers 定理看成一个关于稠密二部图的命题。显然，如果二部图 \(G(A,B,E)\) 有很多条边，那么就会有很多对顶点 \(a\in A,\ b\in B\) 被长度为 \(1\) 的路径（即一条边）连接。于是人们会预期：也有很多对 \(a,a'\in A\) 被长度为 \(2\) 的路径连接，并且有很多对 \(a\in A,\ b\in B\) 被长度为 \(3\) 的路径连接。更进一步，随着路径长度的增加，这种连通性会变得越来越“均匀”；可与 4.7 节中关于和集里算术级数的结果作比较。正是这种均匀性对 Balog–Szemerédi–Gowers 定理的证明至关重要。
路径越长，连法越多、分布越均匀。证明的关键正是把“边多”逐级升级为“长度 2 的路径多”，再升级为“长度 3 的路径多”。
我们先把上面关于长度为 \(2\) 和长度为 \(3\) 的路径的原理形式化。下面用 \(N(v)\) 记顶点 \(v\) 的邻域（与 \(v\) 相邻的顶点集合），\(|N(v)|\) 即 \(v\) 的度数。注意：两点 \(a,a'\in A\) 之间长度为 \(2\) 的路径条数，恰好等于它们的公共邻居个数 \(|N(a)\cap N(a')|\)（每个公共邻居 \(b\) 给出一条 \(a-b-a'\)）。
长度为 2 的路径
引理 6.19（长度为 2 的路径）设 \(G(A,B,E)\) 是二部图，满足 \(|E|\ge |A||B|/K\)（某个 \(K\ge 1\)）。则对任意 \(0<\varepsilon<1\)，存在子集 \(A'\subseteq A\)，使得
\[|A'|\ \ge\ \frac{|A|}{\sqrt{2}\,K}\]
并且 \(A'\) 中至少有 \((1-\varepsilon)\) 比例的顶点对 \(a,a'\) 被至少 \(\dfrac{\varepsilon|B|}{2K^2}\) 条长度为 \(2\) 的路径连接。
证明. 若有必要，减小 \(K\) 之后可设 \(|E|=|A||B|/K\)。观察如下组合恒等式
\[\mathbb{E}_{b\in B}\frac{|N(b)|}{|A|}=\mathbb{E}_{a\in A}\frac{|N(a)|}{|B|}=\frac{|E|}{|A||B|}=\frac1K\]
以及
\[\mathbb{E}_{b\in B}\frac{|N(b)|^2}{|A|^2}=\mathbb{E}_{a,a'\in A}\frac{|N(a)\cap N(a')|}{|B|}.\]
对前一式用 Cauchy–Schwarz 不等式（\(\mathbb{E}[X^2]\ge(\mathbb{E}X)^2\)）可得
\[\mathbb{E}_{a,a'\in A}\frac{|N(a)\cap N(a')|}{|B|}=\mathbb{E}_{b\in B}\frac{|N(b)|^2}{|A|^2}\ \ge\ \Big(\mathbb{E}_{b\in B}\frac{|N(b)|}{|A|}\Big)^2=\frac1{K^2}.\tag{$\ast$}\]
设 \(\Omega\) 为所有满足 \(|N(a)\cap N(a')|<\dfrac{\varepsilon|B|}{2K^2}\) 的顶点对 \((a,a')\) 之集合；换句话说，\((a,a')\in\Omega\) 当且仅当 \(a,a'\) 没有被至少 \(\dfrac{\varepsilon|B|}{2K^2}\) 条长度为 \(2\) 的路径连接。显然有
\[\mathbb{E}_{a,a'\in A}\mathbf 1\big((a,a')\in\Omega\big)\frac{|N(a)\cap N(a')|}{|B|}\ <\ \frac{\varepsilon}{2K^2}\]
（因为在 \(\Omega\) 上被加项已小于 \(\varepsilon/(2K^2)\)，而指示函数的均值不超过 \(1\)），从而
\[\mathbb{E}_{a,a'\in A}\Big(1-\frac1\varepsilon\mathbf 1\big((a,a')\in\Omega\big)\Big)\frac{|N(a)\cap N(a')|}{|B|}\ \ge\ \frac1{2K^2}.\]
这里用到 \((\ast)\) 减去 \(\frac1\varepsilon\cdot\frac{\varepsilon}{2K^2}=\frac1{2K^2}\)。左边可重写为
\[\mathbb{E}_{b\in B}\ \frac1{|A|^2}\sum_{a,a'\in N(b)}\Big(1-\frac1\varepsilon\mathbf 1\big((a,a')\in\Omega\big)\Big),\]
于是由鸽巢原理，存在 \(b\in B\) 使得
\[\frac1{|A|^2}\sum_{a,a'\in N(b)}\Big(1-\frac1\varepsilon\mathbf 1\big((a,a')\in\Omega\big)\Big)\ \ge\ \frac1{2K^2}.\]
特别地，由于括号项不超过 \(1\)，把它全部替换为 \(1\) 得 \(|N(b)|^2/|A|^2\ge 1/(2K^2)\)，即 \(|N(b)|\ge\dfrac{|A|}{\sqrt2\,K}\)；又由该式（和式非负）知坏对的占比受控：\(\big|\{a,a'\in N(b):(a,a')\in\Omega\}\big|\le \varepsilon|N(b)|^2\)。于是令 \(A':=N(b)\) 即得结论。♦
把这条证明拆成动机清晰的小步
- 边多 ⇒ 度数平方的平均大。 平均每个点的度数（按 \(|A|\) 归一）是 \(1/K\)。Cauchy–Schwarz 说“平方的平均 ≥ 平均的平方”，于是 \(\mathbb{E}_b|N(b)|^2/|A|^2\ge 1/K^2\)。
- 度数平方 = 公共邻居总量。 关键恒等式把 \(\mathbb{E}_b|N(b)|^2/|A|^2\) 翻译成 \(\mathbb{E}_{a,a'}|N(a)\cap N(a')|/|B|\)。所以“边多”自动意味着“平均每对 \(a,a'\) 的公共邻居（=长度 2 的路径）多”，至少 \(1/K^2\) 这么多（按 \(|B|\) 归一）。
- 扣掉坏对。 把公共邻居太少（\(<\varepsilon|B|/2K^2\)）的对叫“坏对”。坏对贡献很小，扣掉它们后均值仍 \(\ge 1/(2K^2)\)。
- 鸽巢挑一个明星 \(b\)。 既然按 \(b\) 取平均仍大，必有某个 \(b\) 自己就好。它的邻域 \(N(b)\) 既够大（\(\ge|A|/\sqrt2 K\)），其内部又几乎全是好对（坏对占比 \(\le\varepsilon\)）。取 \(A'=N(b)\) 收工。
\(a\) 与 \(a'\) 之间长度为 \(2\) 的路径数，等于它们公共邻居的个数 \(|N(a)\cap N(a')|\)。引理保证大多数对的这个数都很大。
长度为 3 的路径
现在我们对长度为 \(3\) 的路径得到一个类似的结果。
推论 6.20（长度为 3 的路径）设 \(G(A,B,E)\) 是二部图，满足 \(|E|\ge|A||B|/K\)（某个 \(K\ge1\)）。则存在 \(A'\subseteq A,\ B'\subseteq B\)，满足
\[|A'|\ \ge\ \frac{|A|}{4\sqrt2\,K},\qquad |B'|\ \ge\ \frac{|B|}{4K},\]
使得每一个 \(a\in A'\) 与 \(b\in B'\) 都被至少 \(\dfrac{|A||B|}{2^{12}K^4}\) 条长度为 \(3\) 的路径连接。
证明. 在应用引理 6.19 之前，先把图 \(G\) 略作整理是方便的。令 \(\tilde A\) 为 \(A\) 中度数至少为 \(|B|/2K\) 的顶点组成的集合，并令 \(\tilde G=\tilde G(\tilde A,B,\tilde E)\) 为相应的导出子图。由于从 \(G\) 过渡到 \(\tilde G\) 时至多删去 \(|A||B|/2K\) 条边，可见 \(\tilde G\) 至少还有 \(|A||B|/2K\) 条边。把 \(|A|=L|\tilde A|\) 写成某个 \(L\ge1\) 的形式，并对 \(\tilde G\)（把其中的 \(K\) 替换成 \(2K/L\)，并取 \(\varepsilon:=\dfrac1{16K}\)）应用引理 6.19，可以找到 \(A\)（更准确说是 \(\tilde A\)）的一个子集 \(\tilde A'\)，其大小
\[|\tilde A'|\ \ge\ \frac{|\tilde A|}{\sqrt2\,(2K/L)}=\frac{|A|}{2\sqrt2\,K},\]
并且 \(\tilde A'\) 中至少有 \(1-\dfrac1{16K}\) 比例的对 \(a,a'\) 被至少 \(\dfrac{L^2|B|}{128K^3}\) 条长度为 \(2\) 的路径连接。
我们把一对 \((a,a')\in\tilde A'\times\tilde A'\) 称为坏的（bad），如果它们没有被至少 \(\dfrac{L^2|B|}{128K^3}\) 条长度为 \(2\) 的路径连接；于是坏对至多有 \(\dfrac1{16K}|\tilde A'|^2\) 个。令 \(A'\) 为所有满足“至多有 \(\dfrac1{8K}|\tilde A'|\) 个对 \((a,a')\) 是坏的”那些 \(a\in\tilde A'\) 的集合。则由 Markov 不等式 \(|\tilde A'\setminus A'|\le\dfrac{|\tilde A'|}{2}\)，从而
\[|A'|\ \ge\ \frac12|\tilde A'|\ \ge\ \frac{|A|}{4\sqrt2\,K}.\]
构造好 \(A'\) 后，转向 \(B'\)。由于 \(\tilde A\)（从而 \(\tilde A'\)）中每个元素度数都至少 \(|B|/2K\)，故
\[\sum_{b\in B}\big|\{a\in\tilde A':(a,b)\in E\}\big|=\big|\{(a,b)\in E:a\in A'\}\big|\ \ge\ |\tilde A'|\frac{|B|}{2K},\]
于是若令
\[B':=\Big\{b\in B:\ \big|\{a\in\tilde A':(a,b)\in E\}\big|\ \ge\ \frac{|\tilde A'|}{4K}\Big\},\]
则有
\[|\tilde A'|\,|B'|\ \ge\ \sum_{b\in B'}\big|\{a\in\tilde A':(a,b)\in E\}\big|\ \ge\ |\tilde A'|\frac{|B|}{2K}-\frac{|\tilde A'|}{4K}|B|=\frac{|\tilde A'|\,|B|}{4K}.\]
特别地有 \(|B'|\ge|B|/4K\)。
最后，任取 \(a\in A'\) 与 \(b\in B'\)。由 \(B'\) 的构造，\(b\) 与 \(\tilde A'\) 中至少 \(|\tilde A'|/4K\) 个元素 \(a'\) 相邻。由 \(A'\) 的构造，其中至多 \(|\tilde A'|/8K\) 个对 \((a,a')\) 是坏的。因此至少有 \(|\tilde A'|/4K-|\tilde A'|/8K=|\tilde A'|/8K\) 个顶点 \(a'\)，它们同时与 \(b\) 相邻、且与 \(a\) 被至少 \(\dfrac{L^2|B|}{128K^3}\) 条长度为 \(2\) 的路径连接。于是 \(a\) 与 \(b\) 被连接的长度为 \(3\) 的路径条数至少是
\[\frac{|\tilde A'|}{8K}\cdot\frac{L^2|B|}{128K^3}\ \ge\ \frac{|A||B|}{2^{12}K^4}\]
（用到 \(|\tilde A'|\ge|A|/(2\sqrt2\,K)\) 与 \(L\ge1\)）。♦
为什么要先“清理低度数顶点”，又为什么长度 3 = 长度 2 接一条边
- 清理（取 \(\tilde A\)）。 引理只控制“对”的连通性，但还需要每个点的度数有下界，才能在第三步把长度 2 接到 \(b\) 上。所以先扔掉度数 \(<|B|/2K\) 的稀疏点；扔掉的边不多（\(\le|A||B|/2K\)），剩下的图仍稠密。
- 升级到长度 2。 对清理后的图用引理 6.19，得到大子集 \(\tilde A'\)，其中几乎每对 \(a,a'\) 都有很多长度 2 的路径。
- 过滤出“群众基础好”的 \(a\)。 个别 \(a\) 可能坏对太多。只保留坏伙伴少的 \(a\)（这就是 \(A'\)），用 Markov 不等式保证仍剩一半。
- 选出热门 \(b\)（这就是 \(B'\)）。 与 \(\tilde A'\) 相连数量多的 \(b\) 才入选，保证 \(b\) 有足够多 \(a'\) 可借。
- 拼接：长度 3 = （\(a\) 到 \(a'\) 的长度 2）+（\(a'\) 到 \(b\) 的一条边）。 对固定的 \(a\in A',b\in B'\)，先找出既与 \(b\) 相邻、又与 \(a\) 有很多长度-2 路径的“中转点” \(a'\)（数量 \(\ge|\tilde A'|/8K\)）；每个这样的 \(a'\) 把它与 \(a\) 的每条长度-2 路径，接上 \(a'-b\) 这条边，就得一条 \(a-?-a'-b\) 的长度-3 路径。相乘即得下界。
固定 \(a\in A',\,b\in B'\)。中转点 \(a'\) 既与 \(b\) 相邻（红边），又与 \(a\) 有许多长度-2 路径（绿）。两段拼起来就是 \(a\) 到 \(b\) 的长度-3 路径。
导出 Balog–Szemerédi–Gowers 定理（定理 2.29）
我们现在可以由上面的推论导出 Balog–Szemerédi–Gowers 定理，即定理 2.29。
定理 2.29 的证明. 首先注意，可以通过一个人为的技巧来确保 \(A\) 与 \(B\) 不相交：把环绕群 \(\mathbb Z\) 替换成 \(\mathbb Z\times\mathbb Z\)，把 \(A\) 替换成 \(A\times\{0\}\)，把 \(B\) 替换成 \(B\times\{1\}\)。把定理中的集合 \(G\subset A\times B\) 看成 \(A\) 与 \(B\) 上的一张二部图。应用推论 6.20，可以找到 \(A',B'\) 满足 (2.18)、(2.19)，且每一对 \(a\in A',\,b\in B'\) 都被至少 \(|A||B|/2^{12}K^4\) 条长度为 \(3\) 的路径连接：
\[\big|\{(a',b')\in A\times B:\ (a,b'),(a',b'),(a',b)\in G\}\big|\ \ge\ \frac{|A||B|}{2^{12}K^4}.\]
利用显然的恒等式
\[a+b=(a+b')-(a'+b')+(a'+b),\]
并记 \(x:=a+b',\ y:=a'+b',\ z:=a'+b\)，我们得到
\[\Big|\Big\{(x,y,z)\in \big(A\overset{G}{+}B\big)^3:\ x-y+z=a+b\Big\}\Big|\ \ge\ \frac{|A||B|}{2^{12}K^4}.\]
由于三元组 \((x,y,z)\) 的总数至多为
\[\big|A\overset{G}{+}B\big|^3\ \le\ (K')^3|A|^{3/2}|B|^{3/2},\]
我们断定：\(a+b\) 的可能取值总数至多为
\[2^{12}K^4(K')^3|A|^{1/2}|B|^{1/2},\]
结论随之成立。♦
这步“恒等式 + 数表示法”究竟在干什么
目标是：证明 \(A'+B'\)（\(A'\) 与 \(B'\) 之间的全部和）取值很少。困难在于 \(A',B'\) 之间不一定有边，\(a+b\) 不一定在部分和集里。技巧是把 \(a+b\) 拆成三个一定在部分和集里的量：
- 取一条长度-3 路径 \(a-b'-a'-b\)。它的三条边分别给出 \(a+b',\ a'+b',\ a'+b\)，这三个和都在 \(A\overset{G}{+}B\) 里（因为都是边）。
- 代数恒等式 \(a+b=(a+b')-(a'+b')+(a'+b)\) 把目标和 \(a+b\) 表示成 \(x-y+z\)，其中 \(x,y,z\in A\overset{G}{+}B\)。验证：\((a+b')-(a'+b')+(a'+b)=a+b'-a'-b'+a'+b=a+b\)。✓
- 路径多 ⇒ 表示法多。 每条不同的长度-3 路径给出一个 \((x,y,z)\) 表示。路径至少 \(|A||B|/2^{12}K^4\) 条，故 \(a+b\) 至少有这么多种 \(x-y+z\) 表示。
- 抽屉反推取值少。 三元组 \((x,y,z)\) 一共最多 \(|A\overset{G}{+}B|^3\) 个。若每个值 \(a+b\) 都“吃掉” \(\ge|A||B|/2^{12}K^4\) 个三元组，则不同的值最多 \(\dfrac{\text{三元组总数}}{\text{每值最少表示数}}\) 个，于是 \(|A'+B'|\) 被压到很小。
直觉：表示法越多，说明这些和“高度重合”，互不相同的取值就必然少。
把目标和 \(a+b\) 写成三个“合法和”的组合 \(x-y+z\)。每条长度-3 路径给一组 \((x,y,z)\)，路径多则表示多，逼出取值少。
这个“拆群”小技巧（为什么换成 \(\mathbb Z\times\mathbb Z\)）证明需要 \(A,B\) 不相交，否则同一个点可能既算作 \(A\) 的顶点又算作 \(B\) 的顶点，二部图的两侧会混淆。办法：把每个 \(a\in A\) 标成第二坐标 \(0\)（写作 \((a,0)\)），每个 \(b\in B\) 标成第二坐标 \(1\)（写作 \((b,1)\)）。由于第二坐标不同，\(A\times\{0\}\) 与 \(B\times\{1\}\) 必然不相交，而加法 \((a,0)+(b,1)=(a+b,1)\) 中第一坐标仍是原来的 \(a+b\)，第二坐标恒为 \(1\)，不影响任何和集大小。纯粹是记账技巧，不改变结论。
注意，在这个证明中群是交换的并非关键。对于乘法群，我们可以把 \(a+b=(a+b')-(a'+b')+(a'+b)\) 替换为
\[ab=(ab')(a'b')^{-1}(a'b),\]
其余证明完全相同。
推广：超图版本
作为本节的结束，让我们提一下 Balog–Szemerédi–Gowers 结果对超图（hypergraphs）的一个推广。设 \(A_1,\dots,A_k\) 是具有公共环绕群的加性集合（用上面的技巧可设它们两两不相交），并设 \(E\) 是某族有序 \(k\)-元组 \((a_1,\dots,a_k)\)，满足 \(a_i\in A_i,\ 1\le i\le k\)。集合 \(A_1,\dots,A_k\) 连同 \(E\) 一起，称为一个 \(k\)-一致 \(k\)-部超图（\(k\)-uniform \(k\)-partite hypergraph），记作 \(H\)；此时 \(E\) 称为 \(H\) 的边集（注意，二部图正是 \(k=2\) 的特例）。我们用 \(H\sum_{i=1}^k A_i\) 记所有满足 \((a_1,\dots,a_k)\in E\) 的和 \(a_1+\cdots+a_k\) 组成的集合。当 \(k=2\) 时，我们谈论的就是二部图。
定理 6.21 [340]设 \(k\ge1\)，\(n,K\) 为正数。若 \(A_1,\dots,A_k\) 是群 \(Z\) 中基数至多为 \(n\) 的加性集合，\(H(A_1,\dots,A_k,E)\) 是边数至少为 \(n^k/K\)、且满足 \(\big|H\sum_{i=1}^k A_i\big|\le Kn\) 的 \(k\)-部 \(k\)-一致超图，则可以找到子集 \(A_i'\subset A_i\)，使得
- \(|A_i'|=\Theta\big(n/K^{O_k(1)}\big)\) 对所有 \(1\le i\le k\) 成立；
- \(|A_1'+\cdots+A_k'|=\Theta\big(K^{O_k(1)}n\big)\)。
证明的核心是下面的断言。
断言 6.22设 \(A_1,\dots,A_k\) 与 \(n,K\) 如上面的定理所述。令 \(X=H\sum_{i=1}^k A_i\)。则存在基数至少为 \(\Theta_k\big(n/K^{O_k(1)}\big)\) 的子集 \(A_i'\subset A_i,\ i=1,\dots,k\)，以及基数至多为 \(O_k\big(K^{O_k(1)}n\big)\) 的集合 \(Y_j\subseteq Z,\ 1\le j\le 2k-2\)，使得 \(A_1'+\cdots+A_k'\) 中每个元素都能写成
\[x+\sum_{j=1}^{2k-2}y_j,\qquad x\in X,\ y_j\in Y_j,\]
的形式，且写法至少有 \(\Theta_k\big(n^{2k-2}/K^{O_k(1)}\big)\) 种。
由这个断言推出定理 6.21 是容易的。对断言中的集合 \(A_1,\dots,A_k\)，我们有
\[|A_1'+\cdots+A_k'|\ \le\ \frac{|X|\prod_{j=1}^{2k-2}|Y_j|}{\Theta_k\big(n^{2k-2}/K^{O_k(1)}\big)}\ =\ \Theta_k\big(K^{O_k(1)}n\big),\]
正如所欲。断言 6.22 的证明留作习题。
超图版本是怎样“复用”二部图思路的
\(k=2\) 时，\(2k-2=2\)，恰好对应前面证明里出现的两个“修正项”——也就是 \(a+b=x-(a'+b')+(a'+b)\) 里需要补上的 \(y_1,y_2\) 型项。一般的 \(k\)，把目标和 \(a_1+\cdots+a_k\) 表示成“一个合法和 \(x\in X\)，再加上 \(2k-2\) 个来自小集合 \(Y_j\) 的修正项”，并保证表示法极多。计数原理（取值数 ≤ 总组合数 ÷ 每值最少表示数）于是把和集压小。这正是二部图证明逐步推演的高维翻版。
习题
习题 6.4.1设 \(G=G(A,B,E)\) 是二部图，满足 \(|E|\ge|A||B|/K\)。证明：存在 \(A\) 的子集 \(A'\)，其基数 \(|A'|\ge|A|/K\)，使得 \(A'\) 中任意两个元素都被至少一条长度为 \(2\) 的路径连接。证明：即便 \(A,B,K\) 都很大，\(|A|/K\) 也不能改进为 \(|A|/K+1\)。
习题 6.4.2 [210]设 \(d\) 为大整数。令 \(V=\{0,1\}^d\) 为 \(d\) 维离散立方体，并令 \(G=G(V,E)\) 为如下二部图：在 \(x,y\in V\) 之间连一条边，当且仅当 \(x\) 与 \(y\) 至多在 \(d/2\) 个坐标上不同（即 \(x,y\) 的 Hamming 距离至多为 \(d/2\)）。证明：\(|E|=\big(\tfrac14+o_{d\to\infty}(1)\big)|V|^2\)，但若 \(V'\) 是 \(V\) 中任一基数 \(|V'|\ge c|V|\) 的子集，则存在 \(x,x'\in V'\)，它们在 \(G\) 中被少于 \(o_{d\to\infty}(|V|)\) 条长度为 \(2\) 的路径连接。（提示：用体积装填论证，找到 \(V'\) 中两个几乎对径的点 \(x,x'\)，即它们的 Hamming 距离为 \(d-O(1)\)。）把这个例子改造成二部图的例子，说明即便允许 \(\varepsilon\) 充分小（依赖于 \(K\)），也不能指望去掉引理 6.19 中的 \((1-\varepsilon)\) 因子。
习题 6.4.3（Benny Sudakov，私人通信）设 \(G=G(A,B,E)\) 是二部图，\(|A|=|B|=N\)，\(|E|=\Theta(N^2)\)，其中 \(N\) 充分大。证明：\(G\) 含有一个每个颜色类各有 \(\Theta(\log N)\) 个顶点的完全二部图。证明界 \(\Theta(\log N)\) 是最优的。
习题 6.4.4设 \(Z\) 为有限加法群 \(Z=\mathbb Z_2^d\)（某整数 \(d\)），并设 \(\hat Z\) 为其 Pontryagin 对偶。令 \(G=G(Z,\hat Z,E)\) 为如下二部图：当 \(\chi(x)=0\) 时把 \(x\in Z\) 与 \(\chi\in\hat Z\) 相连。证明 \(|E|=|A||B|/2\)。利用 (4.2)，证明：当 \(A\subseteq Z,\ B\subseteq\hat Z\) 是 \(G\) 中的二部团时，必有 \(|A||B|\le|Z|\)。反之，每当 \(N_1,N_2\) 是满足 \(N_1N_2=|Z|\) 的正整数时，证明 \(G\) 中存在一个二部团 \(A\subseteq Z,\ B\subseteq\hat Z\)，满足 \(|A|=N_1,\ |B|=N_2\)。把这一结果与习题 6.4.3 作比较。
习题 6.4.5（二进抽屉原理）设 \(G=G(A,B,E)\) 是二部图，满足 \(|E|\ge|A||B|/K\)（某 \(K\ge1\)）。证明：存在某个 \(1\le K'\le K\) 以及 \(G(A,B,E)\) 的某个导出子图 \(G'=G(A',B,E')\)，满足
\[|E|/(C+C\log K)\le|E'|\le|E|,\qquad |A|/(C+C\log K)\le|A'|\le|A|,\]
使得对所有 \(a\in A'\) 有 \(|B|/2K'\le\deg_{G'}(a)\le|B|/K'\)。
习题 6.4.6（同时流行原理）设 \(G=G(A,B,E)\) 是二部图，满足 \(|E|\ge|A||B|/K\)（某 \(K\ge1\)）。证明：存在导出子图 \(G'=G(A',B',E')\)，满足下列界
\[|A'|\,|B'|\ \ge\ |E'|\ \ge\ \frac{|A||B|}{2K^2},\qquad |A'|\ \ge\ \frac{|A|}{K^2},\qquad |B'|\ \ge\ \frac{|B|}{K^2}.\]
返回 全书目录