Ramsey games near the critical threshold
Abstract
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
Name | Size | Download all |
---|---|---|
md5:7a34a1540b1913af94c54c300785ab38
|
580.9 kB | Preview Download |
md5:c617bf209d90e86768963399d61bbaed
|
238.6 kB | Preview Download |
Additional details
- Eprint ID
- 98055
- Resolver ID
- CaltechAUTHORS:20190820-162204728
- Deutsche Forschungsgemeinschaft (DFG)
- 415310276
- German-Israeli Foundation for Research and Development
- G-1347-304.6/2016
- Dahlem Research School
- Berlin Mathematics Research Center
- European Research Council (ERC)
- RanDM 676632
- European Research Council (ERC)
- PEPCo 724903
- Projekt DEAL
- Created
-
2019-08-21Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field