Jacques Verstraete: Recent Progress in Ramsey Theory #ICBS2024

The Ramsey number $r(s,t)$ denotes the minimum $N$ such that in any red-blue coloring of the edges of the complete graph $K_N$, there exists a red $K_s$ or a blue $K_t$. While the study of these quantities goes back almost one hundred years, to early papers of Ramsey and Erd\H{o}s and Szekeres, the long-standing conjecture of Erd\H{o}s that $r(s,t)$ has order of magnitude close to $t^{s - 1}$ as $t \rightarrow \infty$ remains open in general. In this talk, we discuss a variety of new techniques, stemming from the discovery that pseudorandom graphs yields good Ramsey graphs. These techniques include methods from geometry, algebra, probability, and combinatorics, and lead to a proof of the Erd\H{o}s conjecture that $r(4,t) = t^{3 - o(1)}$ as $t \rightarrow \infty$., as well as a number of other new constructions in Ramsey theory.

There is a typo in the sequence r(3, t) mentioned in the fourth slide at 6:20.
It is 1, 3, 6, 9, 14, 18, 23, 28, 36 according to the entry A000791 in OEIS.