MathLabs

解法:黄皓用带符号超立方体邻接矩阵证明敏感度猜想(2019年)

第 5/7 步:拼合各部分:主定理由此得出
通俗地说

现在前面三个要素结合在一起。矩阵 AnA_n 以巨大的重数 2n−12^{n-1} 拥有特征值 n\sqrt{n};交错定理表明任何足够大的主子矩阵都必须继承一个至少同样大的特征值;而行和事实又把这个特征值转换回关于实际图 HH 最大度数的结论。

λ1(AH)≥λ2n−1(An)=n\lambda_1(A_H) \ge \lambda_{2^{n-1}}(A_n) = \sqrt{n}
详细分析

固定 QnQ_n 中在顶点集 SS(满足 ∣S∣≥2n−1+1|S| \ge 2^{n-1}+1)上的任意诱导子图 HH,设 AHA_H 是仅保留由 SS 标号的行与列所得的 AnA_n 的主子矩阵。由引理2.2(第3步),AnA_n 以重数 2n−12^{n-1}(超过 2n−∣S∣2^n - |S|)拥有特征值 n\sqrt{n};于是对 i=2n−1i = 2^{n-1} 应用柯西交错定理(第2步)得到 λ1(AH)≥λ2n−1(An)=n\lambda_1(A_H) \ge \lambda_{2^{n-1}}(A_n) = \sqrt{n}。将其与应用于 AHA_H 的行和引理(第4步)结合,即得 Δ(H)≥n\Delta(H) \ge \sqrt{n}——恰是黄皓的定理1.1。

本步骤用到的知识