Unitary Signings and Induced subgraphs of Abelian Cayley graphs

Unitary Signings and Induced subgraphs of Abelian Cayley graphs

-
Noga Alon, Princeton University

What's Happening in Fine Hall

Zoom link: https://princeton.zoom.us/j/93918876391

Passcode: 803011

Let G be a Cayley graph of the elementary abelian 2-group Z_2^n with respect to a set S of size d. In joint work with Kai Zheng we show that for any such G,S and d, the maximum degree of any induced subgraph of G on any set of more than half the vertices is at least \sqrt d. This is deduced from the recent beautiful result of Huang who proved the above for the n-hypercube Q^n, in which the set of generators S is the set of all vectors of Hamming weight 1, establishing the sensitivity conjecture of Nisan and Szegedy. Motivated by his method we define and study unitary signings of adjacency
matrices of graphs, and compare them to the orthogonal signings of Huang. Subsequent work regarding more general Cayley graphs will be mentioned as well.