Ramsey numbers of multiple copies of a graph and the random Ramsey theorem

Summary · qwen2.5:32b

The paper extends the determination of $2$-colour Ramsey numbers to $r$-colour cases for multiple copies of a fixed graph $H$, specifically for $r=3$ and when $H$'s chromatic number is at least $r$, using $(H,r)$-gadgets and linear programming. It also derives the $r$-colour Ramsey number for complete bipartite graphs up to a linear error term, linking to the clique-edge-covering problem, and proves random versions of these results, generalizing the Rödl-Ruciński theorem.

Suggested post angle

Exploring Ramsey numbers in graph theory and their relationship with complete bipartite graphs. Read the article 'Ramsey numbers of multiple copies of a graph and the random Ramsey theorem' to learn more.

Excerpt

arXiv:2605.22395v2 Announce Type: replace Abstract: A well-known result of Burr, Erd\H{o}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\'e-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\H{o}s-Spencer theorem, thereby generalising the random Ramsey theorem of R\"odl and Ruci\'nski [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.