Vertex Ramsey properties of randomly perturbed graphs

DOI10.1002/RSA.20971MaRDI QIDQ3386525zbMATH OpenOpenAlexFDO

Authors Shagnik Das, Patrick Morris, Andrew Treglown

Publication date 5 January 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

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)