Erdős–Szekeres theorem for multidimensional arrays

  • Matija Bucić

    Princeton University, USA
  • Benjamin Sudakov

    ETH Zürich, Switzerland
  • Tuan Tran

    University of Science and Technology of China, Hefei, China
Erdős–Szekeres theorem for multidimensional arrays cover
Download PDF

This article is published open access under our Subscribe to Open model.


The classical Erdős–Szekeres theorem dating back almost a hundred years states that any sequence of distinct real numbers contains a monotone subsequence of length . 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 . 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 in the monotone case and a quadruple exponential one in the lex-monotone case.

Cite this article

Matija Bucić, Benjamin Sudakov, Tuan Tran, Erdős–Szekeres theorem for multidimensional arrays. J. Eur. Math. Soc. 25 (2023), no. 8, pp. 2927–2947

DOI 10.4171/JEMS/1262