解法: 符号付き超立方体隣接行列によるホァンの感度予想の証明(2019年)

この言い換えは、頂点が $\{0,1\}^n$ の二進文字列で、ちょうど1座標だけ異なるもの同士を辺で結んだ超立方体グラフ $Q_n$（$2^n$ 個の頂点を持つ）に関する2つの古典的事実に基づく。ブール関数 $f$ に対し、入力 $x$ での感度は $Q_n$ における $x$ の近傍のうち $f$ の値が変わるものの個数を数えるので、$s(f)$ はレベル集合 $f^{-1}(0)$ と $f^{-1}(1)$ の間に誘導される二部グラフの最大次数そのものである。Nisan–Szegedy（1992）は、$s(f)$ と $\deg(f)$ が他の標準的な複雑性尺度（決定木の深さ、証明書複雑性、ブロック感度 $bs(f)$）すべてと多項式的に関係する一方で互いの関係だけが未解決であることを示し、ある定数 $C$ で $\deg(f) \le s(f)^C$ となるかを問うた。

グラフ理論への言い換えはすでに定量化されていた。Chung–Füredi–Graham–Seymour（1988）は、$Q_n$ の少なくとも $2^{n-1}+1$ 頂点上の任意の誘導部分グラフ $H$ が $\Delta(H) \ge (\tfrac12 - o(1))\log_2 n$ を満たすことを証明し、ゼロ文字列を中心とする球を取ることでちょうど $2^{n-1}+1$ 頂点・最大次数 $\Delta(H) = \lceil\sqrt{n}\rceil$ の誘導部分グラフを構成した。30年間開いていた $\sqrt{n}$ 対 $\log n$ の隙間を完全に埋め、Huang の定理1.1は表示された上界 $\Delta(H) \ge \sqrt{n}$ を主張する。これは上の構成と一致するので定数として最良である。

主張が最大次数のみを問うものなので、純粋な組合せ的証明を期待するかもしれないが、驚くべきことに最適な評価は、巧みに符号を付けた隣接行列への線形代数から得られる。それを次の4ステップで組み立てる。