Abstract

We considerm-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The casem= 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type results for intersection graphs of geometric objects and for other graphs arising in computational geometry. Considering larger values ofmis relevant, e.g., to problems concerning the number of distinct distances determined by a point set. Forp >= 3 andm >= 2, the classical Ramsey numberR(p; m) is the smallest positive integernsuch that anym-coloring of the edges ofK(n), thecompletegraph onnvertices, contains a monochromaticK(p). It is a longstanding open problem that goes back to Schur (1916) to decide whetherR(p; m) <= 2(cm), wherec = c(p). We prove that this is true if each color class is defined semi-algebraically 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 Szemeredi-type regularity lemma for multicolored semi-algebraic graphs, which is of independent interest. The same technique is used to address the semi-algebraic variant of a more general Ramsey-type problem of Erdos and Shelah.

Details

Actions