UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Ramsey games near the critical threshold

Conlon, D; Das, S; Lee, J; Mészáros, T; (2020) Ramsey games near the critical threshold. Random Structures and Algorithms , 57 (4) pp. 940-957. 10.1002/rsa.20959. Green open access

[thumbnail of rsa.20959.pdf]
Preview
Text
rsa.20959.pdf - Published Version

Download (580kB) | Preview

Abstract

Random Structures & Algorithms published by Wiley Periodicals LLC. A well-known result of Rödl and Ruciński states that for any graph H there exists a constant C such that if (Formula presented.), then the random graph Gn, 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 (Formula presented.) the random graph Gn, p is a.a.s. not H-Ramsey. We show that near this threshold, even when Gn, 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 (Formula presented.), then the random graph Gn, 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 (Formula presented.) 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.

Type: Article
Title: Ramsey games near the critical threshold
Open access status: An open access version is available from UCL Discovery
DOI: 10.1002/rsa.20959
Publisher version: https://doi.org/10.1002/rsa.20959
Language: English
Additional information: Copyright © 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 (http://creativecommons.org/licenses/by/4.0/), which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
Keywords: Ramsey theory, random graphs, positional games
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
URI: https://discovery.ucl.ac.uk/id/eprint/10113320
Downloads since deposit
37Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item