一个猜想的证明

立方体图子图的最大度

最近看到一篇文章,讲述了一个几十余年历史的猜想近日被证明的事情。令人惊讶的是论文中的这个证明主题居然只有不到两页,并且只用到了基本的线性代数,遂记录之。

Hypothesis

这个猜想可以是在研究 Bool 函数的“敏感性”时被提出来的,其内容可等价叙述如下:

设 $Q_n$ 表示 $n$ 维立方体图(即顶点为立方体的顶点,两点连有一条无向边当且仅当其在立方体上相邻),求证对于这个图的任意一个包含 $2^{n-1} + 1$ 个顶点的诱导子图,它的最大度数不小于 $\sqrt{n}$ .

Sketch of proof

证明概述如下

Step 1

称一个实对称矩阵 $M$ 是某个图 $G$ 的伪邻接矩阵,如果 $\lvert a_{ij}\rvert = 1$ 当且仅当 $G$ 中的第 $i$ 个顶点和第 $j$ 个相邻,且矩阵除此以外的项均为零. 归纳构造矩阵 $A_n$ ,使得

归纳易证 $A_n$ 是 $Q_n$ 的伪邻接矩阵,且 $A_n$ 的特征向量中恰有 $2^{n - 1}$ 个为 $\sqrt{n}$ , $2^{n - 1}$ 个是 $\sqrt{n}$ .

Step 2

证明一个图的最大度数不小于它的伪邻接矩阵的任何一个特征根.

Step 3

Cauchy interlace lemma:若 $A$ 是一个 $n$ 阶实对称矩阵, $B$ 是它的一个主子阵, 设 $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$ , $\mu_1 \geq \mu_2 \geq \cdots \mu_m$ 分别是它们的全部特征根,则对于每个 $i\ (1 \leq i \leq m)$ ,均有

Step 4

考虑 $Q_n$ 的某个 $2^{n - 1} + 1$ 阶子图,它对应于 $A_n$ 的一个主子阵,由于 $A_n$ 的前 $2^{n - 1}$ 个特征根均为 $\sqrt{n}$ ,根据 Step 3 ,它的最大特征根是 $\sqrt{n}$ ,带入 Step 2 即可得到待证结论.

Details

Step 1

事实上,归纳易证 $A_n^2 = nI_n$ ,故 $A_n$ 的特征根必为 $\pm \sqrt{n}$ ,再注意到 $A_n$ 的迹为 0,故 $A_m$ 必有一半的特征根为 $\sqrt{n}$ ,另一半为 $-\sqrt{n}$ .

Step 2

设 $\lambda_1$ 是 $G$ 的伪邻接矩阵 $A$ 的一个特征值, $\vec{v}_1$ 是它对应的特征向量,则

Step 3

事实只需证明下面这个特殊情形

若 $A$ 是一个 $n$ 阶实对称矩阵, $B$ 是它的一个 $n - 1$ 阶主子阵,设 $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$ , $\mu_1 \geq \mu_2 \geq \cdots \mu_{m - 1}$ 分别是它们的全部特征根,则对于每个 $i\ (1 \leq i \leq m)$ ,均有

注意到这个引理

若 $f, g$ 分别是 $n, n-1$ 阶的实多项式, $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$ , $\mu_1 \geq \mu_2 \geq \cdots \mu_{m - 1}$ 分别是它们的全部根,则

当且仅当 对于任意实数 $\alpha$ , $f + \alpha g$ 的根均为实根.

引理的证明是简单的

不妨设 $B$ 由 $A$ 的前 $n - 1$ 行和列构成,即

从而

注意到等式左边是一个实对称矩阵,右边是 $\lvert A - xI_n\rvert + \alpha \lvert B - xI_{n - 1} \rvert = f + \alpha g$ ,这便表明了 $f + \alpha g$ 的根均为实数.

NEXT
小数部分均匀分布的初等(大概)证明