{
  "id": "2109.06152",
  "version": "v1",
  "published": "2021-09-13T17:46:33.000Z",
  "updated": "2021-09-13T17:46:33.000Z",
  "title": "Enumerating independent sets in Abelian Cayley graphs",
  "authors": [
    "Aditya Potukuchi",
    "Liana Yepremyan"
  ],
  "comment": "21 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We show that any connected Cayley graph $\\Gamma$ on an Abelian group of order $2n$ and degree $\\tilde{\\Omega}(\\log n)$ has at most $2^{n+1}(1 + o(1))$ independent sets. This bound is tight up to to the $o(1)$ term when $\\Gamma$ is bipartite. Our proof is based on Sapozhenko's graph container method and uses the Pl\\\"{u}nnecke-Rusza-Petridis inequality from additive combinatorics.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-09-13T17:46:33.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "abelian cayley graphs",
      "enumerating independent sets",
      "sapozhenkos graph container method",
      "connected cayley graph",
      "abelian group"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}