Back to Search Start Over

The size‐Ramsey number of short subdivisions

Authors :
Rajko Nenadov
Nemanja Draganić
Michael Krivelevich
Source :
Random Structures & Algorithms. 59:68-78
Publication Year :
2021
Publisher :
Wiley, 2021.

Abstract

The $r$-size-Ramsey number $\hat{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$. The notion of size-Ramsey numbers has been introduced by Erdős, Faudree, Rousseau and Schelp in 1978, and has attracted a lot of attention ever since. 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{o}dl, it is shown that for all constant integers $q,r\geq 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 $\hat{R}_r(H^q)\leq O(n^{1+1/q})$ for any such graph $H$.

Details

ISSN :
10982418 and 10429832
Volume :
59
Database :
OpenAIRE
Journal :
Random Structures & Algorithms
Accession number :
edsair.doi...........549d3545f01a5a677c773fca825d778f