Talk information

Date: Sunday, March 3, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Eden Kuperwasser (TAU)
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.