Vertex Ramsey properties of randomly perturbed graphs

Research output: Contribution to journalArticlepeer-review

Standard

Vertex Ramsey properties of randomly perturbed graphs. / Das, Shagnik; Morris, Patrick; Treglown, Andrew.

In: Random Structures and Algorithms, Vol. 57, No. 4, 01.12.2020, p. 983-1006.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Das, Shagnik ; Morris, Patrick ; Treglown, Andrew. / Vertex Ramsey properties of randomly perturbed graphs. In: Random Structures and Algorithms. 2020 ; Vol. 57, No. 4. pp. 983-1006.

Bibtex

@article{126debfa54c14f12b48d27b4436138e4,
title = "Vertex Ramsey properties of randomly perturbed graphs",
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 {\L}uczak, Ruci{\'n}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.",
keywords = "Ramsey theory, random graphs, randomly perturbed structures",
author = "Shagnik Das and Patrick Morris and Andrew Treglown",
note = "{\textcopyright} 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.",
year = "2020",
month = dec,
day = "1",
doi = "10.1002/rsa.20971",
language = "English",
volume = "57",
pages = "983--1006",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "Wiley",
number = "4",

}

RIS

TY - JOUR

T1 - Vertex Ramsey properties of randomly perturbed graphs

AU - Das, Shagnik

AU - Morris, Patrick

AU - Treglown, Andrew

N1 - © 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.

PY - 2020/12/1

Y1 - 2020/12/1

N2 - 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.

AB - 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.

KW - Ramsey theory

KW - random graphs

KW - randomly perturbed structures

UR - http://www.scopus.com/inward/record.url?scp=85092377829&partnerID=8YFLogxK

U2 - 10.1002/rsa.20971

DO - 10.1002/rsa.20971

M3 - Article

VL - 57

SP - 983

EP - 1006

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 4

ER -