Vertex Ramsey properties of randomly perturbed graphs

Shagnik Das, Patrick Morris, Andrew Treglown

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
159 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)983-1006
Number of pages24
JournalRandom Structures and Algorithms
Volume57
Issue number4
Early online date14 Oct 2020
DOIs
Publication statusPublished - 1 Dec 2020

Bibliographical note

© 2020 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC.

This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.

Keywords

  • Ramsey theory
  • random graphs
  • randomly perturbed structures

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Vertex Ramsey properties of randomly perturbed graphs'. Together they form a unique fingerprint.

Cite this