scientific article; zbMATH DE number 1092064
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.
- The Erdős-Ko-Rado theorem for integer sequences
- scientific article; zbMATH DE number 3929687
- Erdős and arithmetic progressions
- On a Theorem of Erdos and Turan
- A generalisation of a theorem of Erdős and Niven
- An Erdős-Ko-Rado theorem for integer sequences of given rank
- A remark on a theorem of Erdős
- On a theorem of Erdős and Fuchs
- scientific article; zbMATH DE number 3895160
- On a theorem of Erdős and Sárközy
- Erdős-Szekeres theorem for cyclic permutations
- A note on the Erdős-Szekeres theorem in two dimensions
- On Monotone Subsequences
- Erdős-Szekeres tableaux
- On the number of monotone sequences
- On Erdős' theorem for monotonic subsequences
- The Erdős-Ko-Rado theorem for integer sequences
- Nondecreasing subsequences of t-sequences
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4367331)