Title: A covering graph perspective on Huang’s theorem
| Speaker: | Maxwell Levit |
| Affiliation: | University of Waterloo |
| Zoom: | Contact Soffia Arnadottir |
Abstract:
Just about a year ago, Hao Huang resolved the sensitivity conjecture by proving that any induced subgraph on more than half the vertices of the hypercube $Q_n$ has maximum degree at least $\sqrt(n)$. The key ingredient in his proof is a special $\pm 1$ signing of the adjacency matrix of $Q_n$.
One way to interpret this matrix is as a schematic for constructing the unique (up to isomorphism) 2-fold cover of $Q_n$ with girth 6. (A graph studied by Cohen and Tits 35 years earlier.)
Another interpretation of this matrix, pointed out by Terence Tao shortly after Huang’s proof, is as the bilinear form associated to a ''twisted'' ($\pm 1$ weighted) convolution operator on the space of functions on the vertices of $Q_n$.
Tao’s remarks will lead us to a Cayley graph construction of the Cohen and Tits cover, as well as some Cayley graph constructions of (seemingly new) high girth covers of cartesian products of cycles.