The size-Ramsey number of powers of paths

Abstract

Given graphs $G$ and $H$ and a positive integer $q$, say that $G$ \emph{is $q$-Ramsey for} $H$, denoted $G\rightarrow (H)_q$, if every $q$-colouring of the edges of $G$ contains a monochromatic copy of $H$. The \emph{size-Ramsey number} $\sr(H)$ of a graph $H$ is defined to be $\sr(H)=\min\{|E(G)|\colon G\rightarrow (H)_2\}$. Answering a question of Conlon, we prove that, for every fixed~$k$, we have $\sr(P_n^k)=O(n)$, where~$P_n^k$ is the $k$th power of the $n$-vertex path $P_n$ (i.e., the graph with vertex set $V(P_n)$ and all edges $\{u,v\}$ such that the distance between $u$ and $v$ in $P_n$ is at most $k$). Our proof is probabilistic, but can also be made constructive.