Andrew Suk (Theory Seminar)

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.