11.6　超图方法The hypergraph approach

设 \(\varepsilon,m\) 以及 \(G=G(V,E)\) 如引理中所述。我们令 \(V_1=V_2=V\)，并令 \(f(x_1,x_2)\) 为 \(G\) 的关联矩阵（邻接矩阵），即 \(f(x_1,x_2)=\mathbb{I}(\{x_1,x_2\}\in E)\)。设 \(\sigma>0\) 是一个稍后选取的小数（它最终会是 \(\varepsilon^4\) 的一个小倍数），并设 \(F:\mathbb{R}^+\times\mathbb{R}^+\to\mathbb{R}^+\) 是一个稍后选取的增长函数（依赖于 \(m\)）。

我们对 \(d=2\) 应用命题 11.29，得到一个分解 \(f=f_{U^\perp}+f_U\)、\(f_{U^\perp}\) 的一个 \(K\)-常值逼近 \(f_C\)（对某个 \(K=O_{\sigma,F}(1)\)），以及 \(V\) 的两个划分 \(V_{1,1},\dots,V_{1,K}\) 与 \(V_{2,1},\dots,V_{2,K}\)，使 \(f_C\) 关于它们取常值。我们可取其公共加细 \(V_{K(i-1)+j}:=V_{1,i}\cap V_{2,j}\)（\(i,j\in[1,K]\)），得到一个统一的划分 \(V_1,\dots,V_{K^2}\)，使 \(f_C\) 在每个乘积 \(V_i\times V_j\) 上取常值。

接下来，令 \(N\) 为小于 \(\sigma|V|/(100mK^2)\) 的最大整数（我们假定 \(|V|\) 关于 \(m,K,\sigma\) 足够大，使 \(N\ge 1\)），并把每个格子 \(V_j\) 任意地划分成若干个大小为 \(N\) 的不相交子格子，外加一个大小至多为 \(N\) 的误差。注意所有这些误差合在一起，构成一个大小至多 \(K^2 N\le \sigma|V|/(100m)\) 的例外集 \(V_*\)，而其余的子格子给出剩余集 \(V\setminus V_*\) 的一个划分 \(V_1,\dots,V_k\)，每个 \(V_j\) 的基数恰为 \(N\)。于是我们有 \[ |V|-\frac{\sigma|V|}{100m}\le kN\le|V|, \] 因此 \(k\ge m\) 且 \(k=\Theta(|V|/N)=\Theta(mK^2/\sigma)\)。

划分 \(V_1,\dots,V_k,V_*\) 还不完全是第 10.6 节意义下的近一致划分，因为有这个例外集 \(V_*\)。但我们可以把 \(V_*\) 任意地拆成 \(k\) 个近一致的小片并分配到各 \(V_j\) 上，把每个 \(V_j\) 替换成稍大的集合 \(V_j'\)，使 \(V_1',\dots,V_k'\) 成为 \(V\) 的一个近一致划分，并且 \[ |V_j'\setminus V_j|=O\!\left(\frac{|V_*|}{k}+1\right)=O\!\left(\frac{K^2N}{mK^2/\sigma}+1\right)=O(\sigma N), \] 这里我们再次假定 \(|V|\) 关于 \(m,K,\sigma\) 适当地大。于是 \(V_j'\) 仅比 \(V_j\) 大了 \(1+O(\sigma)\) 倍。

现在我们来考察一对 \(V_i,V_j\) 的 \(\varepsilon\)-正则性。设 \(X\subset V_i\)，\(Y\subset V_j\) 满足 \(|X|\ge\varepsilon|V_i|\)，\(|Y|\ge\varepsilon|V_j|\)，特别地 \(|X|,|Y|\ge\varepsilon N\)。我们想看是否有 \[ |d(X,Y)-d(V_i,V_j)|\le\varepsilon; \] 若我们能证明 \[ \left|\mathbb{E}_{x_1\in V_i,x_2\in V_j}\,f(x_1,x_2)\Big(1_X(x_1)1_Y(x_2)-\frac{|X|}{|V_i|}\frac{|Y|}{|V_j|}\Big)\right|\le\varepsilon^3 \tag{11.33} \] 对任意子集 \(X\subset V_i,Y\subset V_j\)（基数无下界要求）成立，则上式即可推出。

我们先做几步预备约化。注意，可以把 \(X\) 限制到 \(V_i'\)、\(Y\) 限制到 \(V_j'\)，并把 \(x_1,x_2\) 的取值范围分别换成 \(V_i'\) 和 \(V_j'\)，左端只产生 \(O(\sigma)\) 的误差。类似地，可以把 \(|X|/|V_i|\) 与 \(|Y|/|V_j|\) 换成 \(|X|/N\) 与 \(|Y|/N\)，同样只接受 \(O(\sigma)\) 的误差。于是 (11.33) 的左端可估为 \[ \left|\mathbb{E}_{x_1\in V_i,x_2\in V_j}\,f(x_1,x_2)\Big(1_X(x_1)1_Y(x_2)-\frac{|X|}{N}\frac{|Y|}{N}\Big)\right|+O(\sigma). \]

现在，由于 \(f_C\) 在 \(V_i\times V_j\) 上取常值，我们有 \[ \mathbb{E}_{x_1\in V_i,x_2\in V_j}\,f_C(x_1,x_2)\Big(1_X(x_1)1_Y(x_2)-\frac{|X|}{N}\frac{|Y|}{N}\Big)=0. \]

其次，由 \(f_U\) 的一致性，我们有 \[ \left|\mathbb{E}_{x_1\in V_i,x_2\in V_j}\,f_U(x_1,x_2)\Big(1_X(x_1)1_Y(x_2)-\frac{|X|}{N}\frac{|Y|}{N}\Big)\right|\le\frac{|V|^2}{N^2\,F(\sigma,K)}=O\!\left(\frac{m^2K^4}{\sigma^2\,F(\sigma,K)}\right). \] 通过适当选取 \(F\)（即令 \(F(\sigma,K)\) 足够大），我们可以确保右端是 \(O(\sigma)\)。

把以上各项放在一起，(11.33) 的左端可被界为 \[ \left|\mathbb{E}_{x_1\in V_i,x_2\in V_j}\,(f_{U^\perp}-f_C)(x_1,x_2)\Big(1_X(x_1)1_Y(x_2)-\frac{|X|}{N}\frac{|Y|}{N}\Big)\right|+O(\sigma). \] 由三角不等式，这小于 \[ 2\,\mathbb{E}_{x_1\in V_i,x_2\in V_j}\,|(f_{U^\perp}-f_C)(x_1,x_2)|+O(\sigma). \]

现在由命题 11.29 与 Cauchy–Schwarz 不等式，我们有 \[ \mathbb{E}_{x_1\in V,x_2\in V}\,|(f_{U^\perp}-f_C)(x_1,x_2)|\le\sigma, \] 削去例外集 \(V_*\) 后，这给出 \[ \mathbb{E}_{x_1\in V_1\cup\cdots\cup V_k,\,x_2\in V_1\cup\cdots\cup V_k}\,|(f_{U^\perp}-f_C)(x_1,x_2)|=O(\sigma). \] 由 Markov 不等式（以及各 \(V_j\) 大小一致），我们断定 \[ \mathbb{E}_{x_1\in V_i,x_2\in V_j}\,|(f_{U^\perp}-f_C)(x_1,x_2)|=O(\sigma/\varepsilon) \] 对除了至多 \(\varepsilon\) 比例的格子对 \((i,j)\) 之外的所有格子对成立。在这种情形下，我们得到 (11.33) 左端的界 \(O(\sigma/\varepsilon)\)；只要取 \(\sigma\) 等于 \(\varepsilon^?\) 的一个小倍数，这就是可接受的。最后，界 \(K=O_{\sigma,F}(1)\) 现在蕴含一个界 \(k=O_{\varepsilon,m}(1)\)，正如所需。这就建立了该引理（取划分 \(V_1,\dots,V_k\)）。♦

注意，在上面的证明中只用到了一个非常特定的函数 \(F(\cdot)\) 的选取。然而，能够任意地设定函数 \(F\) 这件事，在超图理论中变得极其重要，因为它是调和前面提到的那个问题（需要让一个划分给出的正则性控制压倒另一个划分的格子数，同时又不彻底失去对所有误差项的掌控）的最简单办法。当然，为此付出的代价是：论证结束时格子的总数会变得极其巨大。

11.6.6　命题 11.29 的证明：能量增量算法

我们现在开始命题 11.29 的证明。读者不妨把注意力集中在 \(d=2\) 的情形以求熟悉，尽管一般的 \(d\) 情形并无不同。我们将把 \(V_i\) 的划分 \(V_{i,1},\dots,V_{i,K}\) 重新解释为 \(V_i\) 上的 \(\sigma\)-代数 \(\mathcal{B}_i\)（\(1\le i\le d\)），它在 \(V_1\times\cdots\times V_d\) 上诱导出一个更进一步的 \(\sigma\)-代数 \(\mathcal{B}_1\otimes\cdots\otimes\mathcal{B}_d\)，由笛卡尔乘积 \(V_{1,i_1}\times\cdots\times V_{d,i_d}\) 生成。特别注意，函数 \(f_C:=\mathbb{E}(f\mid\mathcal{B}_1\otimes\cdots\otimes\mathcal{B}_d)\) 将是一个取值于 \([0,1]\) 之间的 \(K\)-常值函数。分解 \(f=f_{U^\perp}+f_U\) 将由 \(f_{U^\perp}:=\mathbb{E}(f\mid\mathcal{B}_1'\otimes\cdots\otimes\mathcal{B}_d')\) 与 \(f_U:=f-f_{U^\perp}\) 给出，其中 \(\mathcal{B}_i'\) 是比 \(\mathcal{B}_i\) 略细的 \(\sigma\)-代数。\(\mathcal{B}_i\) 和 \(\mathcal{B}_i'\) 的确切选取将由一个能量增量算法决定，它与证明命题 10.36 时所用的算法非常相似。

我们转入细节。固定 \(V_1,\dots,V_d\) 与函数 \(f:V_1\times\cdots\times V_d\to\mathbb{R}^+\)。给定 \(V_i\) 的任意 \(\sigma\)-代数 \(\mathcal{B}_1,\dots,\mathcal{B}_d\)，我们定义能量 \(\mathcal{E}_f(\mathcal{B}_1\otimes\cdots\otimes\mathcal{B}_d)\) 为 \[ \mathcal{E}_f(\mathcal{B}_1\otimes\cdots\otimes\mathcal{B}_d):=\big\|\mathbb{E}(f\mid\mathcal{B}_1\otimes\cdots\otimes\mathcal{B}_d)\big\|_{L^2(V_1\times\cdots\times V_d)}^2, \] 于是能量取值在 \(0\) 与 \(1\) 之间，且越细的 \(\sigma\)-代数能量越高。正如命题 10.36 依赖于引理 10.40，命题 11.29 将依赖于以下类比。

11.6.7　推广到超图：3-一致情形

现在我们讨论正则性引理向超图的推广。为简化论述，我们只考虑 \(3\)-一致的情形。首先表明，对命题 11.29 证明的一个小改动可以给出如下变体：其中我们得到强得多的一致性控制（关于任意的 \(2\)-边集，而不是顶点集），但代价是一个更弱、更复杂的 \(K\)-常值概念。更精确地说，我们称一个函数 \(f:V_1\times V_2\times V_3\to\mathbb{R}^+\) 是 \((K,2)\)-常值的，若存在划分 \[ V_i\times V_j=E_{ij,1}\cup\cdots\cup E_{ij,K}\qquad(ij=12,23,31), \] 使得 \(f\) 在每个集合 \[ \{(x_1,x_2,x_3)\in V_1\times V_2\times V_3:(x_i,x_j)\in E_{ij,a_{ij}}\text{ 对一切 }ij=12,23,31\} \] 上取常值，其中 \(a_{12},a_{23},a_{31}\in[1,K]\) 任意。

命题 11.33 的证明与命题 11.29 的几乎相同，只是记号负担稍重。我们将它留作习题。

由此可以推出一个全强度的 \(3\)-一致超图正则性引理。这个引理的确切表述相当繁杂、也太不具启发性，不宜在此给出（见 [139]、[283]、[284]、[282]、[360]），但我们将通过非正式地勾勒其证明（遵循 [360]）来间接描述它的表述。

因此总结一下（并略去关于各参数相对大小的微妙问题）：我们从一个三变量函数 \(f(x_1,x_2,x_3)\) 出发，把它逼近成 \(O(K)\) 个双变量函数 \(1_{E_{ij,a}}(x_i,x_j)\) 的组合，加上可控误差；然后我们再把每个 \(1_{E_{ij,a}}(x_i,x_j)\) 逼近成 \(O(K')\) 个单变量函数（即顶点类的指示函数）的组合，同样加上可控误差。在上述精心选取的参数相对大小下，原函数 \(f\) 的这一正则化适用于诸如“准确计数一个 \(3\)-一致超图中 \(3\)-单纯形的数目”之类的任务，其方式在精神上类似于（但比之冗长一些）引理 10.46 的证明。这又最终导致定理 11.27 的证明，而后者又蕴含 Szemerédi 定理以及若干其他推论。

11.6.8　习题

返回 全书目录