{
  "id": "2102.11104",
  "version": "v1",
  "published": "2021-02-22T15:25:23.000Z",
  "updated": "2021-02-22T15:25:23.000Z",
  "title": "Minimum degree stability of $H$-free graphs",
  "authors": [
    "Freddie Illingworth"
  ],
  "comment": "12 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given an $(r + 1)$-chromatic graph $H$, the fundamental edge stability result of Erd\\H{o}s and Simonovits says that all $n$-vertex $H$-free graphs have at most $(1 - 1/r + o(1)) \\binom{n}{2}$ edges, and any $H$-free graph with that many edges can be made $r$-partite by deleting $o(n^{2})$ edges. Here we consider a natural variant of this -- the minimum degree stability of $H$-free graphs. In particular, what is the least $c$ such that any $n$-vertex $H$-free graph with minimum degree greater than $cn$ can be made $r$-partite by deleting $o(n^{2})$ edges? We determine this least value for all 3-chromatic $H$ and for very many non-3-colourable $H$ (all those in which one is commonly interested) as well as bounding it for the remainder. This extends the Andr\\'{a}sfai-Erd\\H{o}s-S\\'{o}s theorem and work of Alon and Sudakov.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-02-22T15:25:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35"
    ],
    "keywords": [
      "free graph",
      "minimum degree stability",
      "fundamental edge stability result",
      "minimum degree greater",
      "chromatic graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}