Andrew Suk : Multicolor Ramsey numbers for semi-algebraic graphs

Posted by Dhruv Mubayi , part of the Mathematical Computer Science Seminar.

At

April 8, 2019, 3 p.m.

In

427 SEO

Abstract

The Ramsey number R(p; m) is the smallest integer n such that any m-coloring on the edges of the complete n-vertex graph contains a monochromatic copy of K_p. Here, we think of p as a fixed constant, and m tends to infinity. In his work related to Fermat’s Last Theorem, Schur proved that 2^Ω(m) < R(3;m) < O(m!). While small improvements have been made to the lower bound, the upper bound remains unchanged. It is an old problem of Erdős to decide whether R(p; m) = 2^O(m), when p is fixed. In this talk, I will sketch a proof of this if we further assume that the edge colorings are semi-algebraic with bounded complexity. This is joint work with Jacob Fox and Janos Pach.