Premium
The size‐Ramsey number of short subdivisions
Author(s) -
Draganić Nemanja,
Krivelevich Michael,
Nenadov Rajko
Publication year - 2021
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20995
Subject(s) - combinatorics , ramsey's theorem , mathematics , graph , graph power , bounded function , monochromatic color , discrete mathematics , line graph , physics , mathematical analysis , optics
The r ‐size‐Ramsey numberR ^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 thatR ^r ( H q ) ≤ O ( n 1 + 1 / q ) for any such graph H .