pith. sign in

arxiv: 1910.00136 · v2 · pith:NLAB6DR3new · submitted 2019-09-30 · 🧮 math.CO

Vertex Ramsey properties of randomly perturbed graphs

classification 🧮 math.CO
keywords ramseygraphgraphsbluecopydetermineperturbedrandom
0
0 comments X
read the original abstract

Given graphs $F,H$ and $G$, we say that $G$ is $(F,H)_v$-Ramsey if every red/blue vertex colouring of $G$ containsa red copy of $F$ or a blue copy of $H$. Results of {\L}uczak, Ruci\'nski 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 \emph{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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.