Combinatorics and theoretical computer science

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

Hao Huang · Six-page arXiv manuscript

6 pages9 claims indexed16 referencesManuscript 2019-08-29

The proposed argument

A recursive signed adjacency matrix has eigenvalues +sqrt(n) and -sqrt(n). Interlacing transfers a lower eigenvalue bound to any majority-size induced subcube graph; a maximum-coordinate estimate bounds this eigenvalue by maximum degree. The paper relates cube graphs to Boolean sensitivity and invokes a degree bound for block sensitivity. The spectral equality example is separate from the maximum-degree equality construction.

The reviewed edition is the six-page arXiv v2, dated 29 August 2019. The original TeX bytes, including CRLF line endings, are retained. The neutral map indexes native statements and cited inputs; an index entry is not a claim of completed review.

Reading order

    Follow the dependencies

    Open the full map ↗

    Select a claim to see its prerequisites and consumers. Edge labels distinguish proof inputs, source references, background and exclusions.

    Your independent assessment

    Track the signed-matrix recursion, principal-submatrix comparison and Boolean-function deductions. Distinguish the two sharpness claims and the hypotheses imported from external sources.

    Notes stay on this device.