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

ゴッツマンとリニアル(1992年)は、$\Gamma(H) \ge h(n) \text{ for every } H \text{ with } |V(H)| \ne 2^{n-1}$ と、すべてのブール関数 $f$ に対する $s(f) \ge h(\deg(f))$ が同値であることを証明した。前者の H では、H とその補グラフの一方が少なくとも $2^{n-1}+1$ 個の頂点を持つ。定理1.1に $h(n) = \sqrt{n}$ を適用すると $s(f) \ge \sqrt{\deg(f)}$ が得られる。