The size‐Ramsey number of powers of paths

Given graphs G and H and a positive integer q , say that G is q ‐ Ramsey for H , denoted G → ( H ) q , if every q ‐coloring of the edges of G contains a monochromatic copy of H . The size‐Ramsey numberr ˆ ( H ) of a graph H is defined to be r ˆ ( H ) = min { ∣ E ( G ) ∣ : G → ( H ) 2 } . Answering a question of Conlon, we prove that, for every fixed k , we have r ˆ ( P n k ) = O ( n ) , where P n k is the k th power of the n ‐vertex path P n (ie, 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.