We consider an extension of the Monotone Subsequence lemma of Erdős and Szekeres in higher dimensions. Let v1,…,vn ∈ ℝd be a sequence of real vectors. For a subset I ⊆ [n] and vector [srarr ]c ∈ {0,1}d we say that I is [srarr ]c-free if there are no i < j ∈ I, such that, for every k = 1,…,d, vik < vik if and only if [srarr ]ck = 0. We construct sequences of vectors with the property that the largest [srarr ]c-free subset is small for every choice of [srarr ]c. In particular, for d = 2 the largest [srarr ]c-free subset is O(n⅝) for all the four possible [srarr ]c. The smallest possible value remains far from being determined.

We also consider and resolve a simpler variant of the problem.