Erdős–Szekeres theorem for multidimensional arrays

Matija Bucić, Benny Sudakov, Tuan Tran

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

The classical Erdős–Szekeres theorem dating back almost a hundred years states that any sequence of (n - 1)2 C 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.

Original languageEnglish (US)
Pages (from-to)2927-2947
Number of pages21
JournalJournal of the European Mathematical Society
Volume25
Issue number8
DOIs
StatePublished - 2023

All Science Journal Classification (ASJC) codes

  • General Mathematics
  • Applied Mathematics

Keywords

  • Erdős–Szekeres theorem
  • Ramsey theory
  • high-dimensional permutations
  • monotone arrays

Fingerprint

Dive into the research topics of 'Erdős–Szekeres theorem for multidimensional arrays'. Together they form a unique fingerprint.

Cite this