Unitary signings and induced subgraphs of Cayley graphs of $\mathbb{Z}_2^{n}$

Noga Alon, Kai Zheng

Published 2020-03-10Version 1

Let $G$ be a Cayley graph of the elementary abelian $2$-group $\mathbb{Z}_2^{n}$ with respect to a set $S$ of size $d$. We prove 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 breakthrough 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$. Motivated by his method we define and study unitary signings of adjacency matrices of graphs, and compare them to the orthogonal signings of Huang. As a byproduct, we answer a recent question of Belardo et. al. about the spectrum of signed $5$-regular graphs.