Erdős-Szekeres theorem for multidimensional arrays

Abstract

The classical Erdős-Szekeres theorem dating back almost a hundred years states that any sequence of $(n-1{)}^2+1$ distinct real numbers contains a monotone subsequence of length $n$. This theorem has been generalised to higher dimensions in a variety of ways but perhaps the most natural one was proposed by Fishburn and Graham more than 25 years ago. They defined the concept of a monotone and a lex-monotone array and asked how large an array one needs in order to be able to find a monotone or a lex-monotone subarray of size $n\times \dots \times n$. Fishburn and Graham obtained Ackerman-type bounds in both cases. We significantly improve these results. Regardless of the dimension we obtain at most a triple exponential bound in $n$ in the monotone case and a quadruple exponential one in the lex-monotone case.

18 pages, 5 figures

References in corpus (5)

• Longest Common Subsequences in Sets of Permutations
• Partition problems in high dimensional boxes
• Edge-ordered Ramsey numbers
• Linear orderings of combinatorial cubes
• On edge-ordered Ramsey numbers

Cited by in corpus (1)

• On quantitative aspects of a canonisation theorem for edge-orderings