Ramsey numbers for multiple copies of sparse graphs

被引:0
作者
Sulser, Aurelio [1 ,3 ]
Trujic, Milos [2 ]
机构
[1] Swiss Fed Inst Technol, Dept Math, Zurich, Switzerland
[2] Swiss Fed Inst Technol, Inst Theoret Comp Sci, Zurich, Switzerland
[3] Swiss Fed Inst Technol, Dept Math, CH-8092 Zurich, Switzerland
基金
瑞士国家科学基金会;
关键词
absorbing method; disjoint union; Ramsey theory; sparse graphs; BIPARTITE GRAPHS; DIAGONAL RAMSEY; THEOREMS;
D O I
10.1002/jgt.23100
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For a graph H $H$ and an integer n $n$, we let n H $nH$ denote the disjoint union of n $n$ copies of H $H$. In 1975, Burr, Erdos and Spencer initiated the study of Ramsey numbers for n H $nH$, one of few instances for which Ramsey numbers are now known precisely. They showed that there is a constant c = c( H ) $c=c(H)$ such that r(n H ) =(2 divide H divide - alpha( H ) ) n + c $r(nH)=(2| H| -\alpha (H))n+c$, provided n $n$ is sufficiently large. Subsequently, Burr gave an implicit way of computing c $c$ and noted that this long-term behaviour occurs when n $n$ is triply exponential in divide H divide $| H| $. Very recently, Bucic and Sudakov revived the problem and established an essentially tight bound on n $n$ by showing r(n H ) $r(nH)$ follows this behaviour already when the number of copies is just a single exponential. We provide significantly stronger bounds on n $n$ in case H $H$ is a sparse graph, most notably of bounded maximum degree. These are relatable to the current state-of-the-art bounds on r( H ) $r(H)$ and (in a way) tight. Our methods rely on a beautiful classic proof of Graham, Rodl and Rucinski, with an emphasis on developing an efficient absorbing method for bounded degree graphs.
引用
收藏
页码:843 / 870
页数:28
相关论文
共 35 条
[1]   Turan numbers of bipartite graphs and related Ramsey-Type questions [J].
Alon, N ;
Krivelevich, M ;
Sudakov, B .
COMBINATORICS PROBABILITY & COMPUTING, 2003, 12 (5-6) :477-494
[2]  
[Anonymous], 1984, Graph Theory and Combinatorics (Cambridge, 1983)
[3]  
Bucicand M., 2023, Adv. Comb., V1, DOI [10.19086/aic.2023.1, DOI 10.19086/AIC.2023.1]
[4]  
Burr S., 1975, INFINITE FINITE SETS, V10, P215
[5]   RAMSEY THEOREMS FOR MULTIPLE COPIES OF GRAPHS [J].
BURR, SA ;
ERDOS, P ;
SPENCER, JH .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1975, 209 (AUG) :87-99
[6]   ON THE RAMSEY NUMBERS R(G,NH) AND R(NG,NH) WHEN N IS LARGE [J].
BURR, SA .
DISCRETE MATHEMATICS, 1987, 65 (03) :215-229
[7]  
Campos M., 2023, ARXIV230309521
[8]  
Chung F., 1999, HIS LEGACY UNSOLVED
[9]   THE RAMSEY NUMBER OF A GRAPH WITH BOUNDED MAXIMUM DEGREE [J].
CHVATAL, C ;
RODL, V ;
SZEMEREDI, E ;
TROTTER, WT .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1983, 34 (03) :239-243
[10]  
CONLON D., 2015, London Math. Soc. Lecture Note Ser., V424, P49