Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2020 | Submitted + Published
Journal Article Open

Ramsey games near the critical threshold


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 ≥ Cn^(-1/m2(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 ≤ Cn^(-1/m2(H)) the random graph Gn, 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 ≥ Cn^(-1/m2(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.

Additional Information

© 2020 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC. This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited. Issue Online: 25 October 2020; Version of Record online: 17 October 2020; Manuscript accepted: 22 April 2020; Manuscript received: 08 August 2019. This research was supported by the Deutsche Forschungsgemeinschaft (DFG) project 415310276; the German‐Israeli Foundation for Scientific Research and Development, GIF grant G‐1347‐304.6/2016 [S.D.]. The Dahlem Research School, DRS Fellowship Program and the Berlin Mathematics Research Center MATH+, project "learning hypergraphs" [T.M.]. The European Research Council (ERC) starting grant RanDM 676632 [D.C.] and ERC consolidator grant PEPCo 724903 [J.L.]. Open access funding enabled and organized by Projekt DEAL. Part of this work was carried out while the third author visited the second and fourth authors at FU Berlin and he is grateful for their hospitality. Open access funding enabled and organized by Projekt DEAL.

Attached Files

Published - rsa.20959.pdf

Submitted - 1908.02991.pdf


Files (819.5 kB)
Name Size Download all
580.9 kB Preview Download
238.6 kB Preview Download

Additional details

August 22, 2023
October 18, 2023