Suk, Andrew
Semialgebraic Ramsey Numbers
Abstract
Given a finite set P of points from R^d, a kary semialgebraic relation E on P is the set of ktuples 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 Nelement point set P in R^d equipped with a kary semialgebraic relation E, such that E has complexity at most t, contains s members such that every ktuple induced by them is in E, or n members such that every ktuple 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 Ramseytype problem on hyperplane arrangements in R^d. We also study multicolor Ramsey numbers for triangles in our semialgebraic setting, achieving some partial results.
BibTeX  Entry
@InProceedings{suk:LIPIcs:2015:5095,
author = {Andrew Suk},
title = {{Semialgebraic Ramsey Numbers}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {5973},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897835},
ISSN = {18688969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5095},
URN = {urn:nbn:de:0030drops50955},
doi = {10.4230/LIPIcs.SOCG.2015.59},
annote = {Keywords: Ramsey theory, semialgebraic relation, onesided hyperplanes, Schur numbers}
}
2015
Keywords: 

Ramsey theory, semialgebraic relation, onesided hyperplanes, Schur numbers 
Seminar: 

31st International Symposium on Computational Geometry (SoCG 2015)

Issue date: 

2015 
Date of publication: 

2015 