2013/07/19 by Marek Eliáš, Jiří Matoušek, Eliáš, Marek +6
Computer Science · Mathematics · #05D10 (Primary) #52C45 (Secondary) #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05D10 #msc:52C45
paper · pdf · doi:10.48550/arxiv.1307.5157
12 pages
openalex publication_date 2013/07/19 · arxiv created 2014/01/07 · arxiv updated 2014/01/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in ℝd. 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, Fox, Pach, Sudakov, and Suk 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 ℝk-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, 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.