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

黄皓(2019年,引言)研究 $n$ 维超立方体图 $Q_n$,其 $2^n$ 个顶点是 $\{0,1\}^n$ 中的二进制串,边连接恰好相差一个坐标的两个串。1988年,钟(Chung)、菲雷迪(Furedi)、格雷厄姆(Graham)与西摩(Seymour)证明了 $Q_n$ 中超过一半顶点上的任意诱导子图的最大度数至少为 $(1/2-o(1))\log_2 n$,并构造了恰好 $2^{n-1}+1$ 个顶点、最大度数仅为 $\lceil\sqrt n\rceil$ 的诱导子图。黄皓的论文完全弥合了这两个界之间的差距:定理1.1指出,$Q_n$ 中至少 $2^{n-1}+1$ 个顶点上的任意诱导子图 $H$ 都满足 $\Delta(H) \ge \sqrt{n}$,恰好与先前的构造相匹配。