MIT-Harvard-MSR Combinatorics Seminar: Size Ramsey numbers

SEMINARS

Speaker:

Yuval Wigderson - Stanford

The size Ramsey number of a graph $H$ is the minimum number of edges in a  graph $G$ with the property that no matter how we two-color the edges of  $G$, we can find a monochromatic copy of $H$. This notion was introduced  in 1978 by Erdős, Faudree, Rousseau, and Schelp, and despite more than  four decades of work, there is a lot that is still unknown; notably, of  the four questions that conclude the Erdős–Faudree–Rousseau–Schelp paper,  only one had been resolved as of last year. In this talk, I'll discuss  recent work in which we resolve $\approx 2.5$ of the three remaining  questions, using a variety of new combinatorial and probabilistic constructions.

Based on joint work with David Conlon and Jacob Fox.