Vertex Ramsey properties of randomly perturbed graphs

Shagnik Das; Patrick Morris; Andrew Treglown

doi:10.1002/rsa.20971

Vertex Ramsey properties of randomly perturbed graphs

Shagnik Das, Patrick Morris, Andrew Treglown

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

192 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 language	English
Pages (from-to)	983-1006
Number of pages	24
Journal	Random Structures and Algorithms
Volume	57
Issue number	4
Early online date	14 Oct 2020
DOIs	https://doi.org/10.1002/rsa.20971
Publication status	Published - 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
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Access to Document

10.1002/rsa.20971Licence: Creative Commons: Attribution (CC BY)

DasS2020VertexFinal published version, 577 KBLicence: Creative Commons: Attribution (CC BY)

https://doi.org/10.1002/rsa.20971Licence: Creative Commons: Attribution (CC BY)

Cite this

@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",

}

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

SN - 1042-9832

VL - 57

SP - 983

EP - 1006

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 4

ER -

Vertex Ramsey properties of randomly perturbed graphs

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this