Bounded VC-Dimension Implies the Schur-Erdos Conjecture

被引:3
作者
Fox, Jacob [1 ]
Pach, Janos [2 ,3 ,4 ]
Suk, Andrew [5 ]
机构
[1] Stanford Univ, Stanford, CA 94305 USA
[2] Renyi Inst, Budapest, Hungary
[3] IST Austria, Vienna, Austria
[4] MIPT, Moscow, Russia
[5] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA
基金
奥地利科学基金会;
关键词
05D10;
D O I
10.1007/s00493-021-4530-9
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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-3. He showed that r(3; m) <= O(m!), and a simple construction demonstrates that r(3; m) >= 2(omega(m)). An old conjecture of Erdos states that r(3; m) = 2(Theta(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.
引用
收藏
页码:803 / 813
页数:11
相关论文
共 22 条
  • [1] Crossing patterns of semi-algebraic sets
    Alon, N
    Pach, J
    Pinchasi, R
    Radoicic, R
    Sharir, M
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 2005, 111 (02) : 310 - 326
  • [2] [Anonymous], 1964, Proc. Amer. Math. Soc, DOI DOI 10.2307/2034050
  • [3] [Anonymous], 1949, Izvestiya Akad. Nauk SSSR. Ser. Mat.
  • [4] A SINGLY EXPONENTIAL STRATIFICATION SCHEME FOR REAL SEMIALGEBRAIC VARIETIES AND ITS APPLICATIONS
    CHAZELLE, B
    EDELSBRUNNER, H
    GUIBAS, LJ
    SHARIR, M
    [J]. THEORETICAL COMPUTER SCIENCE, 1991, 84 (01) : 77 - 105
  • [5] Chung F. R. K., 1973, Discrete Mathematics, V5, P317, DOI 10.1016/0012-365X(73)90125-8
  • [6] RAMSEY-TYPE THEOREMS
    ERDOS, P
    HAJNAL, A
    [J]. DISCRETE APPLIED MATHEMATICS, 1989, 25 (1-2) : 37 - 52
  • [7] Erdos P, 1938, MITT FORSCH I MATH M, V2, P74
  • [8] Fox J., Israel Journal of Mathematics
  • [9] Erds-Hajnal Conjecture for Graphs with Bounded VC-Dimension
    Fox, Jacob
    Pach, Janos
    Suk, Andrew
    [J]. DISCRETE & COMPUTATIONAL GEOMETRY, 2019, 61 (04) : 809 - 829
  • [10] A semi-algebraic version of Zarankiewicz's problem
    Fox, Jacob
    Pach, Janos
    Sheffer, Adam
    Suk, Andrew
    Zahl, Joshua
    [J]. JOURNAL OF THE EUROPEAN MATHEMATICAL SOCIETY, 2017, 19 (06) : 1785 - 1810