Premium
Ramsey games near the critical threshold
Author(s) -
Conlon David,
Das Shagnik,
Lee Joonkyung,
Mészáros Tamás
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20959
Subject(s) - combinatorics , monochromatic color , ramsey's theorem , mathematics , graph , random graph , constant (computer programming) , discrete mathematics , ramsey theory , edge coloring , graph power , line graph , physics , computer science , optics , programming language
A well‐known result of Rödl and Ruciński states that for any graph H there exists a constant C such that if p ≥ C n − 1 / m 2 ( H ) , then the random graph G n , p is a.a.s. H ‐Ramsey, that is, any 2‐coloring 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 p ≤ c 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 p ≥ c n − 1 / m 2 ( H ) , then the random graph G n , p a.a.s. has the property that every 2‐edge‐coloring without monochromatic copies of H cannot be extended to an H ‐free coloring after ω ( 1 ) extra random edges are added. This generalizes a result by Friedgut, Kohayakawa, Rödl, Ruciński, 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‐color case and show that these theorems need not hold when H is not strictly 2‐balanced.