A Multidimensional Generalization of the Erdős–Szekeres Lemma on Monotone Subsequences

Abstract

We consider an extension of the Monotone Subsequence lemma of Erdős and Szekeres in higher dimensions. Let v¹,…,vⁿ ∈ ℝ^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, vⁱ_k < vⁱ_k if and only if ^{[srarr ]}c_k = 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.