License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.59
URN: urn:nbn:de:0030-drops-50955
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5095/
Go to the corresponding LIPIcs Volume Portal

Suk, Andrew

Semi-algebraic Ramsey Numbers

pdf-format:
12.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{suk:LIPIcs:2015:5095,
  author =	{Andrew Suk},
  title =	{{Semi-algebraic Ramsey Numbers}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{59--73},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5095},
  URN =		{urn:nbn:de:0030-drops-50955},
  doi =		{10.4230/LIPIcs.SOCG.2015.59},
  annote =	{Keywords: Ramsey theory, semi-algebraic relation, one-sided hyperplanes, Schur numbers}
}

Keywords: Ramsey theory, semi-algebraic relation, one-sided hyperplanes, Schur numbers
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI