View PDF HTML (experimental)

Abstract:A well-known result of Burr, Erdős and Spencer [Transactions of the American Mathematical Society, 1975] determines the $2$-colour Ramsey number for any sufficiently large collection of vertex-disjoint copies of a fixed graph $H$ without isolated vertices. A focus of this paper is to give analogous results for the corresponding $r$-colour Ramsey problem. More precisely we determine, up to an additive constant, this Ramsey number in the case when $r=3$ and also in the case when the chromatic number of $H$ is at least $r$. In these cases our results depend on a parameter which, roughly speaking, describes the corresponding class of potential extremal colourings of the complete graph. Our proofs rely on our notion of $(H,r)$-gadgets, which is crucial to obtain results that are best-possible up to additive constant terms. We exploit this notion using linear programming and the Poincaré-Miranda theorem.
We also determine, up to a linear error term, the corresponding $r$-colour Ramsey number in the case when $H$ is a complete bipartite graph. Here, the corresponding class of potential extremal examples exhibits a connection with the well-known clique-edge-covering problem.
We also prove random versions of some of our results. In particular, we prove a random version of the Burr-Erdős-Spencer theorem, thereby generalising the random Ramsey theorem of Rödl and Ruciński [Journal of the American Mathematical Society, 1995]. Our proofs make use of coloured versions of the (sparse) regularity lemma and the KLR conjecture for random graphs.

Submission history

From: Andrew Treglown [view email]
[v1] Thu, 21 May 2026 12:29:05 UTC (12 KB)
[v2] Thu, 2 Jul 2026 18:40:07 UTC (46 KB)