dc.contributor.author
Conlon, David
dc.contributor.author
Das, Shagnik
dc.contributor.author
Lee, Joonkyung
dc.contributor.author
Mészáros, Tamás
dc.date.accessioned
2020-10-26T09:54:06Z
dc.date.available
2020-10-26T09:54:06Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/28648
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-28397
dc.description.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 urn:x-wiley:rsa:media:rsa20959:rsa20959-math-0001, 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 urn:x-wiley:rsa:media:rsa20959:rsa20959-math-0002 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 urn:x-wiley:rsa:media:rsa20959:rsa20959-math-0003, 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 urn:x-wiley:rsa:media:rsa20959:rsa20959-math-0004 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.
en
dc.rights.uri
https://creativecommons.org/licenses/by/4.0/
dc.subject
Ramsey theory
en
dc.subject
random graphs
en
dc.subject
positional games
en
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik
dc.title
Ramsey games near the critical threshold
dc.type
Wissenschaftlicher Artikel
dcterms.bibliographicCitation.doi
10.1002/rsa.20959
dcterms.bibliographicCitation.journaltitle
Random Structures & Algorithms
dcterms.bibliographicCitation.number
4
dcterms.bibliographicCitation.pagestart
940
dcterms.bibliographicCitation.pageend
957
dcterms.bibliographicCitation.volume
57
dcterms.bibliographicCitation.url
https://doi.org/10.1002/rsa.20959
refubium.affiliation
Mathematik und Informatik
refubium.affiliation.other
Institut für Mathematik
![Dieser Normdateneintrag wurde von einer Benutzerin oder einem Benutzer als gültig bestätigt.](/cache_202e45ad85b55efaeb29160f63cd3f3b/themes/FuCD/images/authority_control/invisible.gif)
refubium.funding
DEAL Wiley
refubium.note.author
Die Publikation wurde aus Open Access Publikationsgeldern der Freien Universität Berlin gefördert.
refubium.resourceType.isindependentpub
no
dcterms.accessRights.openaire
open access
dcterms.isPartOf.eissn
1098-2418
dcterms.isPartOf.zdb
1500812-5