文章基本信息
- 标题：Bounded VC-Dimension Implies the Schur-ErdÅ's Conjecture
- 本地全文：下载
- 作者：Jacob Fox ; J{'a}nos Pach ; Andrew Suk 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：164
- 页码：46:1-46:8
- DOI：10.4230/LIPIcs.SoCG.2020.46
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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â,f. 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.
- 关键词：Ramsey theory; VC-dimension; Multicolor Ramsey numbers
