Unitary Signings and Induced Subgraphs of Cayley Graphs of ${\mathbb{Z}}_2^n$

Abstract

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.

12 pages, 1 figure