Vertex Ramsey properties of randomly perturbed graphs. Issue 4 (14th October 2020)

• Record Type: Journal Article
• Authors: Das, Shagnik; Morris, Patrick; Treglown, Andrew
• Is Part Of: Random structures & algorithms. Volume 57:Issue 4(2020)
• Page Start: 983
• Page End: 1006
• Publication Date: 2020-10-14
• Subjects: Ramsey theory -- random graphs -- randomly perturbed structures; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20971
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : Given graphs F, H and G, we say that G is ( F, H ) v ‐Ramsey if every red/blue vertex coloring of G contains a red copy of F or a blue copy of H . Results of Łuczak, Ruciński and Voigt, and Kreuter determine the threshold for the property that the random graph G ( n, p ) is ( F, H ) v ‐Ramsey. In this paper we consider the sister problem in the setting of randomly perturbed graphs . In particular, we determine how many random edges one needs to add to a dense graph to ensure that with high probability the resulting graph is ( F, H ) v ‐Ramsey for all pairs ( F, H ) that involve at least one clique.