Ramsey games near the critical threshold

DOI10.1002/RSA.20959zbMATH Open1460.05124arXiv1908.02991OpenAlexW3095762686MaRDI QIDQ3386523FDOQ3386523

Authors: David Conlon, Shagnik Das, Joonkyung Lee, Tamás Mészáros 

Publication date: 5 January 2021

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

Abstract: A well-known result of R"odl and Ruci'nski states that for any graph $H$ there exists a constant $C$ such that if $pgeqC{n}^{-1/m_2(H)}$, then the random graph $G_{n,p}$ is a.a.s. $H$-Ramsey, that is, any $2$-colouring of its edges contains a monochromatic copy of $H$. Aside from a few simple exceptions, the corresponding $0$-statement also holds, that is, there exists $c>0$ such that whenever $pleqc{n}^{-1/m_2(H)}$ the random graph $G_{n,p}$ is a.a.s. not $H$-Ramsey. We show that near this threshold, even when $G_{n,p}$ is not $H$-Ramsey, it is often extremely close to being $H$-Ramsey. More precisely, we prove that for any constant $c>0$ and any strictly $2$-balanced graph $H$, if $pgeqc{n}^{-1/m_2(H)}$, then the random graph $G_{n,p}$ a.a.s. has the property that every $2$-edge-colouring without monochromatic copies of $H$ cannot be extended to an $H$-free colouring after $omega(1)$ extra random edges are added. This generalises a result by Friedgut, Kohayakawa, R"odl, Ruci'nski and Tetali, who in 2002 proved the same statement for triangles, and addresses a question raised by those authors. We also extend a result of theirs on the three-colour case and show that these theorems need not hold when $H$ is not strictly $2$-balanced.

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

Recommendations

• Ramsey properties of random graphs
• A randomized version of Ramsey's theorem
• On an anti-Ramsey threshold for sparse graphs with one triangle
• scientific article; zbMATH DE number 524135
• Threshold Functions for Ramsey Properties

zbMATH Keywords

Ramsey theoryrandom graphspositional games

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Ramsey theory (05D10)

Cites Work

• Title not available (Why is that?)
• Extremal results for random discrete structures
• Combinatorial theorems in sparse random sets
• Hypergraph containers
• Independent sets in hypergraphs
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Ramsey Games Against a One-Armed Bandit
• On the KŁR conjecture in random graphs
• Threshold Functions for Ramsey Properties
• Title not available (Why is that?)
• The sparse regularity lemma and its applications
• A short proof of the random Ramsey theorem
• Symmetric and asymmetric Ramsey properties in random hypergraphs
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Towards the Kohayakawa-Kreuter conjecture on asymmetric Ramsey properties
• Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs

Cited In (13)

• Van der Waerden and Ramsey type games
• A randomized version of Ramsey's theorem
• Many cliques in \(H\)-free subgraphs of random graphs
• A sharp threshold for random graphs with a monochromatic triangle in every edge coloring
• On an anti-Ramsey threshold for sparse graphs with one triangle
• Ramsey properties of random graphs and folkman numbers
• Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs
• Ramsey games with giants
• Bounds on Ramsey games via alterations
• Interview with David Conlon
• Ramsey goodness of clique versus paths in random graphs
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Density version of the Ramsey problem and the directed Ramsey problem

This page was built for publication: Ramsey games near the critical threshold

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