{
  "id": "2004.14139",
  "version": "v1",
  "published": "2020-04-29T12:41:12.000Z",
  "updated": "2020-04-29T12:41:12.000Z",
  "title": "The size-Ramsey number of short subdivisions",
  "authors": [
    "Nemanja Draganić",
    "Michael Krivelevich",
    "Rajko Nenadov"
  ],
  "comment": "12 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "The $r$-size-Ramsey number $\\hat{R}_r(H)$ of a graph $H$ is the smallest number of edges a graph $G$ can have, such that for every edge-coloring of $G$ with $r$ colors there exists a monochromatic copy of $H$ in $G$. The notion of size-Ramsey numbers has been introduced by Erd\\H{o}s, Faudree, Rousseau and Schelp in 1978, and has attracted a lot of attention ever since. For a graph $H$, we denote by $H^q$ the graph obtained from $H$ by subdividing its edges with $q{-}1$ vertices each. In a recent paper of Kohayakawa, Retter and R{\\\"o}dl, it is shown that for all constant integers $q,r\\geq 2$ and every graph $H$ on $n$ vertices and of bounded maximum degree, the $r$-size-Ramsey number of $H^q$ is at most $(\\log n)^{20(q-1)}n^{1+1/q}$, for $n$ large enough. We improve upon this result using a significantly shorter argument by showing that $\\hat{R}_r(H^q)\\leq O(n^{1+1/q})$ for any such graph $H$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-04-29T12:41:12.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "size-ramsey number",
      "short subdivisions",
      "smallest number",
      "constant integers",
      "bounded maximum degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}