We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Erdős--Szekeres theorem for multidimensional arrays.
- Authors
Bucíc, Matija; Sudakov, Benny; Tran, Tuan
- Abstract
The classical Erdős--Szekeres theorem dating back almost a hundred years states that any sequence of (n - 1)² + 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 x • • • x 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.
- Subjects
MONOTONE operators; EXPONENTIAL functions; PERMUTATIONS; RAMSEY theory; OPERATOR theory
- Publication
Journal of the European Mathematical Society (EMS Publishing), 2023, Vol 25, Issue 8, p2927
- ISSN
1435-9855
- Publication type
Article
- DOI
10.4171/JEMS/1262