{
  "id": "2105.10971",
  "version": "v1",
  "published": "2021-05-23T16:43:49.000Z",
  "updated": "2021-05-23T16:43:49.000Z",
  "title": "Independent sets in subgraphs of a shift graph",
  "authors": [
    "Andrii Arman",
    "Vojtěch Rödl",
    "Marcelo Tadeu Sales"
  ],
  "comment": "10 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "Erd\\\"{o}s, Hajnal and Szemer\\'{e}di proved that any subset $G$ of vertices of a shift graph $\\text{Sh}_{n}^{k}$ has the property that the independence number of the subgraph induced by $G$ satisfies $\\alpha(\\text{Sh}_{n}^{k}[G])\\geq \\left(\\frac{1}{2}-\\varepsilon\\right)|G|$, where $\\varepsilon\\to 0$ as $k\\to \\infty$. In this note we show that for $k=2$ and $n \\to \\infty$ there are graphs $G\\subseteq \\binom{[n]}{2}$ with $\\alpha(\\text{Sh}_{n}^{k}[G])\\leq \\left(\\frac{1}{4}+o(1)\\right)|G|$, and $\\frac{1}{4}$ is best possible. We also consider a related problem for infinite shift graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-05-23T16:43:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69"
    ],
    "keywords": [
      "independent sets",
      "infinite shift graphs",
      "independence number",
      "related problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}