The size‐Ramsey number of short subdivisions. Issue 1 (11th January 2021)

• Record Type: Journal Article
• Authors: Draganić, Nemanja; Krivelevich, Michael; Nenadov, Rajko
• Is Part Of: Random structures & algorithms. Volume 59:Issue 1(2021)
• Page Start: 68
• Page End: 78
• Publication Date: 2021-01-11
• Subjects: Ramsey theory -- random graphs -- subdivisions; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20995
• Languages: English
• ISSNs: 1042-9832

Abstract

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 .