科研之友
微信
新浪微博
Facebook
分享链接
摘要
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. In the setting of the present paper, we express this lemma by saying that the set of predicates Phi = {x(1) < x(2), 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) under bar of real numbers has an n-term subsequence (b) under bar such that at least one of the Phi(j) holds everywhere on (b) under bar 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 (and sometimes they are indeed doubly exponential): for every Phi that is Erdos-Szekeres, there is a constant C such that ES Phi (n) <= 2(2Cn). 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). This setting includes many results and problems in geometric Ramsey theory, and it appears considerably more involved. 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.
- 出版日期2014-9-15
