Semi-algebraic Ramsey numbers

Given a finite point set P subset of R-d, a k-ary semi-algebraic relation B on P is a set of k-tuples of points in P determined by a finite number of polynomial equations and inequalities in kd real variables. The description complexity of such a relation is at most t if the number of polynomials and their degrees are all bounded by t. The Ramsey number R-k(d,t)(s,n) is the minimum N such that any N-element point set P in R-d equipped with a k-ary semi-algebraic relation E of complexity at most t contains s members such that every k-tuple induced by them is in E or n members such that every k-tuple induced by them is not in E. We give a new upper bound for R-k(d,t)(s,n) for k >= 3 and s fixed. In particular, we show that for fixed integers d,t,s R-3(d,t) (s, n) <= 2(no(1)) establishing a subexponential upper bound on R-3(d,t) (s,n). This improves the previous bound of 2(nC1) due to Conlon, Fox, Pach, Sudakov, and Suk where C1 depends on d and t, and improves upon the trivial bound of 2(nC2) which can be obtained by applying classical Ramsey numbers where C-2 depends on s. As an application, we give new estimates for a recently studied Ramsey-type problem on hyperplane arrangements in R-d. We also study multi-color Ramsey numbers for triangles in our semi-algebraic setting, achieving some partial results. (C) 2015 Elsevier Inc. All rights reserved.