Exponential Erd\H{o}s-Szekeres theorem for matrices

Abstract: In 1993, Fishburn and Graham established the following qualitative extension of the classical ErdH{o}s-Szekeres theorem. If

N

is sufficiently large with respect to

n

, then any

N i m e s N

real matrix contains an

n i m e s n

submatrix in which every row and every column is monotone. We prove that the smallest such

N

is at most

2^{n^{4 + o (1)}}

, greatly improving the previously best known double-exponential upper bound, and getting close to the best known lower bound

n^{n / 2}

. In particular, we prove the following surprising sharp transition in the asymmetric setting. On one hand, every

8 n^{2} i m e s 2^{n^{4 + o (1)}}

matrix contains an

n i m e s n

submatrix, in which every row is mononote. On the other hand, there exist

n^{2} / 6 i m e s 2^{2^{n^{1 - o (1)}}}

matrices containing no such submatrix .

This page was built for publication: Exponential Erd\H{o}s-Szekeres theorem for matrices