Tao–Vu · 加性组合学 · 第 10 章 k=3 的 Szemerédi 定理

10.6　Szemerédi 正则性引理The Szemerédi regularity lemma

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步把直觉与每一步动机讲清楚，不用比喻。

本节目标本节要把一条贯穿整个离散数学的核心工具——Szemerédi 正则性引理——讲清楚：任何一张稠密的大图，都可以被切成不太多的小块，使得绝大多数“块与块之间”的连边看起来像随机连的。然后我们用它，绕开傅里叶分析，给出 Roth 定理（不含三项等差数列的集合必然稀疏）的一个全新的、图论味道的证明。一路上的关键词是：边密度、\(\varepsilon\)-正则、诱导匹配、三角形移除。

在 Szemerédi 定理（定理 10.1）的原始证明中，Szemerédi 引入了图论中的一个重要结果，即 Szemerédi 正则性引理。此后，这条引理已成为离散数学的主要工具之一。粗略地说，它断言：任何稠密的大图都可以被分解为相对少量的若干个不相交的子结构，其中大多数部分的行为类似于随机图（pseudo-random，伪随机）。从更具“遍历论”色彩的角度看，这条引理可以理解为：一张图的示性函数可以被分解为一个“低复杂度”的部分与一个“伪随机”的部分。

为陈述这条引理，我们需要一些记号。

边密度与 \(\varepsilon\)-正则

定义 10.41（\(\varepsilon\)-正则性）设 \(G(V,E)\) 是一张图。若 \(X,Y\) 是 \(V\) 的两个不相交、非空的子集，我们定义 \(X\) 与 \(Y\) 之间的边密度（edge density）\(d(X,Y)\) 为 \[ d(X,Y) := \mathbb{P}_{x\in X,\,y\in Y}\big(\{x,y\}\in E\big). \] 若 \(\varepsilon>0\)，我们称数对 \((X,Y)\) 是 \(\varepsilon\)-正则的（\(\varepsilon\)-regular），如果只要 \(X'\subseteq X,\ Y'\subseteq Y\) 满足 \(|X'|\ge \varepsilon|X|\) 且 \(|Y'|\ge \varepsilon|Y|\)，就有 \[ \big|\,d(X',Y')-d(X,Y)\,\big|\le \varepsilon. \] 一个划分 \(V=V_1\cup V_2\cup\cdots\cup V_k\) 称为近乎均匀的（near-uniform），如果 \(-1\le |V_i|-|V_j|\le 1\)（即各块大小至多相差 \(1\)）。
把定义读懂边密度 \(d(X,Y)\) 就是：在 \(X\) 里随便挑一个点 \(x\)、在 \(Y\) 里随便挑一个点 \(y\)，它们之间恰好有边相连的概率。换成计数就是 \[ d(X,Y)=\frac{\#\{(x,y):x\in X,\,y\in Y,\,\{x,y\}\in E\}}{|X|\,|Y|}, \] 即“真实存在的跨边数”除以“可能存在的跨边数 \(|X||Y|\)”，是介于 \(0\) 和 \(1\) 之间的一个比例。

\(\varepsilon\)-正则是在说一件更强的事：不只整体密度是某个值 \(d\)，而且你放大去看任何一块够大的子区域（\(X'\) 至少占 \(X\) 的 \(\varepsilon\) 比例，\(Y'\) 至少占 \(Y\) 的 \(\varepsilon\) 比例），密度都还是几乎那个 \(d\)（误差不超过 \(\varepsilon\)）。这正是“随机连边”的特征：随机图里，无论你盯住哪一小片看，连边比例都差不多。反过来，若有某个角落特别密、某个角落特别稀，那它就不正则。

X Y X'（≥ε|X|） Y'（≥ε|Y|）
边密度 \(d(X,Y)\) = 实线条数 ÷ \(|X||Y|\)。\(\varepsilon\)-正则要求：哪怕只盯住虚线框里的子集 \(X',Y'\)（够大），它们之间的密度 \(d(X',Y')\) 也与整体 \(d(X,Y)\) 相差不超过 \(\varepsilon\)。

Szemerédi 正则性引理断言：给定一个正常数 \(\varepsilon\) 和一张图 \(G\)，总能找到 \(V\) 的一个块数不太多的近乎均匀划分，使得其中大多数数对 \((V_i,V_j)\) 都是 \(\varepsilon\)-正则的。

引理 10.42（正则性引理）设 \(\varepsilon\) 为一个正常数，\(m\ge 1\) 为一个整数，\(G=G(V,E)\) 为一张图。若 \(|V|\) 充分大（依赖于 \(\varepsilon\) 与 \(m\)），则存在一个近乎均匀的划分 \(V=V_1\cup\cdots\cup V_k\)，其块数满足 \(m\le k\le O_{\varepsilon,m}(1)\)，使得在所有 \(\binom{k}{2}\) 个（乃至 \(k^2\) 个）数对 \((V_i,V_j)\) 中，至多只有 \(\varepsilon k^2\) 个不是 \(\varepsilon\)-正则的。
引理在说什么把这句话拆成三件保证：
① 块数可控。 划分的块数 \(k\) 只依赖于 \(\varepsilon\) 和 \(m\)，与图有多大无关——哪怕 \(V\) 有十亿个点，块数 \(k\) 仍是一个固定常数。
② 块大小齐整。 各块大小几乎相等（至多差 \(1\)），都约为 \(\tfrac{1}{k}|V|\)。
③ 绝大多数块对正则。 在 \(k^2\) 对块里，“坏的”（非正则）对不超过 \(\varepsilon k^2\)，所以好的占了 \((1-\varepsilon)\) 这么大的比例。
直观结论：任何稠密大图，从“块与块之间”这个粗粒度看上去，几乎处处像随机图。这就是它强大的原因——它把杂乱无章的图，整理成了有限多个“近乎随机”的二部图拼起来的样子。

注记 10.43正则性引理并不断言所有数对 \((V_i,V_j)\) 都是正则的，只断言其中有 \((1-\varepsilon)\) 比例的数对是正则的。事实上，有例子表明：人们不能指望所有数对都正则（见习题 10.6.5）。
注记 10.44本定理要求 \(|V|\) 充分大（依赖于 \(\varepsilon\) 与 \(m\)）；换个说法，我们需要 \(\varepsilon=o_{|V|\to\infty;\,m}(1)\)。正则性引理的证明允许取 \[ \varepsilon=O_m\!\left(\frac{1}{(\log_* |V|)^{1/5}}\right), \] 其中 \(\log_*\) 是塔式指数 \(n\mapsto e\!\uparrow\!\uparrow\! n\) 的反函数；塔式指数由递归 \(e\!\uparrow\!\uparrow\!1=e\) 与 \(e\!\uparrow\!\uparrow\!(n+1):=\exp(e\!\uparrow\!\uparrow\! n)\) 定义。颇为惊人的是，Gowers 证明了这个界本质上是紧的：对任意充分大的 \(|V|\)，都存在某些图，其上找不到任何参数 \(\varepsilon\) 大于 \(\varepsilon=\Omega\!\left(\dfrac{1}{\log_* |V|}\right)\) 的 \(\varepsilon\)-正则划分。
\(\log_*\) 有多大？为什么这界这么差塔式指数长这样：\(e\!\uparrow\!\uparrow\!1=e\approx 2.7\)，\(e\!\uparrow\!\uparrow\!2=e^{e}\approx 15\)，\(e\!\uparrow\!\uparrow\!3=e^{15}\approx 3{\times}10^6\)，\(e\!\uparrow\!\uparrow\!4=e^{3\times10^6}\) 已是天文数字……它暴涨。它的反函数 \(\log_* N\)（要把 \(N\) 反复取对数多少次才降到 \(1\)）因此涨得极慢：对人类能写下的几乎所有 \(N\)，\(\log_* N\) 都只是 \(4\) 或 \(5\)。
所以 \(\varepsilon\) 随 \(|V|\) 趋于 \(0\) 的速度慢得可怕——这意味着用正则性引理得到的定量结论，误差衰减极其缓慢。这正是本节末尾要讨论的“界很差”问题的根源。

正则性引理的证明可在多本图论教科书中找到；在 11.6 节中，我们将用与上一节类似的“遍历论”技巧给出此引理的一个证明。关于这条引理的信息论视角参见 [359]，分析学视角参见 [239]。综述文章 [208] 收录了正则性引理的大量应用。在本节中，我们仅限于讨论它在加性组合学中的少数几个应用，尤其是对 Roth 定理的应用。

诱导匹配与一条图论命题

为通过正则性引理证明 Roth 定理，先证明一些图论结果会比较方便。设 \(G=G(V,E)\) 为一张图。\(E\) 中的一组边 \(\{e_1,\dots,e_k\}\) 若两两不相交（没有公共端点），就称为一个匹配（matching）。一个匹配称为诱导的（induced），如果由这些边的端点张成的子图，除了匹配本身已有的那些边之外，不含任何其它的边。

诱导匹配（合法） 端点之间没有额外的边 非诱导（有额外边） 虚线这条额外边破坏了“诱导”
匹配 = 一组两两不共端点的边。诱导匹配 = 这些端点之间再无其它边。右图多出一条跨边（虚线），故非诱导。
命题 10.45 [304]设 \(G=G(V,E)\) 是一张图，其边集是 \(|V|\) 个诱导匹配的并。则 \(|E|=o_{|V|\to\infty}(|V|^2)\)。
命题在说什么“边集是 \(|V|\) 个诱导匹配的并”是一条很强的结构假设：你能把所有边分成 \(|V|\) 组，每组都是一个诱导匹配。命题说，在这种结构下，图不可能太稠密——边数远小于 \(|V|^2\)（即“可能边数”的一个固定比例）。换句话说，诱导匹配这种“稀疏又干净”的结构，多到 \(|V|\) 个并起来，仍撑不出稠密图。证明的策略是：用正则性引理把图整理成近乎随机的块对，再加上一个直觉事实——一个稠密的、\(\varepsilon\)-正则的二部图，里头容不下大的诱导匹配（因为随机连边的地方，端点间总会冒出额外的边）。

证明. 策略是运用正则性引理，并结合下述直观事实：一个稠密的 \(\varepsilon\)-正则图无法承载任何大的诱导匹配。

假设命题不成立。那么我们能找到一个整数 \(m\ge 1\)，以及任意大的图 \(G(V,E)\)，满足 \(|E|\ge \dfrac{6}{m}|V|^2\)（不妨这样设），且每张这样的图 \(G\) 都是 \(|V|\) 个诱导匹配的并。

固定其中一张大图。对它运用正则性引理（取 \(\varepsilon:=\dfrac1m\)），得到一个划分 \(V=V_1\cup\cdots\cup V_k\)，其中 \(m\le k\le O_m(1)\)，对所有 \(i\) 有 \(|V_i|=\dfrac1k|V|+O(1)\)，并且在所有数对 \((V_i,V_j)\) 中，除至多 \(\dfrac1m k^2\) 个之外，其余都是 \(\dfrac1m\)-正则的。

称 \(G\) 的一条边 \(e\) 为坏边，如果下述三种情形之一发生：

不难验证，坏边的总数至多为 \[ (1+o_{|V|\to\infty;\,m}(1))\left[\,k\binom{|V|/k+O(1)}{2}+\frac2m\binom{k}{2}\left(\frac{|V|}{k}\right)^2+\frac1m k^2\left(\frac{|V|}{k}\right)^2\right]\le \frac3m|V|^2, \] 只要 \(V\) 充分大（依赖于 \(m\)）。于是，若令 \(E'\subset E\) 为 \(E\) 中所有非坏的边，则仍有 \(|E'|\ge \dfrac3m|V|^2\)。

由鸽巢原理，我们因此能找到 \(G\) 的一个诱导匹配 \(F\)，它包含 \(E'\) 中至少 \(\dfrac3m|V|\) 条边。

称一个集合 \(V_i\) 为贫乏的（poor），如果它包含来自 \(F\) 的顶点至多 \(\dfrac2m|V_i|\) 个。若我们把所有贫乏的 \(V_i\)（连同它们关联的边）从 \(F\) 中删去，则总共至多删去 \(\dfrac2m|V|\) 条边。于是，剩下的匹配 \(F\) 中仍将含有一条来自 \(E'\) 的边。按定义，这条边连接两个不同的、非贫乏的集合 \(V_i,V_j\)，它们的边密度至少为 \(\dfrac2m\)，且 \((V_i,V_j)\) 是 \(\dfrac1m\)-正则的。若记 \(V_{i,F}\) 与 \(V_{j,F}\) 分别为 \(V_i,V_j\) 中来自 \(F\) 的顶点，则我们得到 \[ d(V_{i,F},V_{j,F})\ \ge\ d(V_i,V_j)-\frac1m\ \ge\ \frac1m. \]

一方面，由于 \(F\) 是诱导匹配，\(V_{i,F}\) 与 \(V_{j,F}\) 之间的边数不可能超过 \(|V_{i,F}|\)，因而其边密度不可能超过 \(1/|V_{j,F}|\)。我们得出 \[ |V_{j,F}|\le m. \] 另一方面，由于 \(V_j\) 非贫乏，有 \(|V_{j,F}|\ge \dfrac2m|V_j|\)，而 \(|V_j|=\dfrac1k|V|+O(1)\)。综合得 \(|V|=O_{m,k}(1)=O_m(1)\)，这与“\(V\) 可以依赖 \(m\) 任意大”的假设矛盾。命题得证。♦

把证明的逻辑骨架捋一遍
  1. 反证开局。 假设命题假，则有稠密图（边数 \(\ge \frac6m|V|^2\)）却由 \(|V|\) 个诱导匹配拼成，且 \(|V|\) 可任意大。
  2. 正则化。 用正则性引理（\(\varepsilon=\frac1m\)）把 \(V\) 切成 \(k\) 个齐整的块，绝大多数块对正则。
  3. 扔掉坏边。 三类坏边（块内边、低密度块对的边、非正则块对的边）加起来不超过 \(\frac3m|V|^2\)，所以好边 \(E'\) 还剩 \(\ge\frac3m|V|^2\) 条。
  4. 鸽巢取一个大匹配。 好边分散在 \(|V|\) 个诱导匹配里，必有一个匹配 \(F\) 含 \(\ge\frac3m|V|\) 条好边。
  5. 修剪贫乏块。 删掉“在 \(F\) 中点很少”的块后，\(F\) 里仍剩好边——它落在一对“密度高、又正则”的块 \((V_i,V_j)\) 之间。
  6. 挤出矛盾。 正则 + 高密度 \(\Rightarrow\) 两块在 \(F\) 中的顶点之间密度 \(\ge\frac1m\)；但诱导匹配 \(\Rightarrow\) 密度 \(\le 1/|V_{j,F}|\)。两边一夹，逼出 \(|V_{j,F}|\le m\)，进而 \(|V|\) 被一个只依赖 \(m\) 的常数卡住——与“\(|V|\) 任意大”矛盾。

核心张力：“正则又稠密”要求处处都有不少边，而“诱导匹配”却要求端点之间再无额外边——这两者势不两立，除非图本身很小。

上述定理有若干等价的表述形式，见习题。该定理的一个略强版本如下。

引理 10.46（三角形移除引理）[304]设 \(G=G(V,E)\) 是一张图，它至多包含 \(\delta|V|^3\) 个三角形。则可以从 \(G\) 中移除 \(o_{\delta\to 0}(|V|^2)\) 条边，得到一张无三角形的图（即完全不含任何三角形）。

引理 10.46 可用证明命题 10.45 时所用的同一方法来证明，留作习题。事实上，由引理 10.46 也可以轻松推出命题 10.45。

三角形移除引理的直觉它说的是一种“全或无”的现象：如果一张图的三角形很少（只有 \(\delta|V|^3\) 个，相对于可能的 \(\sim|V|^3\) 个三元组而言占比 \(\delta\) 很小），那么这些三角形一定“脆弱”到——只要删掉极少量（\(o(|V|^2)\) 条）边，就能把它们全部消灭干净。换言之，“几乎无三角形”可以升级为“真正无三角形”，代价很小。这条看似纯图论的引理，下面会摇身一变成为 Roth 定理的引擎。

用命题 10.45 重证 Roth 定理

现在我们用命题 10.45 给出 Roth 定理（定理 10.8）的另一个证明。

证明. 固定一个奇数阶的有限加法群 \(Z\)，以及 \(Z\) 的一个不含等差数列的子集 \(A\)。只需证明 \(|A|=o_{|Z|\to\infty}(|Z|)\) 即可。

我们如下定义一张二部图 \(G\)：两个色类分别取为集合 \(Z\times\{1\}\) 与 \(Z\times\{2\}\)。对每个 \(a\in Z\) 与每个 \(r\in A\)，我们在 \((a+r,1)\) 与 \((a+2r,2)\) 之间画一条边。对每个固定的 \(a\in Z\)，由所有 \(r\in A\) 给出的边 \((a+r,1)\!-\!(a+2r,2)\) 构成一个匹配。

我们断言这个匹配是诱导的。因为，若还存在另一条边，连接 \((a+r,1)\) 与 \((a+2s,2)\)，其中 \(r,s\in A\) 且 \(r\neq s\)，那么按照构造方式，必有 \(2s-r\in A\)。但这样一来，\(r,\ s,\ 2s-r\) 就构成了 \(A\) 中一个真正的、长度为 \(3\) 的等差数列，矛盾。因此 \(G\) 是 \(|Z|\) 个诱导匹配的并，从而其边数至多为 \(o_{|Z|\to\infty}(|Z|^2)\)。而 \(G\) 中的边数显然是 \(|A|\,|Z|\)，结论随之得证。♦

逐步看清“为什么 \(r,s,2s-r\) 是等差数列”
  1. 第 \(a\) 组匹配里的边长这样：左端 \((a+r,1)\)、右端 \((a+2r,2)\)，其中 \(r\in A\)。所以一条边的“左标减一倍、右标减两倍”应当对得上同一个 \(a\)。
  2. 设想有条“捣乱”的边：左端仍是 \((a+r,1)\)，右端却是另一个 \((a+2s,2)\)（来自 \(s\in A\)，\(s\neq r\)）。它要算一条合法的边，必须属于某一组，比如第 \(a'\) 组：即存在 \(r'\in A\) 使 \(a'+r'=a+r\) 且 \(a'+2r'=a+2s\)。
  3. 两式相减：\(r'=(a+2s)-(a+r)=2s-r\)。于是 \(2s-r=r'\in A\)。
  4. 现在看 \(r,\ s,\ 2s-r\) 三个数：相邻差都是 \(s-r\)（因为 \(s-r=s-r\)，\((2s-r)-s=s-r\)）。这正是公差为 \(s-r\neq 0\) 的三项等差数列，且三项都在 \(A\) 里。
  5. 但 \(A\) 不含三项等差数列——矛盾！所以“捣乱的边”根本不存在，每组匹配确为诱导匹配。

最后一步代数到结论：图有 \(|Z|\) 个诱导匹配，由命题 10.45，边数 \(=|A||Z|=o(|Z|^2)\)，两边除以 \(|Z|\) 即得 \(|A|=o(|Z|)\)，也就是说不含三项等差数列的集合必稀疏。

色类 Z×{1} 色类 Z×{2} a+r₁ a+r₂ a+r₃ a+2r₁ a+2r₂ a+2r₃ 第 a 组（同一个 a，r 跑遍 A）：水平连边构成一个诱导匹配
对固定的 \(a\)，把每个 \(r\in A\) 对应到一条边 \((a+r,1)\!-\!(a+2r,2)\)。若两组边在某顶点处“串台”，便逼出 \(A\) 中的三项等差数列；无此数列 \(\Rightarrow\) 每组皆为诱导匹配，共 \(|Z|\) 组。

更强的命题与定量问题

事实上，上述方法给出了 Roth 定理的如下更强形式。

命题 10.47 [3]设 \(Z\) 为一个有限加法群，\(A\subset Z\times Z\) 满足：\(A\) 不含任何“直角三角形”，即不含形如 \((a,b),\ (a,b+r),\ (a+r,b)\) 的三点组，其中 \(a,b,r\in Z\) 且 \(r\neq 0\)。则 \(|A|=o_{|Z|\to\infty}(|Z|^2)\)。

我们把命题 10.47 的证明（及其与 Roth 定理的联系）留作习题。

(a,b) (a,b+r) (a+r,b)
“直角三角形”：一个顶点 \((a,b)\)，向上挪 \(r\) 得 \((a,b+r)\)，向右挪 \(r\) 得 \((a+r,b)\)，直角恰在 \((a,b)\)。命题 10.47 说不含这种构型的集合 \(A\subset Z\times Z\) 必稀疏。

为上述各结果中的 \(o(\,)\) 项获得更定量的界，是颇有意义的。通过使用正则性引理的一个显式定量版本，可以把命题 10.45 中的 \(o_{|V|\to\infty}(|V|^2)\) 加强为 \(O\!\left(|V|^2/(\log_* |V|)^{1/5}\right)\)，对引理 10.46、Roth 定理以及命题 10.47 也类似。因此，这一方法所达到的定量界，与傅里叶方法所达到的界相比，逊色不少。（不过，图论方法稍微更易推广到一般 \(k\) 的情形；见下一章。）鉴于 Roth 定理（用傅里叶方法）的界明显优于正则性引理所能给出的界，人们自然被引向如下问题。

问题 10.48 [139]在不使用正则性引理的前提下，证明命题 10.45（或引理 10.46）。并找到一个更好的定量界。

就命题 10.47 而言，关于该问题已有一些近期进展 [381], [314]。特别地，目前已知最好的界为 \[ |A|=O\!\left(\frac{|Z|^2}{\log\log|Z|}\right), \] 归功于 Shkredov [314]。

为什么大家在意“界更好”正则性引理的威力在于普适——对任何稠密图都管用；但代价是它内部用到塔式指数级的精度（回忆注记 10.44 的 \(\log_*\)），所以推出的衰减速度慢得惊人。而傅里叶方法（本章前几节）针对 Roth 定理量身定制，能给出指数级好得多的界。问题 10.48 想知道：命题 10.45 / 三角形移除引理这类结论，是否本质上必须依赖正则性引理那套昂贵机器，还是有更“便宜”的证明能带来更好的定量界。这是加性组合学里一条活跃的研究主线。

习题

习题
  1. 10.6.1 [304]　证明命题 10.45 等价于下述命题：设 \(G(V,E)\) 是一张图，使得每条边至多含于一个三角形。则 \(|E|=o_{|V|\to\infty}(|V|^2)\)。
  2. 10.6.2（\((6,3)\)-定理）[304]　证明命题 10.45 等价于下述命题：设 \(G=G(V,E)\) 是一个 \(3\)-一致超图（即 \(E\) 中每条“边”都是 \(V\) 中三个顶点构成的集合 \(\{x,y,z\}\)），使得 \(V\) 中不存在任何六个顶点同时含有 \(E\) 中三条或更多的边。则 \(|E|=o_{|V|\to\infty}(|V|^2)\)。
  3. 10.6.3 [304]　证明引理 10.46 蕴含命题 10.45。（提示：先化归到“二部图是诱导匹配之并”的情形。向图中添加 \(|V|\) 个新顶点，每个诱导匹配对应一个，把每个新顶点连向该诱导匹配中的所有顶点。这便造出一个三部图，它含的三角形相当少，但要使其无三角形却需移除很多边。）
  4. 10.6.4 [304]　用正则性引理证明引理 10.46。
  5. 10.6.5 [8]　设 \(V_1=\{v_1,\dots,v_n\}\)，\(V_2=\{w_1,\dots,w_n\}\) 是两组不相交的顶点，令 \(V:=V_1\cup V_2\)，并设 \(G=G(V_1,V_2,E)\) 是由所有满足 \(i\le j\) 的边 \(\{v_i,w_j\}\) 构成的二部图。用它说明：即使对非常简单的图，人们也必须容许存在一个非正则的例外数对 \((V_i,V_j)\) 集合。
  6. 10.6.6　通过修改 Roth 定理的证明，用命题 10.45 证明命题 10.47。
  7. 10.6.7 [323]　用引理 10.46 证明命题 10.47，而不经过命题 10.45。（提示：考虑这样一张图，其顶点是 \(Z^2\) 中的竖直线 \(\{(a,b):a=\text{常数}\}\)、水平线 \(\{(a,b):b=\text{常数}\}\) 与对角线 \(\{(a,b):a+b=\text{常数}\}\)；两个顶点之间连边当且仅当它们对应的两条线方向不同，且交于 \(A\) 中的某一点。）
  8. 10.6.8　证明命题 10.47 蕴含 Roth 定理。（提示：若 \(A\subseteq Z\)，考虑形如 \(\{(a,b)\in Z\times Z:a+2b\in A\}\) 的集合。）
  9. 10.6.9 [136]　设 \(V_1,V_2\) 是两个不相交的有限集，\(f_1:V_1\to\{-1,+1\}\) 与 \(f_2:V_2\to\{-1,+1\}\) 是两个函数。设 \(G=G(V_1,V_2,E)\) 是这样构造的二部图：在 \(x_1\in V_1\) 与 \(x_2\in V_2\) 之间连边，当且仅当 \(f_1(x_1)=f_2(x_2)\)。设 \(X_1\subset V_1\) 与 \(X_2\subset V_2\) 非空，且 \(0<\varepsilon<1\)。证明：若 \((X_1,X_2)\) 是 \(\varepsilon\)-正则的，则 \[ \big|\mathbb{E}_{x_1\in X_1}f_1(x_1)\big|,\ \big|\mathbb{E}_{x_2\in X_2}f_2(x_2)\big|\ \ge\ 1-O(\varepsilon). \] 这表明：任何把 \(V_1,V_2\) 划分为正则数对的划分，本质上必须是集合 \(\{x_1\in V_1:f_1(x_1)=\pm1\}\) 与 \(\{x_2\in V_2:f_2(x_2)=\pm1\}\) 的一个加细。
  10. 10.6.10 [136]　设 \(V\) 是一个大的有限集。证明：存在 \(n\) 个函数 \(f_1,\dots,f_n:V\to\{-1,+1\}\)，其中 \(n=\Omega(\log|V|)\)，具有如下性质……（原文此处接续到下一页，性质内容未在本节摘录中完整给出。）

返回 全书目录