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

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.


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


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.