A note on the Erdős-Szekeres theorem in two dimensions (Q2030741): Difference between revisions

Summary: \textit{H. Burkill} and \textit{L. Mirsky} [Discrete Math. 6, 15--28 (1973; Zbl 0357.05011)], and \textit{K. Kalmanson} [J. Comb. Theory, Ser. A 15, 343--346 (1973; Zbl 0362.05027)] prove independently that, for every \(r\geqslant 2, n\geqslant 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\leqslant 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\leqslant v\) if, for every \(i\) between 1 and \(n, u_i\leqslant v_i\). Just like Burkill and Mirsky, and Kalmanson, for every \(k, \ell\geqslant 1, d\geqslant 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.