Bounded VC-Dimension Implies the Schur-Erdős Conjecture
Bounded VC-Dimension Implies the Schur-Erdős Conjecture
复制标题
有界 VC 维意味着 Schur-ErdÅs 猜想
DOI：
10.1007/s00493-021-4530-9
复制
发表时间：
2021
期刊：
影响因子：
1.1
通讯作者：
Suk, Andrew
中科院分区：
文献类型：
--
作者：
Fox, Jacob;Pach, János;Suk, Andrew
1916年，Schur引入了Ramsey数r（3;m），它是最小整数n> 1，使得对于完全图Kn的边的任意m-着色，存在K3的单色副本。他证明了r（3;m）≤O（m！），一个简单的构造证明了r（3;m）≥ 2Ω（m）。一个古老的Erdans猜想指出r（3;m）= 2Θ（m）。本文证明了VC维数有界的猜想形式染色，即由每个色类的顶点邻域诱导的集合系统具有VC维数有界的性质的形式染色。
In 1916, Schur introduced the Ramsey numberr(3;m), which is the minimum integern> 1 such that for anym-coloring of the edges of the complete graphKn, there is a monochromatic copy ofK3. He showed thatr(3;m) ≤O(m!), and a simple construction demonstrates thatr(3;m) ≥ 2Ω(m). An old conjecture of Erdős states thatr(3;m) = 2Θ(m). In this note, we prove the conjecture form-colorings with bounded VC-dimension, that is, form-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.
登录
查看更多内容
DOI：
10.1090/ulect/064
发表时间：
2016-07
期刊：
--
影响因子：
--
作者：
L. Guth
通讯作者：
L. Guth
半代数着色的 Schur-ErdÅs 问题
影响因子：
1
作者：
Fox, Jacob;Pach, János;Suk, Andrew
通讯作者：
Suk, Andrew
几何扩展器的重叠特性
DOI：
--
发表时间：
2010
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
J. Fox;M. Gromov;V. Lafforgue;A. Naor;J. Pach
通讯作者：
J. Pach
实半代数簇的单指数分层方案及其应用
影响因子：
1.1
作者：
B. Chazelle;H. Edelsbrunner;L. Guibas;M. Sharir
通讯作者：
M. Sharir