The sensitivity conjecture, induced subgraphs of cubes, and Clifford\n algebras

2019/07/29 by Daniel V. Mathews, Mathews, Daniel V.
Mathematics · #05C50 #15A66 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #Rings and Algebras (math.RA)

paper · pdf · doi:10.48550/arxiv.1907.12357

openalex publication_date 2019/07/29 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28

Abstract

We give another version of Huang's proof that an induced subgraph of the\nn-dimensional cube graph containing over half the vertices has maximal degree\nat least \√(n), which implies the Sensitivity Conjecture. This argument\nuses Clifford algebras of positive definite signature in a natural way. We also\nprove a weighted version of the result.\n

Related

• Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
• Huang's theorem and the exterior algebra
• Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs" [arXiv:2003.13166]
• On Induced Subgraphs of the Hamming Graph
• Induced subgraphs of powers of oriented cycles