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
No substantive issue found

Scope: Six selected proof components, their recorded prerequisites and one full-source Astra adjudication; external proofs are not all audited.

Headline results: The hypercube bound and sensitivity conclusions are supported in the checked scope. No substantive defect was established.

The one-dimensional interlacing endpoint needs a direct check. Separately attributed arguments verify square sharpness and the needed sensitivity implication; these do not authenticate every historical citation or certify the whole manuscript.

An assessment of the stated scope, not a formal proof certificate. What the labels mean ↗

Panel commentary

This page contains assessments and source-audit conclusions. Human comparison remains pending. Return to the reading view to form your own assessment first.

Decisions by result

Open the decorated graph ↗

Double borders mark terminal results in the recorded proof graph. Green, yellow and red summarize scoped adjudications. Yellow also marks unadjudicated claims and unresolved dependencies; a paper-level assessment does not fill in missing node decisions.

SOURCE-ADJUDICATED AI REVIEW / PUBLISHED 15 NOVEMBER 2026

The Sensitivity Conjecture

Hao Huang, Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. Six-page arXiv manuscript, 1907.00847v2.

The main hypercube bound and the sensitivity conclusions are supported in the checked scope. Astra confirms only a trivial endpoint omission in the printed interlacing invocation, not a false theorem. A separately attributed, checked construction verifies perfect-square sharpness; external-source authentication remains a distinct limit.

Reviewed component Source-adjudicated result
Signed-matrix spectrum Supported: A_n squared is nI; trace fixes multiplicities.
Maximum-degree comparison Supported with the standard loopless-graph convention.
Hypercube lower bound Supported; handle n = 1 directly. Square sharpness separately verified.
Spectral strengthening Supported; the star proves eigenvalue sharpness for every n.
Sensitivity versus degree Deduction and a separate direct parity argument checked. Full cited equivalence not audited.
Block sensitivity Quartic deduction checked; precise Tal statement and date sourced, full external proof not audited.

Each of six targets received independent Sol and Fable 5.2 assessments at high effort. Dependent waves opened only after source checks. Astra at max effort adjudicated the selected remaining issues using all six original page images. Model labels, original failures and costs are preserved separately from the conclusions below.

This is an identified, familiar development paper, with possible training-set exposure. No human expert grade, blind benchmark, experimental validation or formal proof certificate is claimed. Only the scopes listed here were audited; the neutral reading index and panel decision map are separate artifacts.


The proof chain and its qualifications

Signed matrices and the hypercube bound

The recursive symmetric matrix satisfies A_(n)^(2) = nI. Its zero trace gives equal multiplicities for the two eigenvalues, ±sqrt(n). The absolute-value matrix is precisely cube adjacency. For an induced vertex set H, the corresponding principal submatrix has a largest eigenvalue at least sqrt(n) by interlacing; the maximum-coordinate eigenvector estimate bounds that eigenvalue by the maximum degree of H. The interlacing index is 2^(n-1), as required.

The one-dimensional endpoint and spectral sharpness

The stated interlacing lemma assumes a proper principal submatrix; at n = 1, H is the whole K_(2). Directly, its maximum degree is 1. This elementary endpoint completion preserves the theorem. For the spectral remark, x^(T)A_(H)x ≤ |x|^(T)|A_(H)||x| gives the additional Rayleigh comparison. All even vertices plus one odd vertex induce a star K_(1,n) and 2^(n-1) - n isolates. The largest eigenvalue is sqrt(n), but the maximum degree is n: this is a different sharpness statement.

A separately attributed maximum-degree equality construction

For n = k², take F to be the AND of k ORs, each on k disjoint variables. Its sensitivity is k and its top multilinear coefficient is ±1. Put f = 1 - 2F and χ(x) = (-1)^(Σx). Then |E[fχ]| = 2^(1-n). Choose the sign so g = ±fχ has positive mean. The set H = {g = 1} has exactly 2^(n-1) + 1 vertices. Along an edge, g stays constant exactly when F changes, so every degree in H is at most k. The lower bound forces equality. This is an orchestrator-proposed verification, independently checked in the adjudication; it does not authenticate the original 1988 construction or claim historical novelty.

Sensitivity and block sensitivity

The printed sensitivity deduction uses the Gotsman-Linial equivalence and the majority part of the cube. A separate direct check restricts F to a highest-degree monomial’s d variables; its coefficient survives and sensitivity cannot increase. Multiplication of its signed output by parity produces an unbalanced partition. Internal edges in either part are exactly sensitive edges of F, so the cube bound gives s(F) ≥ sqrt(d). Constants are immediate. With Tal’s imported bound, the remaining deduction is bs(F) ≤ deg(F)² ≤ s(F)^(4).

Astra independently verified the proposed parity construction and sensitivity implication. It also supplied a shorter lower-bound check: the positive eigenspace has dimension N/2 and the coordinate subspace supported on H has dimension N/2 + 1, so their intersection contains a nonzero vector. Restriction yields the eigenvalue sqrt(n) for A_H directly, including n = 1. These are new verification arguments, not claims about what the original author wrote.


Evidence, coverage and service cost

External inputs and historical scope

Huang’s documented receipt date is 20 July 2019; the reviewed arXiv v2 is dated 29 August 2019. These dates have different roles. The Annals record supplies the receipt date. The 1988 sharpness source and the full 1992 Gotsman-Linial proof were not retrieved for a complete audit. Publisher metadata supports the latter’s date and subject, while the direct argument above verifies only the implication needed here. Cauchy interlacing is an explicitly identified standard input, not a claim that Fisk’s article was fully audited.

Tal’s primary manuscript, Properties and applications of boolean function composition, explicitly gives the coefficient-one block-sensitivity bound in Theorem 4, restated in Section 6. Its statement, definitions and amplification argument were inspected; the ECCC 2012/163 record establishes pre-cutoff availability. The retained PDF came from a university mirror after the direct download failed. Exact edition-byte identity and a complete audit of all 26 pages and imported results are not claimed.

Independent checks and remaining limits

Exact finite checks cover A_(n) through n = 7; all 11,501 required-size induced subsets through n = 4; all 276 Boolean functions through three variables; and the equality construction for k = 1, 2, 3, 4. These calculations check examples and conventions, not the general proofs. Survey history, every complexity-measure equivalence and the open questions were not assigned individual reviews.

Of 13 native responses, 11 passed the automatic gates; 2 needed explicit editorial reconciliation. One Sol response used metadata or paraphrases as source quotations. Astra associated an explicitly background reference with unresolved citation findings in a field reserved for proof use. Only citation bindings and that association array changed; the original failures and mathematical judgments are retained. Local reviewer uncertainty about absent external texts was kept distinct from a false theorem.

Accounted API use USD
12 independent Sol/Fable assessments 1.116735
1 Astra max adjudication(s) 0.727560
Total for this paper 1.844295
Allocated ceiling within shared $25 12.500000

Provider-reported usage at frozen rates, rounded upward per durable attempt; includes invalid responses. These figures are not provider invoices or total service costs. First submission to final collection: 37.9 minutes, including staged waiting and operator work; not an SLA or labor-cost measurement. No retries or synchronous fallback were used.

Qualification judgment: useful evidence for supervised review of proof-heavy theoretical computer science. This is a combinatorial proof with complexity-theory consequences, not a test of empirical systems, arbitrary algorithms or software correctness. Broader advertising needs unfamiliar papers, negative controls and independent expert grading.

Downloads and publication record

Original review PDF · Structured assessments · Decision records · Verification results

The owner authorized publication after the internal trial. The downloadable PDF is the unchanged original report and retains its internal-qualification heading. This web edition changes that heading and adds these download links; mathematical findings are unchanged. The public package excludes private service orders, customer records, request logs and reasoning streams. Publication is not a new benchmark run or an expansion to unrestricted STEM review.

Source record

Additional supporting archive items are identified in the original report. View the manuscript hashes and repository snapshot.

Download panel reportDownload curated review packageSeparate reading packet