{
  "id": "2402.10025",
  "version": "v2",
  "published": "2024-02-15T15:45:44.000Z",
  "updated": "2024-05-30T14:07:46.000Z",
  "title": "An improved lower bound on the Shannon capacities of complements of odd cycles",
  "authors": [
    "Daniel G. Zhu"
  ],
  "comment": "7 pages, 1 figure",
  "categories": [
    "math.CO",
    "cs.IT",
    "math.IT"
  ],
  "abstract": "Improving a 2003 result of Bohman and Holzman, we show that for $n \\geq 1$, the Shannon capacity of the complement of the $2n+1$-cycle is at least $(2^{r_n} + 1)^{1/r_n} = 2 + \\Omega(2^{-r_n}/r_n)$, where $r_n = \\exp(O((\\log n)^2))$ is the number of partitions of $2(n-1)$ into powers of $2$. We also discuss a connection between this result and work by Day and Johnson in the context of graph Ramsey numbers.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2024-05-30T14:07:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "94A24",
      "05C38",
      "05C55"
    ],
    "keywords": [
      "shannon capacity",
      "lower bound",
      "odd cycles",
      "complement",
      "graph ramsey numbers"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}