Establishes that the 2-color Ramsey number for sufficiently many vertex-disjoint copies of H remains asymptotically the same in the random graph G(n,p) for appropriate p.
Ramsey properties for tilings in random graphs
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
Let $mH$ be the graph formed by $m$ vertex-disjoint copies of a graph $H$. Let $G \to (H)_r$ denote that, in any $r$-colouring of the edges of $G$, there exists a monochromatic copy of $H$. In 1975, Burr, Erd\H{o}s, and Spencer showed that if $H$ is a graph on $k$ vertices whose independence number is $\alpha$, then $K_n \to (mH)_2$, where $m\sim n/(2k-\alpha)$, and that the $1/(2k-\alpha)$ factor is best possible. In the 1990s, R\"{o}dl and Ruci\'{n}ski proved that, for all but a few graphs~$H$, the threshold for the property $\mathbb{G}(n,p) \to (H)_r$ is $n^{-1/m_2(H)}$. In this paper, generalizing the result of Burr, Erd\H{o}s, and Spencer, we prove that $n^{-1/\max\{m_2(H),1\}}$ is the threshold for the property $\mathbb{G}(n,p) \to (mH)_2$, where $m\sim n/(2k-\alpha)$. This threshold matches the one found by R\"{o}dl and Ruci\'nski for most graphs $H$, extending their result in the case $r=2$.
fields
math.CO 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
A random version of the Burr-Erd\H{o}s-Spencer theorem
Establishes that the 2-color Ramsey number for sufficiently many vertex-disjoint copies of H remains asymptotically the same in the random graph G(n,p) for appropriate p.