Monotone Subsequences in Any Dimension

We exhibit sequences ofnpoints inddimensions with no long monotone subsequences, by which we mean when projected in a general direction, our sequence has no monotone subsequences of lengthn+dor more. Previous work proved that this function ofnwould lie betweennand 2 n; this paper establishes that the coefficient ofnis one. This resolves the question of how the Erdős–Szekeres result that a (one-dimensional) sequence has monotone subsequences of at mostngeneralizes to higher dimensions.