Semi-Algebraic Colorings of Complete Graphs

Authors Jacob Fox, János Pach, Andrew Suk



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.36.pdf
  • Filesize: 440 kB
  • 12 pages

Document Identifiers

Author Details

Jacob Fox
  • Stanford University, 450 Serra Mall, Building 380, Stanford, CA 94305, USA
János Pach
  • École Polytechnique Fédérale de Lausanne, CH-1015 Lausanne, Switzerland,
  • Rényi Institute, Hungarian Academy of Sciences, Budapest, Hungary
Andrew Suk
  • University of California San Diego, 9500 Gilman Dr, La Jolla, CA 92093, USA

Cite AsGet BibTex

Jacob Fox, János Pach, and Andrew Suk. Semi-Algebraic Colorings of Complete Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 36:1-36:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.36

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 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 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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
Keywords
  • Semi-algebraic graphs
  • Ramsey theory
  • regularity lemma

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. N. Alon, J. Pach, R. Pinchasi, R. Radoičić, and M. Sharir. Crossing patterns of semi-algebraic sets. J. Combin. Theory Ser. A, 111:310-326, 2005. Google Scholar
  2. S. Basu, R. Pollack, and M.-R. Roy. Algorithms in Real Algebraic Geometry. Springer-Verlag, Berlin, 2003. Google Scholar
  3. B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theor. Comput. Sci., 84:77-105, 1991. Google Scholar
  4. D. Conlon, J. Fox, C. Lee, and B. Sudakov. The Erdős-Gyárfás problem on generalized Ramsey numbers. Proc. Lond. Math. Soc., 110:1-15, 2015. Google Scholar
  5. D. Conlon, J. Fox, J. Pach, B. Sudakov, and A. Suk. Ramsey-type results for semi-algebraic relations. Trans. Amer. Math. Soc., 366:5043-5065, 2014. Google Scholar
  6. P. Erdős. Solved and unsolved problems in combinatorics and combinatorial number theory. Proc. 12th Southeastern Conf. on Combinatorics, Graph Theory and Computing, (Baton Rouge, La.), Congr. Numer., 1:49-62, 1981. Google Scholar
  7. P. Erdős and A. Gyárfás. A variant of the classical Ramsey problem. Combinatorica, 17:459-467, 1997. Google Scholar
  8. J. Fox, M. Gromov, V. Lafforgue, A. Naor, and J. Pach. Overlap properties of geometric expanders. J. Reine Angew. Math. (Crelle’s Journal), 671:49-83, 2012. Google Scholar
  9. J. Fox, J. Pach, A. Sheffer, A. Suk, and J. Zahl. A semi-algebraic version of Zarankiewicz’s problem. J. Eur. Math. Soc., 19:1785-1810, 2017. Google Scholar
  10. J. Fox, J. Pach, and A. Suk. A polynomial regularity lemma for semi-algebraic hypergraphs and its applications in geometry and property testing. SIAM J. Comput., 45:2199-2223, 2016. Google Scholar
  11. J. Fox, J. Pach, and A. Suk. More distinct distances under local conditions. Combinatorica, 38:501-509, 2018. Google Scholar
  12. J. Fox and B. Sudakov. Ramsey-type problem for an almost monochromatic K₄. SIAM J. Discrete Math., 23:155-162, 2008. Google Scholar
  13. W. T. Gowers. Lower bounds of tower type for Szemerédi’s uniformity lemma. Geom. Funct. Anal., 7:322-337, 1997. Google Scholar
  14. V. Koltun. Almost tight upper bounds for vertical decompositions in four dimensions. J. ACM, 51:699-730, 2004. Google Scholar
  15. A. V. Kostochka and D. Mubayi. When is an almost monochromatic K₄ guaranteed? Combin. Probab. Comput., 17:823-830, 2008. Google Scholar
  16. J. Matoušek. Lectures on Discrete Geometry. Springer-Verlag, New York, 2002. Google Scholar
  17. D. Mubayi. Edge-coloring cliques with three colors on all 4-cliques. Combinatorica, 18:293-296, 1998. Google Scholar
  18. F. Ramsey. On a problem in formal logic. Proc. London Math. Soc., 30:264-286, 1930. Google Scholar
  19. I. Schur. Über die Kongruenz x^m + y^m = z^mmod p. Jahresber. Deutch. Math. Verein., 25:114-117, 1916. Google Scholar
  20. A. Suk. Semi-algebraic Ramsey numbers. J. Combin. Theory Ser. B, 116:465-483, 2016. Google Scholar
  21. E. Szemerédi. Regular partitions of graphs. Problémes Combinatoires et Théorie des Graphes, Orsay (1976), 260:299-401, 1976. Google Scholar
  22. X. Xiaodong, X. Zheng, G. Exoo, and S.P. Radziszowski. Constructive lower bounds on classical multicolor Ramsey numbers. Electron. J. Combin., 11, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail