{
  "id": "2012.02159",
  "version": "v1",
  "published": "2020-12-03T18:44:52.000Z",
  "updated": "2020-12-03T18:44:52.000Z",
  "title": "Extremal density for sparse minors and subdivisions",
  "authors": [
    "John Haslegrave",
    "Jaehoon Kim",
    "Hong Liu"
  ],
  "comment": "33 pages, 6 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "We prove an asymptotically tight bound on the extremal density guaranteeing subdivisions of bounded-degree bipartite graphs with a mild separability condition. As corollaries, we answer several questions of Reed and Wood on embedding sparse minors. Among others, $\\bullet$ $(1+o(1))t^2$ average degree is sufficient to force the $t\\times t$ grid as a topological minor; $\\bullet$ $(3/2+o(1))t$ average degree forces every $t$-vertex planar graph as a minor, and the constant $3/2$ is optimal, furthermore, surprisingly, the value is the same for $t$-vertex graphs embeddable on any fixed surface; $\\bullet$ a universal bound of $(2+o(1))t$ on average degree forcing every $t$-vertex graph in any nontrivial minor-closed family as a minor, and the constant 2 is best possible by considering graphs with given treewidth.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-12-03T18:44:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C83",
      "05C35"
    ],
    "keywords": [
      "sparse minors",
      "vertex graph",
      "mild separability condition",
      "average degree forces",
      "bounded-degree bipartite graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 33,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}