Recent progress in Ramsey Theory

Abstract: 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ős and Szekeres, the long-standing conjecture of Erdős that $r(s,t)$ has order of magnitude close to $t^{s - 1}$ as $t \rightarrow \infty$ remains open in general. It took roughly sixty years before the order of magnitude of $r(3,t)$ was determined by Jeong Han Kim, who showed $r(3,t)$ has order of magnitude $t^2/(\log t)$ as $t \rightarrow \infty$. In this talk, we discuss a variety of new techniques, including mention of the proof that for some constants $a,b > 0$ and $t \geq 2$, \[ a\frac{t^3}{(\log t)^4} \leq r(4,t) \leq b\frac{t^3}{(\log t)^2},\] as well as new progress on other Ramsey numbers, on Erdős-Rogers functions, Ramsey minimal graphs, and on coloring hypergraphs.

Joint work in part with David Conlon, Sam Mattheus, and Dhruv Mubayi.

combinatorics

Audience: learners

UCLA Combinatorics Seminar

Series comments: This quarter, the talks will be in-person with no Zoom livestream.