Combinatorics Seminar

When: Sunday, December 26, 10am Where: Schreiber 309 Speaker: Benny Sudakov, University of California at Los Angeles Title: A conjecture of Erdos on Ramsey numbers

Abstract:

The Ramsey number r(G) of a graph G is the minimum N such that every red-blue coloring of the edges of the complete graph on N vertices contains a monochromatic copy of G. Determining or estimating these numbers is one of the central problems in combinatorics.

One of the oldest results in Ramsey Theory, proved by Erdos-Szekeres in the 1930's, asserts that the Ramsey number of the complete graph with m edges is at most 2^{O(\sqrt{m})}. Motivated by this, about a quarter century ago Erdos conjectured that there is an absolute constant c such that r(G)< 2^{c\sqrt{m}} for any graph G with m edges. In this talk we discuss a proof of this conjecture.