The sensitivity conjecture, induced subgraphs of cubes, and Clifford algebras (Q2098195): Difference between revisions

Summary: We give another version of Huang's proof that an induced subgraph of the \(n\)-dimensional cube graph containing over half the vertices has maximal degree at least \(\sqrt{n}\), which implies the Sensitivity Conjecture. This argument uses Clifford algebras of positive definite signature in a natural way. We also prove a weighted version of the result.