Combinatorics: Yahav Alon (TAU)

Mon, 16/05/202211:00-13:00
Sprinzak 202

HUJI Combinatorics Seminar 

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

Link to live session:

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}≪pn^{−1/2}.

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