Tao–Vu · 加性组合学 · 第 6 章 图论方法

6.2　独立集、无和子集与 Sidon 集Independent sets, sum-free subsets, and Sidon sets

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 定义 / 定理 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。本节出现的 \(\log\) 一律指自然对数 \(\ln\)（因为它来自调和级数 \(1+\tfrac12+\dots+\tfrac1n\approx\ln n\)）。

本节目标把一个加性集合（一堆数）里“互相之间不会相加得到集合里别的数”的大子集找出来。核心工具是把“相加关系”翻译成一张图：两个数若相加落回集合内就连一条边；这样“无和子集”就变成图里的独立集（互不相连的点集）。于是只要证明“度数小的图必有大独立集”（Turán 定理），就能保证每个集合都有较大的无和子集。本节再讨论这种子集到底能多大、又最大不过多大（上下界）。

直觉上，人们预期度数较小的图拥有较大的独立集。下面这条由 Turán 给出的定理，把这一直觉量化了。

定理 6.1（Turán 定理）设 \(G=G(V,E)\) 是一个有 \(n\) 个顶点的图。则 \(G\) 含有一个大小至少为 \[\sum_{v\in V}\frac{1}{\deg(v)+1}\] 的独立集。特别地，若 \(G\) 的最大度为 \(d\)，则 \(G\) 有一个大小至少为 \(n/(d+1)\) 的独立集。

这里“独立集”指顶点的一个子集 \(S\)，使得 \(S\) 中任意两点之间都没有边相连。最大度 \(d\) 是指所有顶点中邻居最多的那个的邻居数。

证明. 我们将使用概率方法，更确切地说是一阶矩方法（first moment method）。设 \(\pi:V\to[1,n]\) 是一个均匀随机选取的双射（即把 \(1,2,\dots,n\) 这些编号随机地、等概率地分配给各个顶点）。我们称一个顶点 \(v\in V\) 是好的（good），如果它比自己的所有邻居都大，意思是：只要 \(w\in N(v)\)（\(w\) 是 \(v\) 的邻居），就有 \(\pi(w)<\pi(v)\)。令 \(S\) 为所有好顶点构成的集合。显然 \(S\) 是一个独立集（因为若两个相邻的顶点都“好”，则它们各自都要比对方大，矛盾）。此外，对任意 \(v\in V\)，容易验证 \(v\) 为好顶点的概率恰为 \(\dfrac{1}{\deg(v)+1}\)。于是由期望的线性性 (1.4) 得 \[E(|S|)=\sum_{v\in V}P(v\in S)=\sum_{v\in V}\frac{1}{\deg(v)+1},\] 从而以正的概率有 \(|S|\ge\sum_{v\in V}\dfrac{1}{\deg(v)+1}\)。结论得证。♦

关键一步是“\(v\) 是好顶点的概率 \(=\dfrac{1}{\deg(v)+1}\)”。下面把它讲透。

  1. 只盯住 \(v\) 和它的 \(\deg(v)\) 个邻居，一共 \(\deg(v)+1\) 个顶点。随机双射 \(\pi\) 在这 \(\deg(v)+1\) 个顶点上的相对大小顺序是完全随机的——每个顶点都等可能地成为这一小群里编号最大的那个。
  2. \(v\) “好” 当且仅当 \(v\) 在这一小群里编号最大。因为这一小群里 \(\deg(v)+1\) 个成员地位对称，\(v\) 当上最大者的概率就是 \(\dfrac{1}{\deg(v)+1}\)。
  3. 把每个顶点的“好”概率加起来（期望的线性性，无需独立性），就得到好顶点数目的期望 \(E(|S|)\)。
  4. 期望是平均值，所以至少存在一种编号方式，使实际的 \(|S|\) 不小于这个平均值。那一次的 \(S\) 就是我们要的独立集。
三角形：三点两两相连，每点度数为 2 π=3 π=1 π=2 好（比两个邻居都大） 恰好一个好顶点 → 独立集 {π=3}，大小 1 = n/(d+1)=3/3
三角形中无论怎样随机编号，编号最大的那个点（全局最大）总是唯一的好顶点。\(E(|S|)=3\cdot\frac13=1\)，与三角形最大独立集的真实大小 \(1\) 吻合。
例（路径 \(P_4\)） 取四个顶点排成一条链 \(1-2-3-4\)。各点度数为 \(1,2,2,1\)。代入定理 6.1 的下界： \[\frac{1}{1+1}+\frac{1}{2+1}+\frac{1}{2+1}+\frac{1}{1+1}=\frac12+\frac13+\frac13+\frac12=\frac53\approx1.67.\] 所以一定存在大小 \(\ge 2\) 的独立集——确实如此，例如 \(\{1,3\}\)、\(\{1,4\}\)、\(\{2,4\}\) 都是两两不相连的点对。注意这里用“逐点求和”的精细下界 \(\tfrac53\) 比只用最大度的粗略下界 \(n/(d+1)=4/3\approx1.33\) 更强。

6.2.1　无和子集 Sum-free subsets

1965 年，Erdős 与 Moser [86]（另见 [166] 的问题 C14）提出了如下问题。若 \(B\subset A\) 是两个加性集合，当 \(A\) 中没有任何元素能表示为 \(B\) 中两个不同元素之和时，我们就说 \(B\) 关于 \(A\) 是无和的（sum-free with respect to \(A\)）。给定任意加性集合 \(A\)，令 \(\varphi(A)\) 为 \(A\) 的所有关于 \(A\) 无和的子集中，最大者的基数（元素个数）。再令 \(\varphi(n)\) 为在所有大小为 \(n\) 的集合 \(A\) 中 \(\varphi(A)\) 的最小值；于是 \(\varphi(n)\) 是使得“每个由 \(n\) 个实数组成的集合 \(A\) 都含有一个基数为 \(\varphi(n)\)、关于 \(A\) 无和的子集”的最大数。

定义梳理（务必分清三层）
  1. \(B\) 关于 \(A\) 无和：\(A\) 里没有任何元素能写成 \(B\) 里两个不同元素之和。即对 \(B\) 中任意 \(b_1\ne b_2\)，都有 \(b_1+b_2\notin A\)。
  2. \(\varphi(A)\)：对这一个集合 \(A\)，它最大的无和子集有多大。
  3. \(\varphi(n)\)：在所有大小为 \(n\) 的 \(A\) 里挑最“糟糕”（\(\varphi(A)\) 最小）的那一个的值。它是一个保底保证：随便给你 \(n\) 个数，你总能抠出 \(\varphi(n)\) 个数构成无和子集。

请注意，要求 \(B\) 的元素互不相同对这个问题之有趣至关重要。为看清这点，考虑集合 \(A:=2^{[1,n]}=\{2,2^2,\dots,2^n\}\)。显然，若 \(B\) 是 \(A\) 的任一含两个或更多元素的子集，则 \(A\) 中存在一个元素是 \(B\) 中两个（相等的）元素之和。

例（为什么要“不同”） 取 \(A=\{2,4,8,16,\dots,2^n\}\)（\(2\) 的各次幂）。若允许相加的两个元素相等：只要 \(B\) 里有某个 \(2^i\)（且 \(i不同，问题才有意义。

Klarner 曾指出（未发表），Erdős 在 [86] 中也提到，对大的 \(n\) 有 \(\varphi(n)=\Theta(\log n)\)。这个界的第一个公开证明出现在约十年后 Choi 的论文 [55] 中：

定理 6.2设 \(n\) 为大整数。任何由 \(n\) 个实数组成的集合 \(A\) 都含有一个基数为 \(\log n-O(1)\) 的子集 \(B\)，它关于 \(A\) 无和。换言之，\(\varphi(n)\ge\log n-O(1)\)。
证明. 我们先对正实数的集合 \(A\) 证明此断言。把 \(A\) 的元素排序为 \(0a_i\)，而 \(A\) 中比 \(a_i\) 大的元素只有 \(n-i\) 个，所以对一切 \(i\) 都有 \(\deg(a_i)\le n-i\)。由于 \[\sum_{i=1}^{n}\frac{1}{n-i+1}=\log n-O(1),\] 断言得证。
为证明一般情形，由鸽笼原理可知，任何由 \(n\) 个实数组成的集合，要么含有 \(n/2-O(1)\) 个正实数，要么含有 \(n/2-O(1)\) 个负实数，于是（对大的 \(n\)）由上一段即得结论。♦

这条证明把“相加结构”整个翻译成图论问题，是本节最漂亮的地方。逐步拆开看。

  1. 建图：顶点就是 \(A\) 里的数；只要两个数相加的结果还在 \(A\) 里，就在它们之间画一条边。这样一来，一条边 \(=\) 一对“会惹麻烦”的数。
  2. 翻译“无和”为“独立”：一个子集 \(B\) 关于 \(A\) 无和，意思正是 \(B\) 里任两个不同元素之和不落回 \(A\)——也就是 \(B\) 里没有任何一条边。所以“无和子集”恰好就是图 \(G\) 的“独立集”。
  3. 控制度数：把数从小到大排好 \(a_1<\dotsa_i\)，这个和必须是 \(A\) 中比 \(a_i\) 还大的某个元素。而比 \(a_i\) 大的元素只有 \(a_{i+1},\dots,a_n\) 这 \(n-i\) 个；固定 \(a_i\) 时不同邻居 \(a_j\) 给出不同的和，所以邻居数至多 \(n-i\) 个，即 \(\deg(a_i)\le n-i\)。
  4. 求和得调和级数：代入 Turán 下界，\(\sum_i\frac{1}{\deg(a_i)+1}\ge\sum_i\frac{1}{(n-i)+1}=\frac1n+\frac1{n-1}+\dots+1=H_n=\log n-O(1)\)。这正是自然对数出现的原因。
  5. 去掉“正数”假设：一般实数集合里，正数和负数至少有一边占到约一半（鸽笼），对那一边重复上述论证即可。
A = {1,2,3,4,5,6}，连边规则：a+b ∈ A 时连边 1 2 3 4 5 6 绿点 {4,5,6} 两两无边 → 独立集 = 无和子集 4+5,4+6,5+6 均>6 ∉A
例：\(A=\{1,\dots,6\}\)。红边来自 \(1+2=3,\,1+3=4,\,1+4=5,\,1+5=6,\,2+3=5,\,2+4=6\) 都落回 \(A\)。绿色的 \(\{4,5,6\}\) 没有任何红边相连，是独立集，也就是关于 \(A\) 无和的子集（它们两两之和都超过 \(6\)，跑出了 \(A\)）。

现在讨论上界。这时我们感兴趣的是构造一些不含大无和子集的集合 \(A\)。Erdős 与 Moser [86] 证明了 \(\varphi(n)\le n/3\)，并猜测它的阶很可能是 \(o(n)\)。对 Erdős–Moser 结果的第一个改进归功于 Selfridge，他证明了 \[\varphi(n)\le n/4.\] Choi [55] 用筛法证明了对一切 \(\varepsilon>0\) 有 \(\varphi(n)\le O\!\big(n^{2/5+\varepsilon}\big)\)。他还注意到，在这个问题中只需考虑 \(A\) 为正整数集合这一特殊情形即可。Choi 的结果被 Baltz、Schoen 与 Srivastav [17] 略微改进，他们证明了 \(\varphi(n)\le O\!\big(n^{2/5}\log^{2/5}n\big)\)。上界的一个重大改进是 Ruzsa [297] 最近取得的，他证明了 \[\varphi(n)=e^{O(\sqrt{\log n})}.\]

把这些上界排一排，越往后越小：\(n/3\to n/4\to n^{2/5+\varepsilon}\to n^{2/5}\log^{2/5}n\to e^{O(\sqrt{\log n})}\)。最后这个 \(e^{O(\sqrt{\log n})}\) 比任何 \(n^c\)（\(c>0\)）都小（称为次多项式），却又比任何 \(\log^C n\) 大（因为 \(\sqrt{\log n}\) 比 \(\log\log n\) 大）。它“卡”在多项式与对数之间。

下面我们描述 Ruzsa 的构造，它除了非常巧妙之外，还简短而富有启发性。一个关键技巧是利用 Freiman 同构把问题嵌入到一个维数很高的空间中（另见习题 10.1.4）。

我们将需要一个维数 \(d=\Theta(\sqrt{\log n})\)。利用 Freiman 同构（见引理 5.25），只需构造一个集合 \(A\subset\mathbb{Z}^d\)，使得 \(|A|>n\) 且 \(\varphi(A)\le e^{O(\sqrt{\log n})}\)。对任意 \(r>0\)，令 \(D_r\subset\mathbb{Z}^d\) 为以原点为中心、半径为 \(r\) 的球内的整格点集合，即 \[D_r:=\Big\{(x_1,\dots,x_d)\in\mathbb{Z}^d\ \Big|\ \sum_{i=1}^{d}x_i^2\le r^2\Big\}.\] 然后令 \[A:=\bigcup_{i=0}^{r-1}2^i\cdot D_{r-i},\] 其中 \(r=e^{O(\sqrt{\log n})}\)。对适当选取的 \(d\) 与 \(r\)，可使 \(|A|>n\)，并且我们断言 \[\varphi(A)\le 2^d\,r=e^{O(\sqrt{\log n})}.\] 事实上，设 \(S\subset A\) 的基数大于 \(2^d r\)。那么由鸽笼原理，存在 \(0\le i2^d\)。由于 \(|D_1|=2d+1<2^d\)，我们看出 \(i

Dᵣ：半径 r 的球内整格点（这里 d=2 便于作图） 越大的 r 装下越多格点 A = ∪ᵢ 2ⁱ·Dᵣ₋ᵢ i=0 : 1·Dᵣ （大球，密） i=1 : 2·Dᵣ₋₁ i=2 : 4·Dᵣ₋₂ ⋯ 缩小 第 i 层用 2ⁱ 缩放，半径 r−i 递减 相加 → 跳到下一层 2ⁱ⁺¹·Dᵣ₋ᵢ₋₁
左：\(D_r\) 是半径 \(r\) 球内的整格点（图中取 \(d=2\) 演示，真实证明里 \(d=\Theta(\sqrt{\log n})\)）。右：\(A\) 把 \(D_{r-i}\) 按倍数 \(2^i\) 放大后叠成 \(r\) 层。无和性证明的要害是：同层里两个奇偶相同的向量相加，结果恰好落进下一层 \(2^{i+1}\cdot D_{r-i-1}\subseteq A\)。

把上界证明的鸽笼两连击拆开看，会更清楚为什么 \(A\) 没有大无和子集。

  1. 第一次鸽笼（按层分）：\(A\) 一共 \(r\) 层。若子集 \(S\) 大于 \(2^d r\) 个元素，把它们按所在层分成 \(r\) 堆，必有某一层 \(2^i\cdot D_{r-i}\) 里超过 \(2^d\) 个元素。
  2. 排除最后一层：最末层若是 \(D_1\)，它只有 \(|D_1|=2d+1\) 个格点（原点加上 \(\pm e_1,\dots,\pm e_d\) 这 \(2d\) 个单位向量）。当 \(d\) 适当时 \(2d+1<2^d\)，装不下超过 \(2^d\) 个，故出问题的层必满足 \(i
  3. 第二次鸽笼（按奇偶）：在 \(\mathbb{Z}^d\) 里，每个坐标的奇偶只有两种，整向量的奇偶模式共 \(2^d\) 种。这一层有超过 \(2^d\) 个向量，必有两个 \(s',s''\) 奇偶模式完全相同。
  4. 相加落回 \(A\)：奇偶相同 \(\Rightarrow s'+s''\) 每个坐标都是偶数，平均向量 \((s'+s'')/2\) 仍是整格点，整理后 \(s'+s''\in 2^{i+1}\cdot D_{r-i-1}\subseteq A\)。于是 \(S\) 里出现了一对不同元素之和落回 \(A\)——\(S\) 不是无和的。
  5. 结论：任何无和子集 \(S\) 都不能超过 \(2^d r\)，即 \(\varphi(A)\le 2^d r=e^{O(\sqrt{\log n})}\)。
注记 6.3 我们回到下界。在确立上界的同一篇论文中，Ruzsa [297] 把 Choi 的结果略作改进，证明了 \(\varphi(n)>2\log_3 n-1\)。鉴于 Ruzsa 的上界是次多项式的，人们也许会猜测 \(\varphi(n)=\Theta(\log n)\)，即 \(\varphi(n)\) 的正确数量级就是 \(\log n\)。然而事实并非如此。在最近的一篇论文中，Sudakov、Szemerédi 与 Vu [340] 证明了 \(\varphi(n)\) 是超对数的：于是用 Landau 记号写作 \[\varphi(n)=\omega(\log n).\] 尽管这个结果只比 Choi 的结果改进了一点点，但它的证明需要重型机械，涉及 Balog–Szemerédi–Gowers 定理、Freiman 定理以及 Szemerédi 定理。在这篇论文 [340] 中，作者们还证明了 Balog–Szemerédi–Gowers 定理的一个超图版本（见 6.4 节）。
当前已知的 \(\varphi(n)\) 夹逼小结：下界 \(\varphi(n)=\omega(\log n)\)（严格大于对数阶，Sudakov–Szemerédi–Vu），上界 \(\varphi(n)=e^{O(\sqrt{\log n})}\)（次多项式，Ruzsa）。两端之间仍有差距，\(\varphi(n)\) 的精确数量级尚未完全确定——只知道它比 \(\log n\) 大、却比任何 \(n^c\) 小。

返回 全书目录