2026-07-26T00:33:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5095 2024-03-06T10:35:50Z ddc:004 open_access

Semi-algebraic Ramsey Numbers Suk, Andrew Ramsey theory semi-algebraic relation one-sided hyperplanes Schur numbers Given a finite set P of points from R^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 R^{d,t}_k(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, 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 R^{d,t}_k(s,n) for k=3 and s fixed. In particular, we show that for fixed integers d,t,s, R^{d,t}_3(s,n)=2^{n^{o(1)}}, establishing a subexponential upper bound on R^{d,t}_3(s,n). This improves the previous bound of 2^{n^C} 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 R^d. We also study multi-color Ramsey numbers for triangles in our semi-algebraic setting, achieving some partial results. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrew Suk 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.59 urn:nbn:de:0030-drops-50955 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.59 eng https://creativecommons.org/licenses/by/3.0/legalcode