Unitary signings and induced subgraphs of Cayley graphs of Zn2

*Advances in Combinatorics*, November. https://doi.org/10.19086/aic.17912.

### Editorial introduction

Boolean functions play an important role in many different areas of computer science. The *local sensitivity* of a Boolean function f:{0,1}n→{0,1} on an input x∈{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)≠f(x+ei), where ei 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→{0,1} on an input x∈{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≥2 and define a Boolean function f:{0,1}2k2→{0,1} as follows: the coordinates of x∈{0,1}2k2 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 k2. 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 √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 √d. In particular, when the generating set consists of the n unit vectors, the Cayley graph is the n-dimensional hypercube.