The size‐Ramsey number of powers of paths. Issue 3 (2nd December 2018)

• Record Type: Journal Article
• Authors: Clemens, Dennis; Jenssen, Matthew; Kohayakawa, Yoshiharu; Morrison, Natasha; Mota, Guilherme Oliveira; Reding, Damian; Roberts, Barnaby
• Is Part Of: Journal of graph theory. Volume 91:Issue 3(2019)
• Page Start: 290
• Page End: 299
• Publication Date: 2018-12-02
• Subjects: powers of paths -- Ramsey -- size‐Ramsey; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22432
• Languages: English
• ISSNs: 0364-9024

Abstract

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.