Unitary Signings and Induced Subgraphs of Cayley Graphs of
$\mathbb{Z}_2^{n}$
Advances in Combinatronics (2020)
Voir la notice de l'article provenant de la source Advances in Combinatronics website
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.
Publié le :
@article{ADVC_2020_a0,
author = {Noga Alon and Kai Zheng},
title = {Unitary {Signings} and {Induced} {Subgraphs} of {Cayley} {Graphs} of
$\mathbb{Z}_2^{n}$},
journal = {Advances in Combinatronics},
publisher = {mathdoc},
year = {2020},
language = {en},
url = {http://geodesic.mathdoc.fr/item/ADVC_2020_a0/}
}
Noga Alon; Kai Zheng. Unitary Signings and Induced Subgraphs of Cayley Graphs of
$\mathbb{Z}_2^{n}$. Advances in Combinatronics (2020). http://geodesic.mathdoc.fr/item/ADVC_2020_a0/