Algebraic Graph Theory Seminar - Maxwell Levit

Title: Signings and induced subgraphs of the Hypercube

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.