HUJI Combinatorics Seminar 


When: Monday May 16th, 2022, at 11AM (Israel time)
Where: Sprinzak 202


Link to live session:
https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=e2bd744b-e453-47d3-8667-ae8100f39554


Speaker: Yahav Alon (TAU)
Title: Two-round Ramsey games


Abstract: A well known result by Łuczak, Ruciński and Voigt ('92) states that there is an absolute constant C>0 such that if p<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) ∪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 ω(1) random edges suffice to "ruin" any colouring.

We extend this result by characterising the threshold for values of p in the range n^{−2/3}≪p≪n^{−1/2}.

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