Abstract
A classical and widely used lemma of Erdos and Szekeres asserts that for every n there exists N such that every N-term sequence a of real numbers contains an n-term increasing subsequence or an n-term nonincreasing subsequence; quantitatively, the smallest N with this property equals (n - 1)(2) + 1. We express this lemma by saying that the set of predicates Phi = {x(1) x(2)} is Erdos-Szekeres with Ramsey function ES Phi (n) = (n - 1)(2) + 1.
In general, we consider an arbitrary finite set Phi = {Phi(1), ... , Phi(m)} of semialgebraic predicates, meaning that each Phi(j) = Phi(j) (x(1), ... , x(k)) is a Boolean combination of polynomial equations and inequalities in some number k of real variables. We define Phi to be Erdos-Szekeres if for every n there exists N such that each N-term sequence (a) of real numbers has an n-term subsequence (b) such that at least one of the Phi(j) holds everywhere on (b) which means that Phi(j) (b(i1), ... , b(ik)) holds for every choice of indices i(1), i(2), ..., i(k), 1 {= i(1) < i(2) < ... < i(k) {= n.
We write ES Phi (n) for the smallest N with the above property. We prove two main results.
First, the Ramsey functions in this setting are at most doubly exponential. Second, there is an algorithm that, given Phi, decides whether it is Erdos-Szekeres; thus, 1-dimensional Erdos-Szekeres-style theorems can in principle be proved automatically.
We regard these results as a starting point in investigating analogous questions for d-dimensional predicates, where instead of sequences of real numbers, we consider sequences of points in R-d (and semialgebraic predicates in their coordinates). Here we prove a decidability result for algebraic predicates in R-d (i.e., conjunctions of polynomial equations), as well as for a multipartite version of the problem with arbitrary semialgebraic predicates in R-d.