Erdős–Szekeres theorem for multidimensional arrays
OPEN ACCESS
Loading...
Author / Producer
Date
2023-07-07
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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 × ⋯ × 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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
25 (8)
Pages / Article No.
2927 - 2947
Publisher
European Mathematical Society
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Erdős–Szekeres theorem; high-dimensional permutations; monotone arrays; Ramsey theory
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
Notes
Funding
196965 - Problems in Extremal and Probabilistic Combinatorics (SNF)