Huang's theorem and the exterior algebra

2019/07/25 by Роман Карасев, Karasev, Roman
Computer Science · Mathematics · #05C50 #15A66 #15A75 #Advanced Topics in Algebra #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Rings and Algebras (math.RA)

paper · pdf · doi:10.48550/arxiv.1907.11175

openalex publication_date 2019/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this note we give a version of Hao Huang's proof of the sensitivity conjecture, shedding some light on the origin of the magical matrix A in that proof. For the history of the subject and the importance of this conjecture to the study of boolean functions, we refer to the original paper. Here we only state the main result: Consider the boolean cube Q_n=\0,1\ⁿ as a graph, whose edges connect pairs of vertices differing in one coordinate. Then any its induced subgraph on greater than 2^n-1 (the half) vertices has degree of some vertex at least √(n).

Related

• The sensitivity conjecture, induced subgraphs of cubes, and Clifford\n algebras
• Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
• Induced subgraphs of powers of oriented cycles
• On Induced Subgraph of Cartesian Product of Paths
• Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs" [arXiv:2003.13166]