TAU Combinatorics Seminar 2021/22

When: Sunday, October 24, 10am
Speaker: Yahav Alon, Tel Aviv University
Title: Two-round Ramsey games


A well known result by Łuczak, Ruciński and Voigt ('92) states that there is an absolute constant $C>0$ such that if $p \le Cn^{-1/2}$ then, with high probability, $G(n,p)$ is not $K_3$-Ramsey.

In a 2002 paper, Friedgut, Kohayakawa, Rödl, Ruciński and Tetali considered a two-round one-player Ramsey game. In this game, a player colours the edges of a random graph $G(n,p)$ in red and blue, and then attempts to extend the colouring to the edges of (previously unseen) $G(n,q)$ such that the resulting colouring of $G(n,p) \cup G(n,q)$ is monochromatic triangle-free. For $p = n^{-2/3}$ they concluded that $q^* = n^{-2/3}$ is a threshold for the existence of a colouring strategy. In addition, for $p = cn^{-1/2}$ below the $K_3$-Ramsey threshold, $q^* = n^{-2}$ is a threshold, implying that, close to the threshold, even $\omega (1)$ random edges suffice to "ruin" the colouring.

We extend this result by characterising the threshold for values of $p$ in the range $n^{-2/3} \ll p \ll n^{-1/2}$.

This is based on joint work with Patrick Morris and Wojciech Samotij.