We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in Rd. A k-ary semialgebraic predicate Φ(x1, . . . , xk) on ℝd is a Boolean combination of polynomial equations and inequalities in the kd coordinates of k points x1, . . . ,xk ε ℝd. A sequence P = (p1, . . . , pn) of points in ℝd is called Φ-homogeneous if either Φ(pi1 , . . . , pik) holds for all choices 1 ≤ i1 < · · · < ik ≤ n, or it holds for no such choice. The Ramsey function RΦ(n) is the smallest N such that every point sequence of length N contains a Φ-homogeneous subsequence of length n. Conlon et al. [Trans. Amer. Math. Soc., 366 (2013), pp. 5043-5065] constructed the first examples of semialgebraic predicates with the Ramsey function bounded from below by a tower function of arbitrary height: for every k ≥ 4, they exhibit a k-ary Φ in dimension 2k-4 with RΦ bounded below by a tower of height k-1. We reduce the dimension in their construction, obtaining a k-ary semialgebraic predicate Φ on Rk-3 with RΦ bounded below by a tower of height k-1. We also provide a natural geometric Ramsey-type theorem with a large Ramsey function. We call a point sequence P in ℝd order-type homogeneous if all (d +1)-tuples in P have the same orientation. Every sufficiently long point sequence in general position in ℝd contains an order-type homogeneous subsequence of length n, and the corresponding Ramsey function has recently been studied in several papers. Together with a recent work of Bárány, Matoušek, and Pór [Curves in ℝd Intersecting Every Hyperplane at Most d+1 Times, preprint, arXiv:1309.1147; extended abstract in Proceedings of the 30th Annual Symposium on Computational Geometry, 2014], our results imply a tower function of Ω(n) of height d as a lower bound, matching an upper bound by Suk up to the constant in front of n.

Lower bounds on geometric Ramsey functions

Elias, Marek
;
2014

Abstract

We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in Rd. A k-ary semialgebraic predicate Φ(x1, . . . , xk) on ℝd is a Boolean combination of polynomial equations and inequalities in the kd coordinates of k points x1, . . . ,xk ε ℝd. A sequence P = (p1, . . . , pn) of points in ℝd is called Φ-homogeneous if either Φ(pi1 , . . . , pik) holds for all choices 1 ≤ i1 < · · · < ik ≤ n, or it holds for no such choice. The Ramsey function RΦ(n) is the smallest N such that every point sequence of length N contains a Φ-homogeneous subsequence of length n. Conlon et al. [Trans. Amer. Math. Soc., 366 (2013), pp. 5043-5065] constructed the first examples of semialgebraic predicates with the Ramsey function bounded from below by a tower function of arbitrary height: for every k ≥ 4, they exhibit a k-ary Φ in dimension 2k-4 with RΦ bounded below by a tower of height k-1. We reduce the dimension in their construction, obtaining a k-ary semialgebraic predicate Φ on Rk-3 with RΦ bounded below by a tower of height k-1. We also provide a natural geometric Ramsey-type theorem with a large Ramsey function. We call a point sequence P in ℝd order-type homogeneous if all (d +1)-tuples in P have the same orientation. Every sufficiently long point sequence in general position in ℝd contains an order-type homogeneous subsequence of length n, and the corresponding Ramsey function has recently been studied in several papers. Together with a recent work of Bárány, Matoušek, and Pór [Curves in ℝd Intersecting Every Hyperplane at Most d+1 Times, preprint, arXiv:1309.1147; extended abstract in Proceedings of the 30th Annual Symposium on Computational Geometry, 2014], our results imply a tower function of Ω(n) of height d as a lower bound, matching an upper bound by Suk up to the constant in front of n.
2014
Elias, Marek; Matousek, Jiri; Roldan-Pensado, Edgardo; Safernova, Zuzana
File in questo prodotto:
File Dimensione Formato  
1307.5157.pdf

accesso aperto

Tipologia: Documento in Pre-print (Pre-print document)
Licenza: Creative commons
Dimensione 186.52 kB
Formato Adobe PDF
186.52 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11565/4044269
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 6
social impact