Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. (English) Zbl 1427.05116

Huang, Hao

Ann. Math. (2) 190, No. 3, 949-955 (2019).

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.

Reviewer: Colton Magnant (Morrow)

MSC:

05C35	Extremal problems in graph theory
05C07	Vertex degrees
05C60	Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Keywords:

sensitivity conjecture; Boolean function; hypercube; eigenvalue interlacing

References:

[1]	Ambainis, A.; Sun, X., New separation between \(s(f)\) and \(bs(f)\), Electronic Colloquium on Computational Complexity (ECCC), 18, 116 pp. (2011)
[2]	Buhrman, Harry; de Wolf, Ronald, Complexity measures and decision tree complexity: a survey. Complexity and Logic, Theoret. Comput. Sci.. Theoretical Computer Science, 288, 21-43 (2002) · Zbl 1061.68058
[3]	Chung, F. R. K.; F\`“{u}redi, Zolt\'”{a}n; Graham, R. L.; Seymour, P., On induced subgraphs of the cube, J. Combin. Theory Ser. A. Journal of Combinatorial Theory. Series A, 49, 180-187 (1988) · Zbl 0653.05037
[4]	Drucker, A., A note on a communication game (2017)
[5]	Fisk, S., A very short proof of {C}auchy’s interlace theorem for eigenvalues of {H}ermitian matrices, Amer. Math. Monthly, 112, 118 pp. (2005) · Zbl 1078.60011
[6]	Gilmer, Justin; Kouck\'{y}, Michal; Saks, Michael, A new approach to the sensitivity conjecture. I{TCS}’15—{P}roceedings of the 6th {I}nnovations in {T}heoretical {C}omputer {S}cience, 247-254 (2015) · Zbl 1364.68197
[7]	Gopalan, Parikshit; Nisan, Noam; Servedio, Rocco A.; Talwar, Kunal; Wigderson, Avi, Smooth {B}oolean functions are easy: efficient algorithms for low-sensitivity functions. I{TCS}’16—{P}roceedings of the 2016 {ACM} {C}onference on {I}nnovations in {T}heoretical {C}omputer {S}cience, 59-70 (2016) · Zbl 1334.68068
[8]	Gopalan, Parikshit; Servedio, Rocco A.; Wigderson, Avi, Degree and sensitivity: tails of two distributions. 31st {C}onference on {C}omputational {C}omplexity, LIPIcs. Leibniz Int. Proc. Inform., 50, 13-23 (2016) · Zbl 1380.68223
[9]	Gotsman, C.; Linial, N., The equivalence of two problems on the cube, J. Combin. Theory Ser. A. Journal of Combinatorial Theory. Series A, 61, 142-146 (1992) · Zbl 0769.05050
[10]	Hatami, P.; Kulkarni, R.; Pankratov, D., Variations on the Sensitivity Conjecture, Theory of Computing Library, Graduate Surveys, 4, 1-27 (2011)
[11]	Kenyon, Claire; Kutin, Samuel, Sensitivity, block sensitivity, and {\(l\)}-block sensitivity of {B}oolean functions, Inform. and Comput.. Information and Computation, 189, 43-53 (2004) · Zbl 1072.68047
[12]	Nisan, N., {CREW PRAM}s and decision trees. Proc. 21st STOC, 327-335 (1989)
[13]	Nisan, Noam; Szegedy, M\'{a}ri\'{o}, On the degree of {B}oolean functions as real polynomials. Special Issue on Circuit Complexity, Comput. Complexity, 4, 301-313 (1994) · Zbl 0829.68047
[14]	Rubinstein, David, Sensitivity vs. block sensitivity of {B}oolean functions, Combinatorica. Combinatorica. An International Journal on Combinatorics and the Theory of Computing, 15, 297-299 (1995) · Zbl 0837.68080
[15]	Tal, Avishay, Properties and applications of {B}oolean function composition. I{TCS}’13—{P}roceedings of the 2013 {ACM} {C}onference on {I}nnovations in {T}heoretical {C}omputer {S}cience, 441-454 (2013) · Zbl 1361.68094
[16]	Virza, Madars, Sensitivity versus black sensitivity of {B}oolean functions, Inform. Process. Lett.. Information Processing Letters, 111, 433-435 (2011) · Zbl 1260.68163