## 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 language | English (US) |
---|---|

Pages (from-to) | 2927-2947 |

Number of pages | 21 |

Journal | Journal of the European Mathematical Society |

Volume | 25 |

Issue number | 8 |

DOIs | |

State | Published - 2023 |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)
- Applied Mathematics

## Keywords

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