Erdős–Szekeres theorem for multidimensional arrays
Matija Bucić
Princeton University, USABenjamin Sudakov
ETH Zürich, SwitzerlandTuan Tran
University of Science and Technology of China, Hefei, China
![Erdős–Szekeres theorem for multidimensional arrays cover](/_next/image?url=https%3A%2F%2Fcontent.ems.press%2Fassets%2Fpublic%2Fimages%2Fserial-issues%2Fcover-jems-volume-25-issue-8.png&w=3840&q=90)
Abstract
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