2014/06/25 by Suk, Andrew · 1 citation
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1406.6550
Given a finite point set P ⊂ ℝd, a k-ary semi-algebraic relation E on P is the set of k-tuples of points in P, which is 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 Rd,tk(s,n) is the minimum N such that any N-element point set P in ℝd equipped with a k-ary semi-algebraic relation E, such that E has 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 Rd,tk(s,n) for k≥ 3 and s fixed. In particular, we show that for fixed integers d,t,s, Rd,t3(s,n) ≤ 2^no(1), establishing a subexponential upper bound on Rd,t3(s,n). This improves the previous bound of 2nC due to Conlon, Fox, Pach, Sudakov, and Suk, where C is a very large constant depending on d,t, and s. As an application, we give new estimates for a recently studied Ramsey-type problem on hyperplane arrangements in ℝd. We also study multi-color Ramsey numbers for triangles in our semi-algebraic setting, achieving some partial results.