×

Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1. (English) Zbl 1301.05351

Summary: A classical and widely used lemma of Erdős and Szekeres asserts that for every \(n\) there exists \(N\) such that every \(N\)-term sequence \(\underline{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\geq x_2\}\) is Erdős-Szekeres with Ramsey function \(\mathrm{ES}_\Phi (n)=(n-1)^2+1\). In general, we consider an arbitrary finite set \(\Phi=\{\Phi_1,\dots,\Phi_m\}\) of semialgebraic predicates, meaning that each \(\Phi_j=\Phi_j(x_1,\dots,x_k)\) is a Boolean combination of polynomial equations and inequalities in some number \(k\) of real variables. We define {\(\Phi\)} to be Erdős-Szekeres if for every \(n\) there exists \(N\) such that each \(N\)-term sequence \(\underline{a}\) of real numbers has an \(n\)-term subsequence \(\underline{b}\) such that at least one of the \(\Phi_j\) holds everywhere on \(\underline{b}\), which means that \(\Phi_j(b_{i_1},\dots,b_{i_k})\) holds for every choice of indices \(i_1,i_2,\dots,i_k\), \(1\leq i_1<i_2<\cdots<i_k\leq n\). We write \(\mathrm{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 Erdős-Szekeres, there is a constant \(C\) such that \(\mathrm{ES}_\Phi (n)\leq 2^{2^{C_n}}\). Second, there is an algorithm that, given {\(\Phi\)}, decides whether it is Erdős-Szekeres; thus, 1-dimensional Erdős-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 \(\mathbb 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 \(\mathbb R^d\) (i.e., conjunctions of polynomial equations), as well as for a multipartite version of the problem with arbitrary semialgebraic predicates in \(\mathbb R^d\).

MSC:

05D10 Ramsey theory
52C45 Combinatorial complexity of geometric structures
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] N. Alon, J. Pach, R. Pinchasi, R. Radoičić, and M. Sharir, Crossing patterns of semi-algebraic sets , J. Combin. Theory Ser. A 111 (2005), 310-326. · Zbl 1099.14048
[2] I. Bárány, Z. Füredi, and L. Lovász, On the number of halving planes , Combinatorica 10 (1990), 175-183. · Zbl 0718.52009
[3] S. Basu, R. Pollack, and M.-F. Roy, Algorithms in Real Algebraic Geometry , Algorithms Comput. Math. 10 , Springer, Berlin, 2003. · Zbl 1031.14028
[4] J. Bochnak, M. Coste, and M.-F. Roy, Real Algebraic Geometry , Ergeb. Math. Grenzgeb. (3) 36 , Springer, Berlin, 1998.
[5] B. Bukh, P.-S. Loh, and G. Nivasch, One-sided epsilon-approximants , in preparation. · Zbl 1387.05178
[6] B. Bukh, J. Matoušek, and G. Nivasch, Stabbing simplices by points and flats , Discrete Comput. Geom. 43 (2010), 321-338. · Zbl 1186.52001
[7] B. Bukh, J. Matoušek, and G. Nivasch, Lower bounds for weak epsilon-nets and stair-convexity , Israel J. Math. 182 (2011), 199-208. · Zbl 1222.68395
[8] D. Conlon, J. Fox, J. Pach, B. Sudakov, and A. Suk, Ramsey-type results for semi-algebraic relations , to appear in Trans. Amer. Math. Soc., preprint, [math.CO]. 1301.0074v1 · Zbl 1306.14027
[9] M. Eliáš and J. Matoušek, Higher-order Erdős-Szekeres theorems , Adv. Math. 244 (2013), 1-15. · Zbl 1283.05175
[10] P. Erdős and G. Szekeres, A combinatorial problem in geometry , Compos. Math. 2 (1935), 463-470. · Zbl 0012.27010
[11] J. Fox, M. Gromov, V. Lafforgue, A. Naor, and J. Pach, Overlap properties of geometric expanders , J. Reine Angew. Math. 671 (2012), 49-83. · Zbl 1306.05171
[12] A. Gabrielov and N. Vorobjov, Betti numbers of semialgebraic sets defined by quantifier-free formulae , Discrete Comput. Geom. 33 (2005), 395-401. · Zbl 1073.14072
[13] T. Gerken, Empty convex hexagons in planar point sets , Discrete Comput. Geom. 39 (2008), 239-272. · Zbl 1184.52016
[14] R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey Theory , 2nd ed., Wiley, New York, 1990.
[15] J. Matoušek, Lectures on Discrete Geometry , Grad. Texts in Math. 212 , Springer, New York, 2002.
[16] W. Morris and V. Soltan, The Erdős-Szekeres problem on points in convex position-a survey , Bull. Amer. Math. Soc. (N.S.) 37 (2000), 437-458. · Zbl 0958.52018
[17] C. M. Nicolás, The empty hexagon theorem , Discrete Comput. Geom. 38 (2007), 389-397. · Zbl 1146.52010
[18] S. Puddu and J. Sabia, An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs , J. Pure Appl. Algebra 129 (1998), 173-200. · Zbl 0929.68132
[19] D. A. Rosenthal, The classification of the order indiscernibles of real closed fields and other theories , Ph.D. dissertation, University of Wisconsin, Madison, Wis., 1981.
[20] M. J. Steele, “Variations on the monotone subsequence theme of Erdős and Szekeres” in Discrete Probability and Algorithms (Minneapolis, 1993) , IMA Vol. Math. Appl. 72 , Springer, New York, 1995, 111-131. · Zbl 0832.60012
[21] A. Tarski, A Decision Method for Elementary Algebra and Geometry , 2nd ed., Univ. of California Press, Berkeley, Calif., 1951. · Zbl 0044.25102
[22] R. T. Živaljević and S. T. Vrećica, The colored Tverberg’s problem and complexes of injective functions , J. Combin. Theory Ser. A 61 (1992), 309-318. · Zbl 0782.52003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.