解法:黄皓用带符号超立方体邻接矩阵证明敏感度猜想(2019年)
通俗地说现在前面三个要素结合在一起。矩阵 An 以巨大的重数 2n−1 拥有特征值 n;交错定理表明任何足够大的主子矩阵都必须继承一个至少同样大的特征值;而行和事实又把这个特征值转换回关于实际图 H 最大度数的结论。
详细分析固定 Qn 中在顶点集 S(满足 ∣S∣≥2n−1+1)上的任意诱导子图 H,设 AH 是仅保留由 S 标号的行与列所得的 An 的主子矩阵。由引理2.2(第3步),An 以重数 2n−1(超过 2n−∣S∣)拥有特征值 n;于是对 i=2n−1 应用柯西交错定理(第2步)得到 λ1(AH)≥λ2n−1(An)=n。将其与应用于 AH 的行和引理(第4步)结合,即得 Δ(H)≥n——恰是黄皓的定理1.1。
本步骤用到的知识