Combinatorics Seminar
When: Sunday, October 21, 10am
Where: Schreiber 309
Speaker: Asaf Shapira, Tel Aviv University
Title: Ramsey Theory, Integer Partitions and a New Proof
of the Erdos-Szekeres Theorem
Abstract:
The Erdos-Szekeres Lemma on increasing/decreasing subsequences can
be formulated as a Ramsey-type result in graph theory, asking for
the smallest integer N, so that in every 2-coloring of the
complete graph on the integers 1,...,N one can find a
monochromatic monotone path of length n.
Fox, Pach, Sudakov and Suk suggested the study of the natural
hypergraph analogue of this problem. Our main contribution here is
a novel approach for bounding these Ramsey numbers, based on
establishing a surprisingly tight connection between them and the
enumerative problem of counting high-dimensional integer
partitions.
We use this approach to give very tight bounds for these Ramsey
numbers thus answering a problem raised by Fox et al. As a
byproduct, we also get a new pigeonhole proof of the
Erdos-Szekeres Theorem on cups-vs-caps, similar to Seidenberg's
proof of the Erdos-Szekeres Lemma.
Joint work with Guy Moshkovitz.