Speaker: Jacques Verstraete (UCSD)

Title: Recent progress in Ramsey Theory

Abstract: The organizing principle of Ramsey theory is that in large mathematical structures, there are relatively large substructures which are homogeneous. This is quantified in combinatorics by the notion of Ramsey numbers r(s,t), which denote the minimum N such that in any red-blue coloring of the edges of the complete graph on N vertices, there exists a red complete graph on s vertices or a blue complete graph on t vertices.
While the study of Ramsey numbers 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 \to \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 \to \infty. In this talk, we discuss a variety of new techniques, including the modern method of containers, which lead to a proof of the conjecture of Erdős that r(4,t) is of order close to t^3.
One of the salient philosophies in our approach is that good Ramsey graphs hide inside pseudorandom graphs, and the long-standing emphasis of tackling Ramsey theory from the point of view of purely random graphs is superseded by pseudorandom graphs. Via these methods, we also come close to determining the well-studied related quantities known as Erdős-Rogers functions and discuss related hypergraph coloring problems and applications.
Joint work in part with Sam Mattheus, Dhruv Mubayi and David Conlon.

свернуть