{
  "id": "2003.04926",
  "version": "v1",
  "published": "2020-03-10T18:46:57.000Z",
  "updated": "2020-03-10T18:46:57.000Z",
  "title": "Unitary signings and induced subgraphs of Cayley graphs of $\\mathbb{Z}_2^{n}$",
  "authors": [
    "Noga Alon",
    "Kai Zheng"
  ],
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-03-10T18:46:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "cayley graph",
      "induced subgraph",
      "study unitary signings",
      "orthogonal signings",
      "elementary abelian"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}