Induced subgraphs of hypercubes and a proof of the sensitivity conjecture (Q2334869)

The \(n\)-dimensional hypercube \(Q^{n}\) is the graph with vertex set being the vectors in \(\{0, 1\}^{n}\) where two vectors are connected by an edge when they differ in exactly one coordinate. Let \(\Delta(G)\) denote the maximum degree of a vertex in \(G\). This paper proves the following main result. Theorem 1. Given an integer \(n \geq 1\), let \(H\) be an arbitrary induced subgraph of \(Q_{n}\) on \((2^{n-1} + 1)\) vertices. Then \(\Delta(H) \geq \sqrt{n}\) and this inequality is tight when \(n\) is a perfect square. Through a sequence of equivalences, this result proves the sensitivity conjecture, stated below as a theorem. Given a vector \(x \in \{0, 1\}^{n}\) and a set of indices \(S\), let \(x^{S}\) be the vector obtained from \(x\) be flipping the bits of \(x\) in the positions corresponding to indices in \(S\). The local sensitivity of a Boolean function \(f: \{0, 1\}^{n} \rightarrow \{0, 1\}\), denoted by \(\operatorname{s}(f, x)\), is the minimum number of indices \(i\) such that \(f(x) \neq f(x^{\{i\}})\). The sensitivity of \(f\), denoted by \(\operatorname{s}(f)\), is then defined as \(\max_{x} \operatorname{s}(f, x)\). Similarly, the local block sensitivity \(\operatorname{bs}(f, x)\) is the maximum number of disjoint blocks \(B_{1}, \dots, B_{k}\) (subsets of \([n]\)) such that for each \(B_{i}\), \(f(x) \neq f(x^{B_{i}})\) and the block sensitivity of \(f\), \(\operatorname{bs}(f)\), is \(\max_{x} \operatorname{bs}(f, x)\). Theorem 2 (sensitivity conjecture). For every Boolean function \(f\), \[ \operatorname{bs}(f) \leq \operatorname{s}(f)^{4}. \] The main result is proven by a sequence of lemmas, including Cauchy's interlace theorem, which describe the eigenvalues of symmetric square matrices.