Unitary signings and induced subgraphs of Cayley graphs of Z₂^n

DOI10.19086/AIC.17912MaRDI QIDQ5144437zbMATH OpenOpenAlexFDO

Authors

Publication date 16 January 2021

Published in Advances in Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2003.04926

zbMATH Keywords

sensitivity conjecture of Nisan and Szegedy, cubelike graphs

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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 $sqrtd$. 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.

Recommendations

• On sensitivity in bipartite Cayley graphs
• Counterexamples to ``A conjecture on induced subgraphs of Cayley graphs
• Induced subgraph and eigenvalues of some signed graphs
• Induced subgraphs of product graphs and a generalization of Huang's theorem
• On the unitary Cayley graphs of matrix algebras

Cited in

(13)

• On the forcing matching numbers of prisms of graphs
• Unit gain graphs with two distinct eigenvalues and systems of lines in complex space
• Unitary Cayley meet signed graphs
• On sensitivity in bipartite Cayley graphs
• Counterexamples to ``A conjecture on induced subgraphs of Cayley graphs
• Unitary Addition Cayley Ring Signed Graphs *
• Subsets of Cayley graphs that induce many edges
• Induced subgraphs of product graphs and a generalization of Huang's theorem
• Induced subgraph and eigenvalues of some signed graphs
• scientific article; zbMATH DE number 7733107 (Why is no real title available?)
• On induced subgraph of Cartesian product of paths
• The inertia bound is far from tight
• Sensitivity and Hamming graphs

This page was built for publication: Unitary signings and induced subgraphs of Cayley graphs of \(\mathbb{Z}_2^n\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144437)