Monotone Subsequences in High-Dimensional Permutations
Nathan Linial, Michael Simkin · Combinatorics Probability Computing · 2017
This paper is part of the ongoing effort to study high-dimensional permutations. We prove the analogue to the Erdős–Szekeres theorem: For everyk≥ 1, every order-nk-dimensional permutation contains a monotone subsequence of length Ωk( $\sqrt{n}$ ), and this is tight. On the other hand, and unlike the classical case, the longest monotone subsequence in a randomk-dimensional permutation of ordernis asymptotically almost surely Θk(nk/(k+1)).