تقرير
Ramsey games near the critical threshold
| العنوان: | Ramsey games near the critical threshold |
|---|---|
| المؤلفون: | Conlon, David, Das, Shagnik, Lee, Joonkyung, Mészáros, Tamás |
| سنة النشر: | 2019 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics |
| الوصف: | A well-known result of R\"odl and Ruci\'nski states that for any graph $H$ there exists a constant $C$ such that if $p \geq C n^{- 1/m_2(H)}$, then the random graph $G_{n,p}$ is a.a.s. $H$-Ramsey, that is, any $2$-colouring 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\leq cn^{-1/m_2(H)}$ the random graph $G_{n,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 \geq c n^{-1/m_2(H)}$, then the random graph $G_{n,p}$ a.a.s. has the property that every $2$-edge-colouring without monochromatic copies of $H$ cannot be extended to an $H$-free colouring after $\omega(1)$ extra random edges are added. This generalises a result by Friedgut, Kohayakawa, R\"odl, Ruci\'nski 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-colour case and show that these theorems need not hold when $H$ is not strictly $2$-balanced. Comment: 18 pages, 6 figures; to appear in Random Structures & Algorithms |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/1908.02991 |
| رقم الأكسشن: | edsarx.1908.02991 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |