Umeå universitets logga

In 1993, Fishburn and Graham established the following qualitative extension of the classical Erdős–Szekeres theorem. If (Formula presented.) is sufficiently large with respect to (Formula presented.), then any (Formula presented.) real matrix contains an (Formula presented.) submatrix in which every row and every column is monotone. We prove that the smallest such (Formula presented.) is at most (Formula presented.), greatly improving the previously best known double-exponential upper bound of Bucić, Sudakov, and Tran, and matching the best known lower bound (Formula presented.) on an exponential scale. In particular, we prove the following surprisingly sharp transition in the asymmetric setting. On one hand, every (Formula presented.) matrix contains an (Formula presented.) submatrix, in which every row is monotone. On the other hand, there exist (Formula presented.) matrices containing no such submatrix.