2020/04/29 by Draganić, Nemanja, Krivelevich, Michael, Nenadov, Rajko
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2004.14139
The r-size-Ramsey number Rr(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 Hq 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 Hq is at most (log n)20(q-1)n1+1/q, for n large enough. We improve upon this result using a significantly shorter argument by showing that Rr(Hq)≤ O(n1+1/q) for any such graph H.