The size‐Ramsey number of short subdivisions. Issue 1 (11th January 2021) - Draganić, Nemanja; Krivelevich, Michael; Nenadov, Rajko
Abstract: The r ‐size‐Ramsey number 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 ≥ 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 R ^ r ( H q ) ≤ O ( n 1 + 1 / q ) for any such graph H .