Induced subgraphs of hypercubes and a proof of the sensitivity conjecture

DOI10.4007/ANNALS.2019.190.3.6MaRDI QIDQ2334869zbMATH OpenOpenAlexWikidataFDO

Authors Hao Huang

Publication date 8 November 2019

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

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

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)

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.

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

Cites work

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

Cited in

(60)

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

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)