Induced subgraphs of hypercubes and a proof of the sensitivity conjecture

DOI10.4007/ANNALS.2019.190.3.6zbMATH Open1427.05116arXiv1907.00847OpenAlexW2982703414WikidataQ87647546 ScholiaQ87647546MaRDI QIDQ2334869FDOQ2334869

Authors: Hao Huang 

Publication date: 8 November 2019

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Abstract: In this paper, we show that every $(2^{n-1}+1)$-vertex induced subgraph of the $n$-dimensional cube graph has maximum degree at least $sqrtn$. This result is best possible, and improves a logarithmic lower bound shown by Chung, F"uredi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.

Full work available at URL: https://arxiv.org/abs/1907.00847

Recommendations

• On the resolution of the sensitivity conjecture
• The equivalence of two problems on the cube
• The sensitivity conjecture, induced subgraphs of cubes, and Clifford algebras
• On the sensitivity complexity of \(k\)-uniform hypergraph properties
• On the sensitivity conjecture

zbMATH Keywords

hypercubeBoolean functioneigenvalue interlacingsensitivity conjecture

Mathematics Subject Classification ID

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

Cites Work

• On induced subgraphs of the cube
• On the degree of Boolean functions as real polynomials
• Sensitivity vs. block sensitivity of Boolean functions
• Complexity measures and decision tree complexity: a survey.
• Sensitivity versus block sensitivity of Boolean functions
• The equivalence of two problems on the cube
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Juggling Probabilities
• A New Approach to the Sensitivity Conjecture
• Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
• Properties and applications of Boolean function composition
• Title not available (Why is that?)

Cited In (61)

• Eigenpairs of adjacency matrices of balanced signed graphs
• On induced subgraph of Cartesian product of paths
• Log-concave poset inequalities
• Curvature, diameter and signs of graphs
• Maximal colourings for graphs
• Extremal results for \(C_3^-\)-free signed graphs
• Signed zero-divisor graphs over commutative rings
• The inertia bound is far from tight
• A spectral extremal problem on non-bipartite triangle-free graphs
• NEPS of complex unit gain graphs
• Turán problem of signed graph for negative odd cycle
• Counterexamples to ``A conjecture on induced subgraphs of Cayley graphs
• The sensitivity conjecture, induced subgraphs of cubes, and Clifford algebras
• Eigenvalues and critical groups of Adinkras
• Conflict complexity is lower bounded by block sensitivity
• Open problems in the spectral theory of signed graphs
• On the resolution of the sensitivity conjecture
• Signed (0,2)‐graphs with few eigenvalues and a symmetric spectrum
• Graph covers with two new eigenvalues
• Size of sets with small sensitivity: a generalization of Simon's lemma
• Title not available (Why is that?)
• Nodal domain theorems for \(p\)-Laplacians on signed graphs
• Induced subgraphs of hypercubes
• On separation between the degree of a Boolean function and the block sensitivity
• On sensitivity in bipartite Cayley graphs
• Some regular signed graphs with only two distinct eigenvalues
• On the sensitivity complexity of \(k\)-uniform hypergraph properties
• The index of signed graphs with forbidden subgraphs
• On induced subgraphs of the cube
• Combinatorics in the exterior algebra and the Bollobás two families theorem
• On the signed chromatic number of some classes of graphs
• Rainbow coloring hardness via low sensitivity polymorphisms
• An Optimal Separation of Randomized and Quantum Query Complexity
• The equivalence of two problems on the cube
• Induced subgraphs of product graphs and a generalization of Huang's theorem
• Signed graphs with maximal index
• Critical properties and complexity measures of read-once Boolean functions
• An induced subgraph of the Hamming graph with maximum degree 1
• Sensitivities and block sensitivities of elementary symmetric Boolean functions
• Sensitivity, affine transforms and quantum communication complexity
• There is no going back: properties of the non-backtracking Laplacian
• On the Decision Tree Complexity of Threshold Functions
• On induced subgraphs of the Hamming graph
• On the sensitivity complexity of \(k\)-uniform hypergraph properties
• Induced subgraphs of powers of oriented cycles
• A decomposition of signed graphs with two eigenvalues
• Unit gain graphs with two distinct eigenvalues and systems of lines in complex space
• On bounds of \(A_\alpha\)-eigenvalue multiplicity and the rank of a complex unit gain graph
• Induced subgraph and eigenvalues of some signed graphs
• Collectively canalizing Boolean functions
• Interview with Yufei Zhao
• Approximate Degree in Classical and Quantum Computing
• Tight bounds on sensitivity and block sensitivity of some classes of transitive functions
• Critical groups of strongly regular graphs and their generalizations
• On the central levels problem
• Complete signed graphs with largest maximum or smallest minimum eigenvalue
• Title not available (Why is that?)
• On the relationship between energy complexity and other Boolean function measures
• Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
• Coloring the normalized Laplacian for oriented hypergraphs
• The maximum spectral radius of non-bipartite graphs forbidding short odd cycles

This page was built for publication: Induced subgraphs of hypercubes and a proof of the sensitivity conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2334869)