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

DOI10.1215/00127094-2785915zbMATH Open1301.05351arXiv1207.0705OpenAlexW1971456489MaRDI QIDQ461340FDOQ461340

Authors: Boris Bukh, Jiří Matoušek 

Publication date: 10 October 2014

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

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.

Full work available at URL: https://arxiv.org/abs/1207.0705

Recommendations

• scientific article; zbMATH DE number 4213982
• Ramsey-remainder for convex sets and the Erdős-Szekeres theorem
• The Erdős-Szekeres problem and an induced Ramsey question
• On a Ramsey-type problem of Erdős and Pach
• On a Ramsey-type problem of Erdős and Pach
• A Ramsey-style extension of a theorem of Erdős and Hajnal
• scientific article; zbMATH DE number 4045866
• Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem
• On a Ramsey-Turán variant of the Hajnal-Szemerédi theorem
• A dichotomy result for Ramsey quantifiers

zbMATH Keywords

geometric Ramsey-type questions

Mathematics Subject Classification ID

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

Cites Work

• Crossing patterns of semi-algebraic sets
• Title not available (Why is that?)
• Algorithms in real algebraic geometry
• Title not available (Why is that?)
• The empty hexagon theorem
• Empty convex hexagons in planar point sets
• Overlap properties of geometric expanders
• The Erdos-Szekeres problem on points in convex position – a survey
• Title not available (Why is that?)
• Stabbing simplices by points and flats
• Higher-order Erdős-Szekeres theorems
• Ramsey-type results for semi-algebraic relations
• The colored Tverberg's problem and complexes of injective functions
• On the number of halving planes
• An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs
• Betti numbers of semialgebraic sets defined by quantifier-free formulae
• One-sided epsilon-approximants

Cited In (20)

• Cutting lemma and Zarankiewicz's problem in distal structures
• Ramsey-Turán numbers for semi-algebraic graphs
• Ramsey properties of algebraic graphs and hypergraphs
• Ramsey-type results for semi-algebraic relations
• Ramsey numbers of semi-algebraic and semi-linear hypergraphs
• Lexicographic Ramsey theory
• On general position sets in Cartesian products
• The Erdős-Szekeres Problem
• The general position number of integer lattices
• Erdős-Szekeres type theorems for ordered uniform matchings
• Predicates whose maximal length functions increase periodically
• Ordered unavoidable sub-structures in matchings and random matchings
• Ramsey growth in some NIP structures
• Sharp thresholds for a phase transition related to weakly increasing sequences
• Convex polygons in Cartesian products
• An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets
• Three-monotone interpolation
• Phase Transitions for Weakly Increasing Sequences
• Erdős-Szekeres results for set partitions
• Semi-algebraic Ramsey numbers

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)