MathLabs

Worked solution: Huang's signed hypercube adjacency matrix proof of the sensitivity conjecture (2019)

Step 6 of 7: From graphs back to functions: Gotsman--Linial
In plain words

Step 5 was purely about graphs and matrices; Gotsman--Linial's equivalence now translates it back into a statement about Boolean functions. The two level sets f=0f=0 and f=1f=1 give complementary induced subgraphs of {0,1}n\{0,1\}^n, and the equivalence is formulated for the non-balanced case rather than claiming that one level set always has at least 2n−1+12^{n-1}+1 vertices.

s(f)≥deg⁡(f)s(f) \ge \sqrt{\deg(f)}
Detailed analysis

Gotsman and Linial (1992) proved the equivalence Γ(H)≥h(n) for every H with ∣V(H)∣≠2n−1\Gamma(H) \ge h(n) \text{ for every } H \text{ with } |V(H)| \ne 2^{n-1} iff s(f)≥h(deg⁡(f))s(f) \ge h(\deg(f)) for every Boolean function ff. For the former H, one of H and its complement has at least 2n−1+12^{n-1}+1 vertices; Theorem 1.1 with h(n)=nh(n) = \sqrt{n} yields s(f)≥deg⁡(f)s(f) \ge \sqrt{\deg(f)}.

Terms in this step
Monotone function
A function hh with h(n)≤h(n+1)h(n) \le h(n+1) for all nn; used here as the general lower-bound shape in the Gotsman--Linial equivalence.
Knowledge used in this step