Title: Signings and induced subgraphs of the Hypercube
| Speaker: | Maxwell Levit |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
Just over a month ago, Hao Haung resolved the sensitivity conjecture, a 30 year-old question about the complexity of boolean functions. The crux of this work was to prove that any $2^{n-1}+1$ vertex induced subgraph of the hypercube $Q^n$ has maximum degree at least $\sqrt{n}$. The proof is a straightforward application of Cauchy's interlacing theorem, along with a clever signing of the adjacency matrix of the hypercube.
We will briefly introduce this conjecture, present Haung's proof, and then discuss a combinatorial interpretation of the signing. In fact, this is exactly the signing I spoke about last year when discussing an interesting 2-fold cover of the hypercube.