Ramsey numbers of cycles in random graphs

Authors: P. Araújo, M. Pavez-Signé, Nicolás Sanhueza-Matamala
Publication year: 2025
Publication type: Článek v odborném periodiku
Periodical: Random Structures and Algorithms
Projects: Random discrete structures
Embedding, Packing and Limits in Graphs
Bibliographic citation: ARAÚJO, P., PAVEZ-SIGNÉ, M., SANHUEZA-MATAMALA, Nicolás. Ramsey numbers of cycles in random graphs. Random Structures and Algorithms. 2025, 66(1), e21253. ISSN 1042-9832. E-ISSN 1098-2418
Dostupné z: doi:10.1002/rsa.21253.
DOI: 10.1002/rsa.21253
ID: 616462
Online record: View online record

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 >= R(C-n)+C/p and p >= C/n. This is sharp up to the value of C and it improves results of Letzter and of Krivelevich, Kronenberg and Mond.