原文： Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

本文证明了对于 n 维立方体图的每一个拥有 (\(2^{n-1}+1\)) 个顶点的导出子图，其最大的度（degree）至少为 \(\sqrt {n}\)。这个结论优化了由 Chung, F¨uredi, Graham 以及 Seymour 在 1988 年证明的对数形式的下界（lower bound），并且可能是最优解。这个结论可以直接证明由 Nisan 和 Szegedy提出的理论计算机科学界著名猜想–布尔函数敏感度猜想（Sensitivity Conjecture），即布尔函数的敏感度和度是多项式相关的。

1 介绍

设 \(Q^{n}\) 为 n 维超立方体图， 其顶点集合由 \(\{ 0,1\} ^{n}\) 上的向量构成，并且两个向量的坐标中只有一个坐标值不同时，两向量相邻。对于一个无向图 \(G\)，我们使用标准图论标记 \(\Delta(G)\) 表示其最大的度 (degree)，使用 \(\lambda_{1}(G)\) 表示其邻接矩阵的最大特征值。在 1988 年，Chung、F¨uredi、Graham 和 Seymour 证明了如果 \(H\) 是 \(Q^{n}\) 的一个导出子图，且包含大于 \(2^{n-1}\) 个顶点，则 \(H\) 最大的度至少为 \((1/2-o(1)) \log _{2}n\)。此外，他们还构建了一个顶点数为 \((2^{n-1}+1)\) 的导出子图且子图最大的度为 \(\lceil\sqrt{n}\rceil\)（译注：\(\lceil\rceil\)为向上取整标志）。

在这篇简短的论文中，我们证明了以下的结论，并且针对他们构建的导出子图建立了可以取等号的下界。需要留心的是 \(Q^{n}\) 的 \(2^{n-1}\) 个偶顶点（even vertices）导出的子图为空图（译注：这里的偶顶点不是图论中的偶顶点，而是在 Chung、F¨uredi、Graham 和 Seymour 的论文 On Induced Subgraphs of the Cube 中定义的 \(V(G_{\mathrm{even}}^{n})\)，即顶点向量坐标中有偶数个 1 的顶点）。这条定理说明了包含 \(2^{n-1}\) 个偶顶点且再多任意一个顶点的子图最大的度会突变至 \(\sqrt {n}\)。

定理1.1. 对于每个整数 \(n \geqslant 1\)，设 \(H\) 是 \(\sqrt {n}\) 任意包含 \((2^{n-1}+1)\) 个顶点的导出子图，则有 \[\Delta(H) \geqslant \sqrt{n}\] 不等式在 n 为完全平方数时取等号。

导出子图问题与理论计算机科学领域最重要和最具挑战性问题之一的布尔函数敏感度猜想有着紧密的关系。Nisan 在他 1989 年的论文中，给出了在 CREW-PRAM 模型中计算布尔函数值的正确边界。这些边界被表述为两个布尔函数的复杂度测度（complexity measures）。对于 \(x \in\{0,1\}^{n}\) 以及索引 \([n]=\{1, \cdots, n\}\) 的子集 \(S\)，我们使用 \(x^{S}\) 来表示通过翻转 \(x\) 中所有 \(S\) 索引的位置的比特得到的二进制向量。对于 \(f:\{{0,1}\}^{n} \rightarrow \{{0,1}\}\)，输入序列 \(x\) 的本地敏感度（local sensitivity） \(s(f, x)\) 被定义为使 \(f(x) \neq f(x^{\{i\}})\) 成立的 \(i\) 的数量，\(f\) 的敏感度（sensitivity） \(s(f)\) 则被定义为 \({\rm max}_{x}s(f, x)\)。布尔函数敏感度从汉明距离（Hamming distance）角度，度量了布尔函数本地变化的行为。这可以被视为一个连续函数平滑度的离散近似（可以参见原文参考文献[7]来进行更深一步的探讨）。将 \([n]\) 划分为不相交的 \(k\) 块，分别标记为 \(B_1,…,B_k\)。 本地块敏感度（local block sensitivity） \(bs(f, x)\)，被定义为使对于每一块分块 \(B_i\) 都有 \(f(x) \neq f(x^{B_i})\) 成立的 \(k\) 的最大值。同理，\(f\) 的块敏感度（block sensitivity） \(bs(f)\) 定义为 \({\rm max}_{x}bs(f, x)\)。显然，\(b s(f) \geqslant s(f)\)。在复杂度理论领域，Nisan 和 Szegey 提出了一个重要的开放性问题——这两者是否是多项式相关的（polynomially related）。

猜想 1.2. （敏感度猜想 Sensitivity Conjecture）存在一个常量 \(C > 0\)，对于所有布尔函数 \(f\) 均有 \[bs(f) \leqslant s(f)^{C}\]

尽管看起来并不自然，但块敏感度确实是与其他重要的布尔函数复杂度测度多项式相关，包括决策树复杂度（decision tree complexity），认证复杂度（certificate complexity），量子和随机查询复杂度（quantum and randomized query complexity），以及布尔函数的（作为实多项式）的度和近似度（approximate degree）。值得注意的是，这里边的一些关系是很微妙的。举个例子来说，虽然度和近似度都是从布尔函数的代数特性考虑的，但已知的唯一证明两者多项式关系的方法却更多的用到组合数学的相关理论。

敏感度猜想如果被证明为真，那么敏感度将和上面提到的复杂度测度被分到同一类中。在计算方面，敏感度猜想说明了“光滑”（低敏感度）函数在最简单的模型（例如确定决策树模型 deterministic decision tree model）中，是很容易计算的。在代数方面，敏感度猜想断言了这些函数与实多项式有同样低的度。在组合数学方面，正如 Gotsman 和 Linial 发现的那样，敏感度猜想与先前提到的立方体问题是等价的。我们将会在后文讨论这种关联。

尽管经过了将近 30 年的大量尝试，敏感度猜想仍然悬而未决。在此期间，\(bs(f)\) 最好的上界（upper bound） 是用\(s(f)\) 表示的指数函数。例如，Kenyon 和 Kutin 证明了 \(bs(f) = O(e^{s(f)} \sqrt{s(f)})\)。对于下界而言，Rubinstein 首先提出了一个布尔函数 \(f\) 且其 \(bs(f) = \frac{1}{2} s(f)^{2}\)，展示了这两种复杂度测度的二次函数关系。Virza，以及接下来的 Ambainis 和 Sun 构建了一个更好的布尔函数，但两个复杂度测度仍是二次关系。 关于更多的背景和讨论，特别是很多背景和讨论提到的问题和敏感度猜想是等价的，我们推荐读者去阅读 Buhrman 和 de Wolf 的研究以及 Hatami，Kulkarni 和 Pankratov 的研究，还有一些参考文献列出的近期的研究成果。

回想一下文章开头提到的，\(Q^{n}\) 代表 n 维超立方体图。对于 \(Q^{n}\) 的一个导出子图 \(H\)，用 \(Q^{n} - H\) 代表由顶点集合 \(V(Q^{n}) \backslash V(H)\) 导出的 \(Q^{n}\) 的子图。记 \(\Gamma(H) = {\rm max}\{\Delta(H), \Delta(Q^{n} - H)\}\)。布尔函数 \(f\) 的 度 记为 \({\rm deg}(f)\)，其含义是能够唯一表示 \(f\) 的多线性实多项式（multilinear real polynomial）的度。Gotsman 和 Linial 用傅里叶分析得出了以下重要的等价关系。

定理 1.3. （Gotsman 和 Linial 原文参考文献 [9]） 对于任意单调函数 \(h: \mathbb{N} \rightarrow \mathbb{R}\)，以下两条结论是等价的。
（a） 对于 \(Q^{n}\) 的任意导出子图 \(H\) 满足 \(|V(H)| \neq 2^{n-1}\)，有 \(\Gamma(H) \geqslant h(n)\)。
（b）对于任意布尔函数 \(f\)，有 \(s(f) \geqslant h({\rm deg}(f))\)。

注意，定理 1.1 说明了 \(h(n)\) 可以取 \(\sqrt{n}\)，原因是 \(H\) 或者 \(Q^{n} - H\) 两者一定有一个至少包含 \(2^{n-1}+1\) 个顶点。同时，最大的度 \(\Delta\) 是单调的。那么，可以得出

定理 1.4. 对于任意布尔函数 \(f\)， \[s(f) \geqslant \sqrt{{\rm deg}(f)}\]

这个不等式证实了 Gotsman 和 Linia 的猜想。不等式对于多个或运算做与的布尔函数（译注：也就是合取范式）能取到等号【原文参考文献10，例5.2】。回忆下刚才的定理，布尔函数的度与块敏感度是多项式相关的。Nisan 和 Szegedy 证明了 \(bs(f) \leqslant 2deg(f)^2\)【原文参考文献13】，这个边界在后来被 Tal 优化为了 \(bs(f) \leqslant deg(f)^2\)【原文参考文献15】。结合这些结果我们就证明了敏感度猜想。

定理 1.5 对任意布尔函数 \(f\)， \[bs(f) \leqslant s(f)^4\]

2 主要定理证明

为了构建定理 1.1，我们首先介绍一系列的引理。设有一个 \(n \times n\) 的矩阵 \(A\)，\(A\) 的主子矩阵是指通过删除 \(A\) 中同样标号的行列所得到的子矩阵。

引理 2.1 （柯西交错定理 Cauchy’s Interlace Theorem）设 \(A\) 为 \(n \times n\) 的对称矩阵，\(B\) 为 \(A\) 的 \(m \times m\) 主子矩阵，\(m < n\)。若矩阵 \(A\) 的特征值为 \(\lambda_1 \geqslant \lambda_2 \geqslant … \geqslant \lambda_n\)，矩阵 \(B\) 的特征值为 \(\mu_1 \geqslant \mu_2 \geqslant … \geqslant \mu_n\)，那么对于所有的 \(1 \leqslant i \leqslant m\)，

\[\lambda_i \geqslant \mu_i \geqslant \lambda_{i+n-m}\]

柯西交错定理可以由 Courant-Fischer-Weyl 极小极大值定理（Courant-Fischer-Weyl min-max principle）直接得到。在原文参考文献【5】可以找到直接的证明。

引理 2.2 我们递归的定义一系列对称方阵如下，

\[A_1 = \begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix}, A_n = \begin{bmatrix}A_{n - 1} & I \\ I & -A_{n - 1}\end{bmatrix}\]

则 \(A_n\) 就是一个 \(2^n \times 2^n\) 矩阵，其特征值为 \(\sqrt{n}\) 和 \(-\sqrt{n}\)，且两个特征值的重复度（multiplicity）均为 \(2^{n-1}\)。

证明： 我们通过归纳 \(A_n^I = nI\) 来得证。对于 \(n = 1\)，\(A_1^2 = I\)。假设结论成立，则 \(A_{n - 1}^2 = n - 1\)，那么 \[A_n^2 = \begin{bmatrix}A_{n - 1}^2 + I & 0 \\ 0 & A_{n - 1}^2 + I\end{bmatrix} = nI\]

因此，\(A_n\) 的特征值为 \(\sqrt{n}\) 或 \(- \sqrt{n}\)。又因为 \(Tr[A_n] = 0\)，所以 \(A_n\) 的特征值一定是一半为 \(\sqrt{n}\)，一半为 \(- \sqrt{n}\)。\(\square\)

引理 2.3 假设 \(H\) 是一个有 m 个顶点的无向图，\(A\) 是一个对称矩阵，其矩阵元素在 \(\{-1,0,1\}\) 中取值，并且矩阵的行和列由 \(V(H)\) 来索引，当 \(u\) 和 \(v\) 在 \(H\) 中不相邻时，\(A_{u,v} = 0\)。那么

\[\Delta(H) \geqslant \lambda_1 := \lambda_1(A)\]

证明： 设 \(\vec{v}\) 是 \(\lambda_1\) 对应的特征向量，则有 \(\lambda_1\vec{v} = A\vec{v}\)。为了不失一般性，设 \(v_1\) 是 \(\vec{v}\) 坐标中绝对值最大的分量。那么

\[|\lambda_{1}v_1| = |(A\vec{v})_1| = |\sum_{j = 1}^{m}A_{1,j}v_j| = |\sum_{j \sim 1}A_{1,j}v_j| \leqslant \sum_{j \sim 1}|A_{1,j}||v_1| \leqslant \Delta(H)|v_1|\]

因此，\(|\lambda_1| \leqslant \Delta(H)\)。\(\square\)

有了以上几个引理，就可以开始证明主要定理了。

定理 1.1 证明： 设 \(A_n\) 是引理 2.2 中的矩阵，这里要注意，\(A_n\) 的矩阵元素取值在 \(\{-1,0,1\}\) 内。通过迭代构建 \(A_n\)，并不难发现如果把 \(A_n\) 中的 -1 换成 1，我们得到的矩阵正好就是 \(Q^n\) 的邻接矩阵，所以，\(A_n\) 和 \(Q^n\) 就满足了引理 2.3 中的条件。例如，我们让 \(A_n\) 中左上和右下的块对应 \(Q^n\) 的两个 \(n - 1\) 维子立方体，剩下两个单位矩阵对应这两个立方体的完美匹配（perfect match）的连接。因此，\(Q^n\) 的一个 \((2^{n-1}+1)\) 个顶点的导出子图 \(H\) 和 其对应的 \(A_n\) 的主子矩阵 \(A_H\) 就也都满足引理 2.3 的条件了。那么我们可以得到，

\[\Delta(H) \geqslant \lambda_1(A_H)\]

另一方面，从引理 2.2 可以得到，\(A_n\) 的特征值为

\[\sqrt{n},…,\sqrt{n},-\sqrt{n},…,-\sqrt{n}\]

注意 \(A_H\) 是一个 \(2^n \times 2^n\) 矩阵 \(A_n\) 的 \((2^{n-1}+1) \times (2^{n-1}+1)\) 子矩阵。通过柯西交错定理我们可以得到

\[\lambda_1(A_H) \geqslant \lambda_{2^{n-1}}(A_n) = \sqrt{n}\]

结合两个不等式我们就可以得到 \(\Delta(H) \geqslant \sqrt{n}\)，得证。\(\square\)

注： 在证明中，其实还有 \(\lambda_1(H) \geqslant \lambda_1(A_H) \geqslant \sqrt{n}\)。由于 \(\Delta(H) \geqslant \lambda_1(H)\)，这个结果可以说印证了定理 1.1。更有趣的是，不等式 \(\lambda_1(H) \geqslant \sqrt{n}\) 可能对所有的 \(n\) 来说都是最优解。这点可以通过取 \(Q^n\) 所有偶顶点（同上，非图论中的偶顶点）和一个奇顶点来直观感受。这些顶点的导出子图由一个星形图 \(K_{1,n}\) 和一些孤立顶点构成，其最大的特征值就是 \(\sqrt{n}\)。

结束语

懒得翻译了，自己看原文去吧。

版本控制

修改内容	时间	修改人
Init	2020-02-23T16:47:00+08:00	Kortan