Title:
On a conjecture of Kohayakawa and Kreuter
Abstract:
We say that G is Ramsey for a tuple of graphs (H_1, \dots, H_r) if any r-coloring of the edges of G contains, for some i \in [r], a monochromatic copy of H_i in the color i. In their seminal work, Rödl and Ruciński located the threshold at which the binomial random graph G_{n,p} becomes Ramsey for the symmetric case where all H_i are identical. Building on this work, Kohayakawa and Kreuter conjectured where the threshold for the general case should be.
The subject of this talk is a joint work with Wojciech Samotij and Yuval Wigderson, in which we resolve almost all cases of the conjecture. We do so by reducing the conjecture to a deterministic statement, which we then prove for most cases.
In a recent subsequent work of Christoph, Martinsson, Steiner, and Wigderson, this deterministic statement was proven in full generality, thus proving the conjecture