huang_sensitivity_theorem
Provedsensitivity_theorem
Theorem 1.1 (Huang 2019): Every induced subgraph of the n-dimensional hypercube Q_n on more than 2^(n-1) vertices contains some vertex of degree at least sqrt(n), equivalently, n <= deg(v)^2.
Preamble
import Definitions.Def_Hypercube
/-- **Theorem 1.1 (Huang 2019).** Every induced subgraph of the n-dimensional hypercube
on more than `2^(n-1)` vertices contains some vertex of degree at least `√n`
(equivalently, `n ≤ deg(v)²`). -/
Formal statement
theorem huang_sensitivity_theorem :
∀ (n : ℕ), 0 < n → ∀ (S : Finset (Fin n → Bool)), 2 ^ (n - 1) < S.card →
∃ v ∈ S, n ≤ Hypercube.degreeIn n S v ^ 2 := by sorrySource
Huang, Hao. "Induced subgraphs of hypercubes and a proof of the sensitivity conjecture." Annals of Mathematics 190.3 (2019): 949-955.