Induced subgraphs of hypercubes and a proof of the sensitivity conjecture

DOI10.4007/annals.2019.190.3.6zbMath1427.05116arXiv1907.00847OpenAlexW2982703414WikidataQ87647546 ScholiaQ87647546MaRDI QIDQ2334869

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

hypercube Boolean function sensitivity conjecture eigenvalue interlacing

Mathematics Subject Classification ID

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

Related Items (47)

Combinatorics in the exterior algebra and the Bollobás Two Families Theorem ⋮ Unit gain graphs with two distinct eigenvalues and systems of lines in complex space ⋮ An Optimal Separation of Randomized and Quantum Query Complexity ⋮ On the Decision Tree Complexity of Threshold Functions ⋮ Induced subgraphs of powers of oriented cycles ⋮ Interview with Yufei Zhao ⋮ Approximate Degree in Classical and Quantum Computing ⋮ On the signed chromatic number of some classes of graphs ⋮ On sensitivity in bipartite Cayley graphs ⋮ On induced subgraphs of the Hamming graph ⋮ Induced subgraphs of product graphs and a generalization of Huang's theorem ⋮ An induced subgraph of the Hamming graph with maximum degree 1 ⋮ There is no going back: properties of the non-backtracking Laplacian ⋮ On bounds of \(A_\alpha\)-eigenvalue multiplicity and the rank of a complex unit gain graph ⋮ Induced subgraph and eigenvalues of some signed graphs ⋮ Complete signed graphs with largest maximum or smallest minimum eigenvalue ⋮ Critical groups of strongly regular graphs and their generalizations ⋮ Signed (0,2)‐graphs with few eigenvalues and a symmetric spectrum ⋮ Nodal domain theorems for \(p\)-Laplacians on signed graphs ⋮ Collectively canalizing Boolean functions ⋮ The index of signed graphs with forbidden subgraphs ⋮ Extremal results for \(C_3^-\)-free signed graphs ⋮ A spectral extremal problem on non-bipartite triangle-free graphs ⋮ NEPS of complex unit gain graphs ⋮ On the central levels problem ⋮ On the resolution of the sensitivity conjecture ⋮ Unnamed Item ⋮ Conflict complexity is lower bounded by block sensitivity ⋮ Graph covers with two new eigenvalues ⋮ Coloring the normalized Laplacian for oriented hypergraphs ⋮ Unnamed Item ⋮ Open problems in the spectral theory of signed graphs ⋮ Signed graphs with maximal index ⋮ Critical properties and complexity measures of read-once Boolean functions ⋮ On the relationship between energy complexity and other Boolean function measures ⋮ Sensitivity, affine transforms and quantum communication complexity ⋮ Sensitivities and block sensitivities of elementary symmetric Boolean functions ⋮ Tight bounds on sensitivity and block sensitivity of some classes of transitive functions ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Counterexamples to “A conjecture on induced subgraphs of Cayley graphs” ⋮ The maximum spectral radius of non-bipartite graphs forbidding short odd cycles ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ The sensitivity conjecture, induced subgraphs of cubes, and Clifford algebras ⋮ Some regular signed graphs with only two distinct eigenvalues ⋮ Eigenvalues and critical groups of Adinkras ⋮ A decomposition of signed graphs with two eigenvalues ⋮ On separation between the degree of a Boolean function and the block sensitivity

Cites Work

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