{
  "id": "2401.15403",
  "version": "v1",
  "published": "2024-01-27T12:58:41.000Z",
  "updated": "2024-01-27T12:58:41.000Z",
  "title": "Extremal density for subdivisions with length or sparsity constraints",
  "authors": [
    "Jaehoon Kim",
    "Hong Liu",
    "Yantao Tang",
    "Guanghui Wang",
    "Donglei Yang",
    "Fan Yang"
  ],
  "comment": "34 pages, 2 pages, Comments welcome!",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a graph $H$, a balanced subdivision of $H$ is obtained by replacing all edges of $H$ with internally disjoint paths of the same length. In this paper, we prove that for any graph $H$, a linear-in-$e(H)$ bound on average degree guarantees a balanced $H$-subdivision. This strengthens an old result of Bollob\\'as and Thomason, and resolves a question of Gil-Fern\\'{a}ndez, Hyde, Liu, Pikhurko and Wu. We observe that this linear bound on average degree is best possible whenever $H$ is logarithmically dense. We further show that this logarithmic density is the critical threshold: for many graphs $H$ below this density, its subdivisions are forcible by a sublinear bound in $e(H)$ on average degree. We provide such examples by proving that the subdivisions of any almost bipartite graph $H$ with sublogarithmic density are forcible by a sublinear-in-$e(H)$ bound on average degree, provided that $H$ satisfies some additional separability condition.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-01-27T12:58:41.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "subdivision",
      "sparsity constraints",
      "extremal density",
      "average degree guarantees",
      "additional separability condition"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}