REAL

Semi-algebraic colorings of complete graphs

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

[img] 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 Edit Item