The size-Ramsey number of short subdivisions

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$. 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{ö}dl, it is shown that for all constant integers $q,r\ge 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)\le O(n^{1+1/q})$ for any such graph $H$.

12 pages, 1 figure