Ramsey-type results for semi-algebraic relations

Abstract:

A $k$-ary semi-algebraic relation $E$ on $\mathbb {R}^d$ is a subset of $\mathbb {R}^{kd}$, the set of $k$-tuples of points in $\mathbb {R}^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 \leq t$ and the number of polynomials and their degrees are all bounded by $t$. A set $A\subset \mathbb {R}^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 $\mathbb {R}^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.