We exhibit sequences of n points in d dimensions with no long monotone subsequences, by which we mean when projected in a general direction, our sequence has no monotone subsequences of length sq root n + d or more. Previous work proved that this function of n would lie between sq root n and 2 sq root n; this paper establishes that the coefficient of sq root n is one. This resolves the question of how the Erdos Szekeres result that a (one-dimensional) sequence has monotone subsequences of at most sq root n generalizes to higher dimensions.
展开▼
