Vertex Ramsey properties of randomly perturbed graphs

DOI10.1002/RSA.20971zbMATH Open1454.05075arXiv1910.00136OpenAlexW3093041038MaRDI QIDQ3386525FDOQ3386525

Authors: Shagnik Das, Patrick Morris, Andrew Treglown 

Publication date: 5 January 2021

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1910.00136

Recommendations

• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Large Rainbow Cliques in Randomly Perturbed Dense Graphs
• Threshold Functions for Ramsey Properties
• Small rainbow cliques in randomly perturbed dense graphs
• Ramsey properties of random graphs

zbMATH Keywords

Ramsey theoryrandom graphsrandomly perturbed structures

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Spanning trees in randomly perturbed graphs
• Title not available (Why is that?)
• On smoothed analysis in dense graphs and formulas
• Adding random edges to dense graphs
• How many random edges make a dense graph hamiltonian?
• Threshold Functions for Ramsey Properties
• EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
• Universality for bounded degree spanning trees in randomly perturbed graphs
• Concentration of multivariate polynomials and its applications
• Upper tails for subgraph counts in random graphs
• Poisson approximation for large deviations
• Ramsey properties of random graphs
• Title not available (Why is that?)
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Tilings in randomly perturbed dense graphs
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Powers of Hamiltonian cycles in randomly augmented graphs
• Title not available (Why is that?)
• Towards the Kohayakawa-Kreuter conjecture on asymmetric Ramsey properties

Cited In (8)

• Factors in randomly perturbed hypergraphs
• Schur properties of randomly perturbed sets
• On vertex Ramsey graphs with forbidden subgraphs
• Small rainbow cliques in randomly perturbed dense graphs
• Large Rainbow Cliques in Randomly Perturbed Dense Graphs
• Ramsey properties of random graphs
• Random perturbation of sparse graphs
• Ramsey properties of randomly perturbed graphs: cliques and cycles

This page was built for publication: Vertex Ramsey properties of randomly perturbed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386525)