Ramsey properties for tilings in random graphs

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ős, and Spencer showed that if $H$ is a graph on $k$ vertices whose independence number is $\hat{I}\pm$, then $K_n\to (mH{)}_2$, where $m\sim n/(2k-\hat{I}\pm )$, and that the $1/(2k-\hat{I}\pm )$ factor is best possible. In the 1990s, Rödl and Ruciń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ő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-\hat{I}\pm )$. This threshold matches the one found by Rödl and Ruciński for most graphs $H$, extending their result in the case $r=2$.

21 pages