The size‐Ramsey number of powers of paths. Issue 3 (2nd December 2018) - Clemens, Dennis; Jenssen, Matthew; Kohayakawa, Yoshiharu; Morrison, Natasha; Mota, Guilherme Oliveira; Reding, Damian; Roberts, Barnaby
Abstract: 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 number r ˆ ( 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.