Title |
Monotone Subsequences in R.
^{d}
| |

Author |
Laura Heinrich-Litan.
| |

Abstract |
This paper investigates the length of the longest
monotone subsequence of a set of n points in R.
A sequence of points in ^{d}R is called monotone in ^{d}R
if it is monotone with respect to some order
from ${\cal R}_{d}=\{\leq,\geq\}^d$, with other words
if it is monotone in each dimension $i\in \{1,\ldots,d\}$.
The main result of this paper is the construction of a set ^{d}P
which has no monotone subsequences of length larger then
$\lceil n^{\frac{1}{2^{d-1}}}\ \rceil$.
This generalizes to higher dimensions the Erdos-Szekeres result
that there is a 2-dimensional set of n points
which has monotone subsequences of length at most $\lceil\sqrt{n}\ \rceil$.
| |

Downloading | [ps] [pdf] |