Document Open Access Logo

Bounded VC-Dimension Implies the Schur-Erdős Conjecture

Authors Jacob Fox, János Pach, Andrew Suk

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.46.pdf
  • Filesize: 436 kB
  • 8 pages

Document Identifiers

Author Details

Jacob Fox
  • Department of Mathematics, Stanford University, Stanford, CA, USA
János Pach
  • Alfréd Rényi Institute of Mathematics, Budapest, Hungary
  • IST, Vienna, Austria
  • MIPT, Moscow, Russia
Andrew Suk
  • Department of Mathematics, University of California San Diego, La Jolla, CA, USA

Funding

  • Fox, Jacob: Supported by a Packard Fellowship and by NSF award DMS-1855635.
  • Pach, János: Supported by Austrian Science Fund (FWF) grant Z 342-N31 and by the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926.
  • Suk, Andrew: Supported by NSF CAREER award DMS-1800746 and an Alfred Sloan Fellowship.

Cite AsGet BibTex

Jacob Fox, János Pach, and Andrew Suk. Bounded VC-Dimension Implies the Schur-Erdős Conjecture. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 46:1-46:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.46

Abstract

In 1916, Schur introduced the Ramsey number r(3;m), which is the minimum integer n > 1 such that for any m-coloring of the edges of the complete graph K_n, there is a monochromatic copy of K₃. He showed that r(3;m) ≤ O(m!), and a simple construction demonstrates that r(3;m) ≥ 2^Ω(m). An old conjecture of Erdős states that r(3;m) = 2^Θ(m). In this note, we prove the conjecture for m-colorings with bounded VC-dimension, that is, for m-colorings with the property that the set system induced by the neighborhoods of the vertices with respect to each color class has bounded VC-dimension.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
Keywords
  • Ramsey theory
  • VC-dimension
  • Multicolor Ramsey numbers

Metrics

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

References

  1. N. Alon, J. Pach, R. Pinchasi, R. Radoičić, and M. Sharir. Crossing patterns of semi-algebraic sets. J. Comb. Theory, Ser. A, 111:310-326, 2005. URL: https://doi.org/10.1016/j.jcta.2004.12.008.
  2. B. Chazelle, H. Edelsbrunner, L. J. Guibas, and M. Sharir. A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theor. Comput. Sci., 84:77-105, 1991. URL: https://doi.org/10.1016/0304-3975(91)90261-Y.
  3. F. Chung and R. Graham. Erdős on Graphs: His Legacy of Unsolved Problems. A K Peters Series. Taylor & Francis, 1998. URL: https://books.google.com/books?id=Doc_ErUTDcAC.
  4. F. R. K. Chung. On the ramsey numbers n(3, 3, ...3;2). Discret. Math., 5:317-321, 1973. URL: https://doi.org/10.1016/0012-365X(73)90125-8.
  5. Paul Erdős. On sequences of integers no one of which divides the product of two others and on some related problems. Inst. Math. Mech. Univ. Tomsk, 2:74-82, 1938. Google Scholar
  6. P. Erdős and A. Hajnal. Ramsey-type theorems. Discret. Appl. Math., 25:37-52, 1989. URL: https://doi.org/10.1016/0166-218X(89)90045-0.
  7. J. Fox, M. Gromov, V. Lafforgue, A. Naor, and J. Pach. Overlap properties of geometric expanders. Reine Angew. Math. (Crelle’s Journal), 2012:49-83, 2010. URL: https://doi.org/10.1515/CRELLE.2011.157.
  8. J. Fox, J. Pach, A. Sheffer, A. Suk, and J. Zahl. A semi-algebraic version of Zarankiewicz’s problem. J. Eur. Math. Soc. (JEMS), 19:1785-1810, 2014. URL: https://doi.org/10.4171/JEMS/705.
  9. J. Fox, J. Pach, and A. Suk. A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing. SIAM J. Computing, 45:2199-2223, 2015. URL: https://doi.org/10.1137/15M1007355.
  10. J. Fox, J. Pach, and A. Suk. Erdős-Hajnal conjecture for graphs with bounded VC-dimension. Discret. Comput. Geom., 61:809-829, 2019. URL: https://doi.org/10.1007/s00454-018-0046-5.
  11. J. Fox, J. Pach, and A. Suk. The Schur-Erdős problem for semi-algebraic colorings. Israel J. Mathematics, to appear. Google Scholar
  12. L. Guth. Polynomial Methods in Combinatorics. University Lecture Series. Amer. Math. Soc., 2016. Google Scholar
  13. D. Haussler. Sphere packing numbers for subsets of the boolean n-cube with bounded Vapnik-Chervonenkis dimension. J. Comb. Theory, Ser. A, 69:217-232, 1995. Google Scholar
  14. D. Haussler and E. Welzl. epsilon-nets and simplex range queries. Discret. Comput. Geom., 2:127-151, 1987. URL: https://doi.org/10.1007/BF02187876.
  15. T. Kóvari, V. Sós, and P. Turán. On a problem of K. Zarankiewicz. Colloq. Math., 3:50-57, 1954. URL: http://eudml.org/doc/210011.
  16. J. Matouvsek. Lectures on discrete geometry, volume 212 of Graduate texts in mathematics. Springer, 2002. Google Scholar
  17. J. Milnor. On the betti numbers of real varieties. Proc. Amer. Math. Soc., 15:257-280, 1964. Google Scholar
  18. I. G. Petrovskii and O. A. Oleinik. On the topology of real algebraic surfaces (russian). Izv. Akad. Nauk SSSR Ser. Mat., 13:389-402, 1949. Google Scholar
  19. I. Schur. Über die Kongruenz x^m + y^m = z^m (mod p). Jber. Deutsch. Math. Verein., 25:114-116, 1917. URL: http://eudml.org/doc/145475.
  20. E. Szemerédi and W. T. Trotter. Extremal problems in discrete geometry. Combinatorica, 3:381-392, 1983. URL: https://doi.org/10.1007/BF02579194.
  21. V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16:264-280, 1971. URL: https://doi.org/10.1137/1116025.
  22. X. Xu, X. Zheng, G. Exoo, and S. P. Radziszowski. Constructive lower bounds on classical multicolor ramsey numbers. Electr. J. Comb., 11, 2004. URL: http://www.combinatorics.org/Volume_11/Abstracts/v11i1r35.html.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact