Exponential Erd\H{o}s-Szekeres theorem for matrices
| Autor: | Çiçeksiz, Recep Altar, Jin, Zhihan, Räty, Eero, Tomon, István |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | In 1993, Fishburn and Graham established the following qualitative extension of the classical Erd\H{o}s-Szekeres theorem. If $N$ is sufficiently large with respect to $n$, then any $N\times N$ real matrix contains an $n\times 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 $8n^2\times 2^{n^{4+o(1)}}$ matrix contains an $n\times n$ submatrix, in which every row is mononote. On the other hand, there exist $n^{2}/6\times 2^{2^{n^{1-o(1)}}}$ matrices containing no such submatrix . Comment: 10 pages, 1 figure |
| Databáze: | arXiv |
| Externí odkaz: |
|