Monotone arrays and a multidimensional Ramsey Theorem
Connections Workshop: Extremal Combinatorics February 06, 2025 - February 07, 2025
Location: SLMath: Eisenbud Auditorium, Online/Virtual
A foundational result in Ramsey theory appears in a paper of Erdős and Szekeres from 1935: any sequence of n^2 +1 distinct real numbers contains either an increasing or decreasing subsequence of length n+1. This simple result was one of the starting seeds for the development of Ramsey theory. We discuss a generalisation of the Erdős-Szekeres theorem to monotone arrays. We will show how to obtain improvements on a theorem proved by Fishburn and Graham 30 years ago thus confirming a conjecture posed by Bucic, Sudakov, and Tran. More precisely, we will show that a doubly exponential upper bound holds in all dimensions. Finally, we will see how this is intimately connected to a generalisation of Ramsey Theorem on the cartesian product of cliques.