Combinatorics Seminar - Spring '21

When: Sunday, May 8, 10am

Where: Schreiber 309

Speaker: Eden Kuperwasser, Tel Aviv

Title: The List-Ramsey Threshold


Given a family of graphs $\mathcal{H}$ and an integer $r$, we say that a graph is $r$-Ramsey for $\mathcal{H}$ if any $r$-coloring of its edges admits a monochromatic copy of a graph from $\mathcal{H}$. The threshold for the classic Ramsey problem, where $\mathcal{H}$ consists of one graph, was located in the work of R\"odl and Ruci\'nski. In this talk we will offer a twofold generalization to this theorem: showing that the list-coloring version of the property has the same threshold, and extending this result for finite families $\mathcal{H}$. This also confirms further special cases of the Kohayakawa--Kreuter conjecture.

Joint with Wojciech Samotij.