Unitary signings and induced subgraphs of cayley graphs of ℤn2

Noga Alon, Kai Zheng

Research output: Contribution to journalArticlepeer-review

Abstract

Let G be the Cayley graph of the elementary abelian 2-group ℤn2 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 √d. This is deduced from the recent breakthrough result of Huang who proved the above for the n-hypercube Qn, 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, Cioabă, Koolen, and Wang about the spectrum of signed 5-regular graphs.

Original languageEnglish (US)
JournalAdvances in Combinatorics
Volume2021
Issue number1
DOIs
StatePublished - 2021

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Unitary signings and induced subgraphs of cayley graphs of ℤ<sup>n</sup>2'. Together they form a unique fingerprint.

Cite this