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

Huang(2019年、補題2.3)は単純だが重要な事実を示す:$H$ が $m$ 頂点グラフで $A$ が成分が $\{-1,0,1\}$ に属し非零パターンが $H$ の辺に一致する任意の対称行列であれば、$\Delta(H) \ge \lambda_1 := \lambda_1(A)$ が成り立つ。証明は最大固有値の固有ベクトル $v$ を取り、絶対値最大の座標 $v_1$ に着目する:$|\lambda_1 v_1| = |(Av)_1| = \left|\sum_{j \sim 1} A_{1,j} v_j\right| \le \Delta(H)|v_1|$ なので、$|v_1|$ で割ると $\lambda_1(A) \le \Delta(H)$ を得る。