No label defined (Q4367331)

In 1935 Erdős and Szekeres proved that in every sequence composed of \(mn+1\) distinct integers, there exists either a decreasing subsequence longer than \(m\) or an increasing one longer than \(n\). In the present paper, the author proves a stronger form of this theorem: Let \(L^-\) and \(L^+\) be the lengths of the longest decreasing subsequence and the longest increasing subsequence in \(a_1,a_2,\dots,a_n\). Then \[ (1)\qquad L^+L^-\geq n\qquad\text{and} \qquad(2)\qquad L^++ L^-\geq 2\sqrt n. \] We merely mention (2) follows from (1) by the arithmetic mean inequality and (1) from the following simple observation: let the map \(\varphi: a_i\to(\ell^-_i,\ell^+_i)\) \((i=1,2,\dots, n)\), where \(\ell^-_i\) (resp. \(\ell^+_i\)) is the length of the maximal decreasing (resp. increasing) subsequence of \(\{a_i\}^n_{i= 1}\) starting at \(a_i\). Thus \(\varphi:\{a_i\}^n_{i= 1}\to\{(\ell^-_i, \ell^+_i): 1\leq \ell^-_i\leq L^-, 1\leq\ell^+_i\leq L^+\}\). Furthermore, it is easy to see that \(\varphi\) is injective, which gives (1) immediately.