Unitary signings and induced subgraphs of Cayley graphs of \(\mathbb{Z}_2^{n}\)

Boolean functions play an important role in many different areas of computer science. The local sensitivity of a Boolean function \(f:\{0,1\}^n\to \{0,1\}\) on an input \(x\in\{0,1\}^n\) is the number of coordinates whose flip changes the value of \(f(x)\), i.e., the number of i’s such that \(f(x)\not=f(x+e_i)\), where \(e_i\) is the \(i\)-th unit vector. The sensitivity of a Boolean function is its maximum local sensitivity. In other words, the sensitivity measures the robustness of a Boolean function with respect to a perturbation of its input. Another notion that measures the robustness is block sensitivity. The local block sensitivity of a Boolean function \(f:\{0,1\}^n\to \{0,1\}\) on an input \(x\in\{0,1\}^n\) is the number of disjoint subsets \(I\) of \(\{1,..,n\}\) such that flipping the coordinates indexed by \(I\) changes the value of \(f(x)\), and the block sensitivity of \(f\) is its maximum local block sensitivity. Since the local block sensitivity is at least the local sensitivity for any input \(x\), the block sensitivity of \(f\) is at least the sensitivity of \(f\).

The next example demonstrates that the block sensitivity of a Boolean function is not linearly bounded by its sensitivity. Fix an integer \(k\ge 2\) and define a Boolean function \(f:\{0,1\}^{2k^2}\to\{0,1\}\) as follows: the coordinates of \(x\in\{0,1\}^{2k^2}\) are split into \(k\) blocks of size \(2k\) each and \(f(x)=1\) if and only if at least one of the blocks contains exactly two entries equal to one and these entries are consecutive. While the sensitivity of the function \(f\) is \(2k\), its block sensitivity is \(k^2\). The Sensitivity Conjecture, made by Nisan and Szegedy in 1992, asserts that the block sensitivity of a Boolean function is polynomially bounded by its sensivity. The example above shows that the degree of such a polynomial must be at least two.

The Sensitivity Conjecture has been recently proven by Huang in Annals of Mathematics 190 (2019), 949-955. He proved the following combinatorial statement that implies the conjecture (with the degree of the polynomial equal to four): any subset of more than half of the vertices of the \(n\)-dimensional cube \(\{0,1\}^n\) induces a subgraph that contains a vertex with degree at least \(\sqrt{n}\). The present article extends this result as follows: every Cayley graph with the vertex set \(\{0,1\}^n\) and any generating set of size \(d\) (the vertex set is viewed as a vector space over the binary field) satisfies that any subset of more than half of its vertices induces a subgraph that contains a vertex of degree at least \(\sqrt{d}\). In particular, when the generating set consists of the \(n\) unit vectors, the Cayley graph is the \(n\)-dimensional hypercube.