A Note on the Erdős-Szekeres Theorem in Two Dimensions

Abstract

Burkill and Mirsky, and Kalmanson prove independently that, for every $r\ge 2, n\ge 1$, there is a sequence of $r^{2^n}$ vectors in $\mathbb R^n$, which does not contain a subsequence of $r+1$ vectors $v^1, v^2,\dots,v^{r+1}$ such that, for every $i$ between 1 and $n$, $(v^{j}_i)_{1\le j\le r+1}$ forms a monotone sequence. Moreover, $r^{2^n}$ is the largest integer with this property. In this short note, for two vectors $u = (u_1, u_2,\dots, u_n)$ and $v = (v_1, v_2, \dots, v_n)$ in $\mathbb{R}^n$, we say that $u\le v$ if, for every $i$ between 1 and $n$, $u_i\le v_i$. Just like Burkill and Mirsky, and Kalmanson, for every $k, \ell\ge 1, d\ge 2$ we find the maximal $N_1, N_2$ (which turn out to be equal) such that there are numerical two-dimensional arrays of size $(k+\ell-1)\times N_1$ and $(k+\ell)\times N_2$, which neither contain a subarray of size $k\times d$, whose columns form an increasing sequence of $d$ vectors in $\mathbb{R}^k$, nor contain a subarray of size $\ell\times d$, whose columns form a decreasing sequence of $d$ vectors in $\mathbb{R}^{\ell}$. In a consequent discussion, we consider a generalisation of this setting and make a connection with a famous problem in coding theory.