Lower Bounds on Geometric Ramsey Functions

Abstract

We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in $\mathbb{R}^d$. A $k$-ary semialgebraic predicate $\Phi(x_1,\ldots,x_k)$ on $\mathbb{R}^d$ is a Boolean combination of polynomial equations and inequalities in the $kd$ coordinates of $k$ points $x_1,\ldots,x_k\in\mathbb{R}^d$. A sequence $P=(p_1,\ldots,p_n)$ of points in $\mathbb{R}^d$ is called $\Phi$-homogeneous if either $\Phi(p_{i_1}, \ldots,p_{i_k})$ holds for all choices $1\le i_1<\cdots<i_k\le n$, or it holds for no such choice. The Ramsey function $R_\Phi(n)$ is the smallest $N$ such that every point sequence of length $N$ contains a $\Phi$-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\ge 4$, they exhibit a $k$-ary $\Phi$ in dimension $2^{k-4}$ with $R_\Phi$ bounded below by a tower of height k-1. We reduce the dimension in their construction, obtaining a $k$-ary semialgebraic predicate $\Phi$ on $\mathbb{R}^{k-3}$ with $R_\Phi$ 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 $\mathbb{R}^d$ order-type homogeneous if all (d+1)-tuples in $P$ have the same orientation. Every sufficiently long point sequence in general position in $\mathbb{R}^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 $\mathbb{R}^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 $\Omega(n)$ of height $d$ as a lower bound, matching an upper bound by Suk up to the constant in front of $n$.

Locations

• SIAM Journal on Discrete Mathematics - View
• arXiv (Cornell University) - View - PDF