Ramsey numbers of cycles in random graphs

Pedro Araújo; Matías Pavez-Signé; Nicolás Sanhueza-Matamala

paper

Ramsey numbers of cycles in random graphs

arXiv:2208.13028

Abstract

Let $R (C_{n})$ be the Ramsey number of the cycle on $n$ vertices. We prove that, for some $C > 0$ , with high probability every $2$ -colouring of the edges of $G (N, p)$ has a monochromatic copy of $C_{n}$ , as long as $N \geq R (C_{n}) + C / p$ and $p \geq C / n$ . This is sharp up to the value of $C$ and it improves results of Letzter and of Krivelevich, Kronenberg and Mond.

arXiv commentTo appear in Random Structures & Algorithms