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

Huang(2019年、序論)は $n$ 次元超立方体グラフ $Q_n$ を研究する。その $2^n$ 個の頂点は $\{0,1\}^n$ の二進文字列であり、辺はちょうど1座標だけ異なる文字列を結ぶ。1988年、チャン、フューレディ、グラハム、セイモアは $Q_n$ の頂点の半分より多い上の任意の誘導部分グラフが少なくとも $(1/2-o(1))\log_2 n$ の最大次数を持つことを証明し、ちょうど $2^{n-1}+1$ 個の頂点からなり最大次数がわずか $\lceil\sqrt n\rceil$ である誘導部分グラフを構成した。Huangの論文はこの2つの評価の間の差を完全に埋める:定理1.1は、$Q_n$ の少なくとも $2^{n-1}+1$ 個の頂点上の任意の誘導部分グラフ $H$ が $\Delta(H) \ge \sqrt{n}$ を満たすと述べており、これは先の構成と正確に一致する。