Back to Search
Start Over
Vertex Ramsey properties of randomly perturbed graphs
- Source :
- Random Structures & Algorithms. 57:983-1006
- Publication Year :
- 2020
- Publisher :
- Wiley, 2020.
-
Abstract
- Given graphs $F,H$ and $G$, we say that $G$ is $(F,H)_v$-Ramsey if every red/blue vertex colouring of $G$ contains a red copy of $F$ or a blue copy of $H$. Results of {\L}uczak, Ruci\'nski and Voigt and, subsequently, 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.<br />Comment: 21 pages
- Subjects :
- High probability
Random graph
Vertex (graph theory)
Dense graph
Applied Mathematics
General Mathematics
Ramsey theory
500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik
randomly perturbed structures
0102 computer and information sciences
01 natural sciences
Computer Graphics and Computer-Aided Design
Graph
Combinatorics
010201 computation theory & mathematics
FOS: Mathematics
Mathematics - Combinatorics
Combinatorics (math.CO)
random graphs
Software
Mathematics
Subjects
Details
- ISSN :
- 10982418 and 10429832
- Volume :
- 57
- Database :
- OpenAIRE
- Journal :
- Random Structures & Algorithms
- Accession number :
- edsair.doi.dedup.....47ec1d8a471a6ff4ffcd6fe014e0c14b