Ramsey-type results for semi-algebraic relations
A k-ary semi-algebraic relation E on ℝ_d is a subset of ℝ_(kd), the set of k-tuples of points in ℝ_(d), which is determined by a finite number of polynomial inequalities in kd real variables. The description complexity of such a relation is at most t if d, k ≤ t and the number of polynomials and their degrees are all bounded by t. A set A ⊂ ℝ_d is called homogeneous if all or none of the k-tuples from A satisfy E. A large number of geometric Ramsey-type problems and results can be formulated as questions about finding large homogeneous subsets of sets in ℝ_d equipped with semi-algebraic relations. In this paper, we study Ramsey numbers for k-ary semi-algebraic relations of bounded complexity and give matching upper and lower bounds, showing that they grow as a tower of height k − 1. This improves upon a direct application of Ramsey's theorem by one exponential and extends a result of Alon, Pach, Pinchasi, Radoičić, and Sharir, who proved this for k = 2. We apply our results to obtain new estimates for some geometric Ramsey-type problems relating to order types and one-sided sets of hyperplanes. We also study the off-diagonal case, achieving some partial results.
Additional Information© Copyright 2014 American Mathematical Society. The copyright for this article reverts to public domain 28 years after publication. Received by the editors January 1, 2013 and, in revised form, May 7, 2013. Article electronically published on March 5, 2014. The first author was supported by a Royal Society University Research Fellowship. The second author was supported by a Packard Fellowship, by a Simons Fellowship, by an Alfred P. Sloan Fellowship, by NSF grant DMS-1069197, and by an MIT NEC Corporation Award. The third author was supported by Swiss National Science Foundation Grants 200021-137574 and 200020-144531, by Hungarian Science Foundation Grant OTKA NN 102029 under the EuroGIGA programs ComPoSe and GraDR, and by NSF grant CCF-08-30272. The fourth author's research was supported in part by NSF grant DMS-1101185 and by a USA-Israel BSF grant. The fifth author was supported by an NSF Postdoctoral Fellowship and by Swiss National Science Foundation Grant 200021-125287/1
Submitted - 1301.0074.pdf