Monotone Subsequences in High-Dimensional Permutations

Nathan Linial, Michael Simkin

This paper is part of the ongoing effort to study high-dimensional permutations. We prove the analogue to the Erdős-Szekeres theorem: For every $k\ge 1$, every order-$n$ $k$-dimensi…