{
  "id": "1903.10631",
  "version": "v1",
  "published": "2019-03-25T23:16:03.000Z",
  "updated": "2019-03-25T23:16:03.000Z",
  "title": "More on the extremal number of subdivisions",
  "authors": [
    "David Conlon",
    "Oliver Janzer",
    "Joonkyung Lee"
  ],
  "comment": "20 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a graph $H$, the extremal number $\\mathrm{ex}(n,H)$ is the largest number of edges in an $H$-free graph on $n$ vertices. We make progress on a number of conjectures about the extremal number of bipartite graphs. First, writing $K'_{s,t}$ for the subdivision of the bipartite graph $K_{s,t}$, we show that $\\mathrm{ex}(n, K'_{s,t}) = O(n^{3/2 - \\frac{1}{2s}})$. This proves a conjecture of Kang, Kim and Liu and is tight up to the implied constant for $t$ sufficiently large in terms of $s$. Second, for any integers $s, k \\geq 1$, we show that $\\mathrm{ex}(n, L) = \\Theta(n^{1 + \\frac{s}{sk+1}})$ for a particular graph $L$ depending on $s$ and $k$, answering another question of Kang, Kim and Liu. This result touches upon an old conjecture of Erd\\H{o}s and Simonovits, which asserts that every rational number $r \\in (1,2)$ is realisable in the sense that $\\mathrm{ex}(n,H) = \\Theta(n^r)$ for some appropriate graph $H$, giving infinitely many new realisable exponents and implying that $1 + 1/k$ is a limit point of realisable exponents for all $k \\geq 1$. Writing $H^k$ for the $k$-subdivision of a graph $H$, this result also implies that for any bipartite graph $H$ and any $k$, there exists $\\delta > 0$ such that $\\mathrm{ex}(n,H^{k-1}) = O(n^{1 + 1/k - \\delta})$, partially resolving a question of Conlon and Lee. Third, extending a recent result of Conlon and Lee, we show that any bipartite graph $H$ with maximum degree $r$ on one side which does not contain $C_4$ as a subgraph satisfies $\\mathrm{ex}(n, H) = o(n^{2 - 1/r})$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-03-25T23:16:03.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "extremal number",
      "bipartite graph",
      "subdivision",
      "realisable exponents",
      "limit point"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}