一个猜想的证明

立方体图子图的最大度

Posted on 8/1/2019

Contents

Hypothesis
Sketch of proof
Step 1
Step 2
Step 3
Step 4
Details
Step 1
Step 2
Step 3

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

#Hypothesis

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

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

#Sketch of proof

证明概述如下

#Step 1

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

A1=[0110]An=[An1IIAn1]A_{1}=\left[\begin{array}{ll}{0} & {1} \\ {1} & {0}\end{array}\right] \quad A_{n}=\left[\begin{array}{cc}{A_{n-1}} & {I} \\ {I} & {-A_{n-1}}\end{array}\right]

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

#Step 2

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

#Step 3

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

λiμiλi+nm\lambda_i \geq \mu_i \geq \lambda_{i + n - m}

#Step 4

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

#Details

#Step 1

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

#Step 2

λ1\lambda_1GG 的伪邻接矩阵 AA 的一个特征值, v1\vec{v}_1 是它对应的特征向量,则

λ1v1=(Av)1=j=1mA1,jvj=j1A1,jvjj1A1,jv1Δ(H)v1\left|\lambda_{1} v_{1}\right|=\left|(A \vec{v})_{1}\right|=\left|\sum_{j=1}^{m} A_{1, j} v_{j}\right|=\left|\sum_{j \sim 1} A_{1, j} v_{j}\right| \leqslant \sum_{j \sim 1}\left|A_{1, j}\right|\left|v_{1}\right| \leqslant \Delta(H)\left|v_{1}\right|

#Step 3

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

AA 是一个 nn 阶实对称矩阵, BB 是它的一个 n1n - 1 阶主子阵,设 λ1λ2λn\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_nμ1μ2μm1\mu_1 \geq \mu_2 \geq \cdots \mu_{m - 1} 分别是它们的全部特征根,则对于每个 i (1im)i\ (1 \leq i \leq m) ,均有

λ1μ1λ2μ2μn1λn\lambda_1 \geq \mu_1 \geq \lambda_2 \geq \mu_2 \geq \cdots \geq \mu_{n - 1} \geq \lambda_n

注意到这个引理

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

λ1μ1λ2μ2μn1λn\lambda_1 \geq \mu_1 \geq \lambda_2 \geq \mu_2 \geq \cdots \geq \mu_{n - 1} \geq \lambda_n

当且仅当 对于任意实数 α\alphaf+αgf + \alpha g 的根均为实根.

引理的证明是简单的

不妨设 BBAA 的前 n1n - 1 行和列构成,即

A=(Bccd)A=\left(\begin{array}{c|c}{B} & {c} \\ \hline c^{*} & {d}\end{array}\right)

从而

BxIccdx+α=BxIccdx+BxIccα\left\lvert\begin{array}{c|c} {B - xI} & {c} \\ \hline c^* & {d - x + \alpha} \end{array}\right\rvert = % \left\lvert\begin{array}{c|c} {B - xI} & {c} \\ \hline c^* & d - x \end{array}\right\rvert + % \left\lvert \begin{array}{c|c} {B - xI} & {c} \\ \hline c^* & \alpha \end{array}\right\rvert

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