Erdős-Szekeres theorem for multidimensional arrays (Q6172693)

Summary: The classical Erdős-Szekeres theorem dating back almost a hundred years [\textit{P. Erdős} and \textit{G. Szekeres}, Compos. Math. 2, 463--470 (1935; Zbl 0012.27010)] 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 \textit{P. C. Fishburn} and \textit{R. L. Graham} [J. Comb. Theory, Ser. A 62, No. 2, 280--298 (1993; Zbl 0773.05097)] 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 \cdots \times n\). Fishburn and Graham [loc. cit.] 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.