#spectral-graph-theory

Prove that every set of more than $2^{n-1}$ vertices of the $n$-dimensional hypercube induces a subgraph with a vertex of degree at least $\sqrt{n}$. Gotsman and Linial showed that this implies the sensitivity conjecture, that the degree and block sensitivity of a Boolean function are bounded by a…