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 and give complementary induced subgraphs of , and the equivalence is formulated for the non-balanced case rather than claiming that one level set always has at least vertices.
Detailed analysis
Gotsman and Linial (1992) proved the equivalence iff for every Boolean function . For the former H, one of H and its complement has at least vertices; Theorem 1.1 with yields .
- Monotone function
- A function with for all ; used here as the general lower-bound shape in the Gotsman--Linial equivalence.