The size Ramsey number of short subdivisions of bounded degree graphs. Issue 2 (12th July 2018)

• Record Type: Journal Article
• Authors: Kohayakawa, Yoshiharu; Retter, Troy; Rödl, Vojtěch
• Is Part Of: Random structures & algorithms. Volume 54:Issue 2(2019)
• Page Start: 304
• Page End: 339
• Publication Date: 2018-07-12
• Subjects: probabilistic methods -- random graphs -- regularity method -- Size‐Ramsey numbers -- subdivisions of graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20783
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: For graphs G and F, write G → ( F ) ℓ if any coloring of the edges of G with ℓ colors yields a monochromatic copy of the graph F . Suppose S ( h ) is obtained from a graph S with s vertices and maximum degree d by subdividing its edges h times (that is, by replacing the edges of S by paths of length h + 1). We prove that there exists a graph G with no more than ( log ⁡ s ) 20 h s 1 + 1 / ( h + 1 ) edges for which G → ( S ( h ) ) ℓ holds, provided that s ≥ s 0 ( h, d, ℓ ) . We also extend this result to the case in which Q is a graph with maximum degree d on q vertices with the property that every pair of vertices of degree greater than 2 are distance at least h + 1 apart. This complements work of Pak regarding the size Ramsey number of "long subdivisions" of bounded degree graphs.