Abstract
We consider mcolorings of the edges of a complete graph, where each color class is defined semialgebraically with bounded complexity. The case m = 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramseytype results for intersection graphs of geometric objects and for other graphs arising in computational geometry. Considering larger values of m is relevant, e.g., to problems concerning the number of distinct distances determined by a point set.
For p >= 3 and m >= 2, the classical Ramsey number R(p;m) is the smallest positive integer n such that any mcoloring of the edges of K_n, the complete graph on n vertices, contains a monochromatic K_p. It is a longstanding open problem that goes back to Schur (1916) to decide whether R(p;m)=2^{O(m)}, for a fixed p. We prove that this is true if each color class is defined semialgebraically with bounded complexity, and that the order of magnitude of this bound is tight. Our proof is based on the Cutting Lemma of Chazelle et al., and on a Szemeréditype regularity lemma for multicolored semialgebraic graphs, which is of independent interest. The same technique is used to address the semialgebraic variant of a more general Ramseytype problem of Erdös and Shelah.
BibTeX  Entry
@InProceedings{fox_et_al:LIPIcs:2019:10440,
author = {Jacob Fox and J{\'a}nos Pach and Andrew Suk},
title = {{SemiAlgebraic Colorings of Complete Graphs}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {36:136:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771047},
ISSN = {18688969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10440},
URN = {urn:nbn:de:0030drops104401},
doi = {10.4230/LIPIcs.SoCG.2019.36},
annote = {Keywords: Semialgebraic graphs, Ramsey theory, regularity lemma}
}
Keywords: 

Semialgebraic graphs, Ramsey theory, regularity lemma 
Collection: 

35th International Symposium on Computational Geometry (SoCG 2019) 
Issue Date: 

2019 
Date of publication: 

11.06.2019 