Lời giải: Chứng minh giả thuyết độ nhạy của Huang bằng ma trận kề có dấu trên khối siêu lập phương (2019)

Cách phát biểu lại này dựa trên hai sự kiện cổ điển về đồ thị khối siêu lập phương $Q_n$, có $2^n$ đỉnh là các xâu nhị phân của $\{0,1\}^n$, hai đỉnh kề nhau khi khác nhau đúng một toạ độ. Với hàm Boole $f$, độ nhạy tại đầu vào $x$ đếm số lân cận của $x$ trong $Q_n$ mà $f$ đổi giá trị, nên $s(f)$ chính là bậc cực đại của đồ thị hai phía cảm sinh giữa hai tập mức $f^{-1}(0)$ và $f^{-1}(1)$. Nisan và Szegedy (1992) chứng minh $s(f)$ và $\deg(f)$ liên hệ đa thức với mọi độ phức tạp chuẩn khác (độ sâu cây quyết định, độ phức tạp chứng chỉ, độ nhạy khối $bs(f)$) trừ với chính nhau, và đặt giả thuyết $\deg(f) \le s(f)^C$ với hằng số $C$ nào đó.

Bản tương đương thuần đồ thị đã được lượng hoá từ trước: Chung, Füredi, Graham và Seymour (1988) chứng minh mọi đồ thị con cảm sinh $H$ của $Q_n$ trên ít nhất $2^{n-1}+1$ đỉnh thoả $\Delta(H) \ge (\tfrac12 - o(1))\log_2 n$, đồng thời dựng một đồ thị con cảm sinh trên đúng $2^{n-1}+1$ đỉnh với $\Delta(H) = \lceil\sqrt{n}\rceil$ bằng cách lấy quả cầu quanh xâu toàn số 0. Thu hẹp hoàn toàn khe hở giữa $\sqrt{n}$ và $\log n$ tồn tại ba mươi năm, Định lý 1.1 của Huang khẳng định chặn $\Delta(H) \ge \sqrt{n}$ như ở công thức, khớp đúng cấu hình đó nên là hằng số tốt nhất có thể.

Vì phát biểu chỉ hỏi về bậc cực đại, người ta có thể mong một chứng minh thuần tổ hợp; điều bất ngờ là chặn tối ưu lại đến từ đại số tuyến tính trên một ma trận kề được gắn dấu khéo léo, được lắp ráp trong bốn bước tiếp theo.