Ramsey-type problems for tilings in dense graphs

Given a graph H, the Ramsey number R(H) is the smallest positive integer n such that every 2-edge-colouring of K_n yields a monochromatic copy of H. We write mH to denote the union of m vertex-disjoint copies of H. The members of the family {mH : m ≥ 1} are also known as H-tilings. A well-known result of Burr, Erdős and Spencer states that R(mK₃) = 5m for every m ≥ 2. On the other hand, Moon proved that every 2-edge-colouring of K_3m+2 yields a K₃-tiling consisting of m monochromatic copies of K₃, for every m ≥ 2. Crucially, in Moon’s result, distinct copies of K₃ might receive different colours.

In this paper, we investigate the analogous questions where the complete host graph is replaced by a graph of large minimum degree. We determine the (asymptotic) minimum degree threshold for forcing a K₃-tiling covering a prescribed proportion of the vertices in a 2-edge-coloured graph such that every copy of K₃ in the tiling is monochromatic. We also determine the largest size of a monochromatic K₃-tiling one can guarantee in any 2- edge-coloured graph of large minimum degree. These results therefore provide generalisations of the theorems of Moon and Burr–Erdős–Spencer to the setting of dense graphs.

It is also natural to consider generalisations of these problems to r-edge-colourings (for r ≥ 2) and for H-tilings (for arbitrary graphs H). We prove some results in this direction and propose several open questions.