The sensitivity conjecture, induced subgraphs of cubes, and Clifford algebras (Q2098195)

From MaRDI portal
Revision as of 08:50, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
scientific article
Language Label Description Also known as
English
The sensitivity conjecture, induced subgraphs of cubes, and Clifford algebras
scientific article

    Statements

    The sensitivity conjecture, induced subgraphs of cubes, and Clifford algebras (English)
    0 references
    0 references
    17 November 2022
    0 references
    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.
    0 references
    sensitivity conjecture
    0 references
    Clifford algebras
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references