Computer Science/Discrete Mathematics Seminar II

The absorption method is a very simple yet surprisingly powerful idea coming from extremal combinatorics which allows one to convert asymptotic results into exact ones. It has produced a remarkable number of success stories in recent years with perhaps the most prominent being a proof of the existence of designs. In the first part of the talk, we will introduce the basic idea behind the method and then illustrate it by showing how it can be used to prove a modified version of a classical theorem of Hajnal and Szemeredi on equitable colorings of graphs. In the second part of the talk, we will see an application of this result to Ramsey theory. Namely, we will use it to settle a question of Burr, Erdos, and Spencer from 1975 concerning Ramsey numbers of so-called copy graphs, one of the precious few classes of graphs for which we know the Ramsey number precisely.

Based on joint work with Benny Sudakov.