Source-linked AI summary
Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
Hao Huang
TL;DR
The paper addresses the unresolved relationship between sensitivity and other boolean-function complexity measures by proving the equivalent hypercube induced-subgraph statement. Its sharp √n degree bound for every (2^{n-1}+1)-vertex induced subgraph yields a polynomial sensitivity–degree relation and confirms the Sensitivity Conjecture, while the remaining block-sensitivity separation is not closed.
Problem
The Sensitivity Conjecture asks whether boolean-function sensitivity is polynomially related to block sensitivity, despite prior evidence and relationships among other complexity measures.
Method
The paper proves the combinatorially equivalent Gotsman–Linial hypercube induced-subgraph formulation using a spectral method based on symmetric matrix sequences and largest adjacency eigenvalues.
Results
Every (2^{n-1}+1)-vertex induced subgraph of Q_n has maximum degree at least √n, a bound tight when n is a perfect square, confirming the Sensitivity Conjecture.
Takeaways & Limitations
The result establishes a polynomial relationship between sensitivity and degree and places sensitivity within the family of complexity measures polynomially related to block sensitivity.
Takeaways & Limitations
The best known block-sensitivity versus sensitivity separation remains quadratic, while the paper’s Theorem 1.5 gives only a quartic upper bound.
Abstract
from arXiv · showhide
In this paper, we show that every $(2^{n-1}+1)$-vertex induced subgraph of the $n$-dimensional cube graph has maximum degree at least $\sqrt{n}$. This result is best possible, and improves a logarithmic lower bound shown by Chung, Füredi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.
1 Introduction
The paper proves a sharp maximum-degree lower bound for induced subgraphs of the hypercube and uses its equivalence with boolean-function complexity to settle the Sensitivity Conjecture.
- Main result: The result improves the earlier logarithmic lower bound of Chung, Füredi, Graham, and Seymour for induced subgraphs larger than half the cube.Their 1988 bound was approximately (1/2 − o(1)) log_2 n.
- Main result: The 2^{n-1} even vertices of Q_n induce an empty subgraph, so adding one vertex causes the asserted degree jump.The theorem identifies the threshold immediately beyond half the hypercube.
- Sensitivity Conjecture: The Sensitivity Conjecture asks whether sensitivity is polynomially related to block sensitivity, a relationship that remained unresolved despite extensive prior work.Block sensitivity is already polynomially related to several other boolean-function complexity measures.
- Sensitivity Conjecture: Gotsman and Linial showed that cube-subgraph bounds are equivalent to lower bounds relating boolean-function sensitivity to polynomial degree.Their equivalence uses Γ(H), the larger maximum degree of an induced subgraph and its complement.
- Sensitivity Conjecture: The paper’s cube result implies a √n lower-bound function in the Gotsman–Linial equivalence and confirms the Sensitivity Conjecture.The resulting sensitivity–degree inequality is tight for the AND-of-ORs boolean function.
2 Proof of the main theorem
The proof uses recursively defined symmetric matrices whose spectra are controlled by interlacing. Applying these matrices to an induced subgraph of the hypercube yields the sharp maximum-degree lower bound and a stronger spectral bound.
- Spectral tool: Cauchy’s Interlace Theorem compares eigenvalues of a symmetric matrix with those of any principal submatrix.This theorem supplies the spectral comparison used after restricting A_n to the vertices of H.
- Matrix construction: The proof constructs a recursively defined sequence of symmetric matrices A_n with eigenvalues √n and −√n, each of multiplicity 2^(n−1).The construction is established inductively, beginning with the n=1 case.
- Matrix construction: Changing every −1 entry of A_n to 1 produces the adjacency matrix of Q_n, so A_n encodes the hypercube’s adjacency structure.The two diagonal identity blocks represent the perfect matching between the two recursively identified subcubes.
- Main bound: For any (2^(n−1)+1)-vertex induced subgraph H, interlacing and the matrix eigenvalue bounds imply Δ(H) ≥ √n.The induced adjacency matrix is a principal submatrix of A_n, and the proof combines the resulting inequalities.
- Sharpness: The stronger bound λ1(H) ≥ √n is best possible: all even vertices together with one odd vertex induce a star K1,n plus isolated vertices.Since Δ(H) ≥ λ1(H), the spectral statement strengthens the degree lower bound.
3 Concluding Remarks
The paper confirms the Sensitivity Conjecture through its combinatorial equivalent and identifies several directions for extending the hypercube and spectral methods. It also records a remaining gap between known block-sensitivity and sensitivity bounds.
- Main conclusion: The paper confirms the Sensitivity Conjecture by proving the combinatorial equivalent formulation discovered by Gotsman and Linial.The concluding remarks frame the main result as a resolution of the conjecture.
- Open problems: For a highly symmetric graph G, the authors ask how the minimum maximum degree on α(G)+1 vertices can be characterized.They specifically ask when the method used for Theorem 1.1 gives a tight bound.
- Open problems: The hypercube quantity g(n,k) is determined at the studied threshold by g(n,√n)=2^(n−1)+1.The authors leave the asymptotic behavior for other values of k open.
- Remaining gap: The best stated separation between block sensitivity and sensitivity remains quadratic, while Theorem 1.5 supplies only a quartic upper bound.The authors suggest that a direct spectral application to Boolean functions might help close this gap.