Exponential Erdős–Szekeres theorem for matrices

In 1993, Fishburn and Graham established the following qualitative extension of the classical Erdős–Szekeres theorem. If N is sufficiently large with respect to n, then any N x N real matrix contains an n x n submatrix in which every row and every column is monotone. We prove that the smallest such N is at most 2ⁿ^⁴⁺ᵒ⁽¹⁾, greatly improving the previously best known double-exponential upper bound of Bucić, Sudakov, and Tran, and matching the best known lower bound nⁿ/² on an exponential scale. In particular, we prove the following surprisingly sharp transition in the asymmetric setting. On one hand, every 8n² x 2ⁿ^⁴⁺ᵒ⁽¹⁾ matrix contains an n x n submatrix, in which every row is monotone. On the other hand, there exist n²/6 x 2²ⁿ^¹⁻ᵒ⁽¹⁾ matrices containing no such submatrix.