Seminars & Colloquia Calendar

Abstract: Two well-studied problems in Ramsey theory are (1) given a graph G on n vertices, what is the smallest integer N such that there is a monochromatic copy of G in every 2-coloring of a complete graph on N vertices, and (2) given a directed acyclic graph D on n vertices, what is the smallest integer N such that there is a copy of D in every tournament on N vertices.  Note that for both problems, the family of trees has turned out to be an interesting special case, each with a long history and a relatively recent resolution (for sufficiently large n).

We consider quantitative analogues of these problems in the infinite setting; that is, (1) given a countably infinite graph G what is the supremum of the set of real numbers r such that in every 2-coloring of the complete graph on the natural numbers there is a monochromatic copy of G whose vertex set has upper/lower density at least r, and (2) given a countably infinite directed acyclic graph D what is the supremum of the set of real numbers r such that in every tournament on the natural numbers there is a copy of D whose vertex set has upper/lower density at least r?  As it relates to these problems, I will discuss two very surprising results.

Based on joint work with Alistair Benford, Jan Corsten, and Paul McKenney.