Mathematical Computer Science Seminar
Andrew Suk
UCSD
Multicolor Ramsey numbers for semi-algebraic graphs
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.
Monday April 8, 2019 at 3:00 PM in 427 SEO