Monotone Subsequences in High-Dimensional Permutations

Abstract

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$-dimensional permutation contains a monotone subsequence of length $\hat{I}{\text{c◯}}_k\left(\sqrt{n}\right)$, and this is tight. On the other hand, and unlike the classical case, the longest monotone subsequence in a random $k$-dimensional permutation of order $n$ is asymptotically almost surely $\hat{I}{˜}_k\left(n^{\frac{k}{k+1}}\right)$.

12 pages, 1 figure