Fox, J. and Pach, János and Suk, A.
(2019)
*Semi-algebraic colorings of complete graphs.*
In:
35th International Symposium on Computational Geometry, SoCG 2019.
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Dagstuhl.
ISBN 9783959771047

Text
1505.07429 Download (200kB) |

## Abstract

We consider m-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The case m = 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 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 m-coloring of the edges of Kn, the complete graph on n vertices, contains a monochromatic Kp. It is a longstanding open problem that goes back to Schur (1916) to decide whether R(p; m) = 2O(m), for a fixed 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 Szemerédi-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 Erdős and Shelah. © Jacob Fox, János Pach, and Andrew Suk.

Item Type: | Book Section |
---|---|

Additional Information: | Stanford University, 450 Serra Mall, Building 380, Stanford, CA 94305, United States École Polytechnique Fédérale de Lausanne, Lausanne, CH-1015, Switzerland Rényi Institute, Hungarian Academy of Sciences, Budapest, Hungary University of California San Diego, 9500 Gilman Dr, La Jolla, CA 92093, United States Conference code: 148855 Export Date: 5 October 2019 Funding details: Alfred P. Sloan Foundation Funding details: National Sleep Foundation, NSF, DMS 1352121 Funding details: Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung, SNF, 200021-165977, 200020-162884 Funding text 1: Funding Jacob Fox: Supported by a Packard Fellowship and by NSF CAREER award DMS 1352121. János Pach: Supported by Swiss National Science Foundation grants 200020-162884 and 200021-165977. Andrew Suk: Supported by an NSF CAREER award and an Alfred Sloan Fellowship. Stanford University, 450 Serra Mall, Building 380, Stanford, CA 94305, United States École Polytechnique Fédérale de Lausanne, Lausanne, CH-1015, Switzerland Rényi Institute, Hungarian Academy of Sciences, Budapest, Hungary University of California San Diego, 9500 Gilman Dr, La Jolla, CA 92093, United States Conference code: 148855 Export Date: 18 October 2019 Funding details: Alfred P. Sloan Foundation Funding details: National Sleep Foundation, NSF, DMS 1352121 Funding details: Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung, SNF, 200021-165977, 200020-162884 Funding text 1: Funding Jacob Fox: Supported by a Packard Fellowship and by NSF CAREER award DMS 1352121. János Pach: Supported by Swiss National Science Foundation grants 200020-162884 and 200021-165977. Andrew Suk: Supported by an NSF CAREER award and an Alfred Sloan Fellowship. |

Uncontrolled Keywords: | Computational geometry; Algebra; Graph theory; Ramsey theory; Ramsey theory; Complete graphs; Positive integers; Graphic methods; Geometric objects; Intersection graph; Regularity lemma; Regularity lemma; Bounded complexity; Semi-algebraic graphs; Algebraic graph; |

Subjects: | Q Science / természettudomány > QA Mathematics / matematika |

SWORD Depositor: | MTMT SWORD |

Depositing User: | MTMT SWORD |

Date Deposited: | 19 Oct 2019 04:39 |

Last Modified: | 19 Oct 2019 04:39 |

URI: | http://real.mtak.hu/id/eprint/102418 |

### Actions (login required)

Edit Item |