A Caltech Library Service

Ramsey games near the critical threshold

Conlon, David and Das, Shagnik and Lee, Joonkyung and Mészáros, Tamás (2020) Ramsey games near the critical threshold. Random Structures and Algorithms, 57 (4). pp. 940-957. ISSN 1042-9832.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
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.
Funding AgencyGrant Number
Deutsche Forschungsgemeinschaft (DFG)415310276
German-Israeli Foundation for Research and DevelopmentG-1347-304.6/2016
Dahlem Research SchoolUNSPECIFIED
Berlin Mathematics Research CenterUNSPECIFIED
European Research Council (ERC)RanDM 676632
European Research Council (ERC)PEPCo 724903
Subject Keywords:Ramsey theory; random graphs; positional games
Issue or Number:4
Record Number:CaltechAUTHORS:20190820-162204728
Persistent URL:
Official Citation:Conlon, D, Das, S, Lee, J, Mészáros, T. Ramsey games near the critical threshold. Random Struct Alg. 2020; 57: 940–957.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98055
Deposited By: Melissa Ray
Deposited On:21 Aug 2019 18:45
Last Modified:29 Oct 2020 16:10

Repository Staff Only: item control page