Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1

DOI10.1215/00127094-2785915MaRDI QIDQ461340zbMATH OpenOpenAlexFDO

Authors Boris Bukh, Jiří Matoušek

Publication date 10 October 2014

Published in Duke Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.0705, https://projecteuclid.org/euclid.dmj/1410789515

zbMATH Keywords

geometric Ramsey-type questions

Mathematics Subject Classification ID

Ramsey theory (05D10) Combinatorial complexity of geometric structures (52C45)

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 nondecreasing 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_1ge 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_{i_1},...,b_{i_k}) 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 ErdH{o}s--Szekeres, there is a constant C such that ES_Phi(n) < exp(exp(Cn)). Second, there is an algorithm that, given Phi, decides whether it is Erdos-Szekeres; thus, one-dimensional Erdos-Szekeres-style theorems can in principle be proved automatically.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q461340)