论文标题
稀疏图的多个副本的Ramsey编号
Ramsey numbers for multiple copies of sparse graphs
论文作者
论文摘要
对于图$ h $和一个整数$ n $，我们让$ nh $表示不一紧密的联盟 $ n $副本的$ h $。 1975年，伯尔（Burr），埃尔德（Erd）和斯宾塞（Spencer）启动了这项研究 $ nh $的拉姆齐号码，这是拉姆齐号码为少数情况之一 现在正好知道。他们表明有一个常数$ c = c（h）$，这样 $ r（nh）=（2 | h |-α（h））n + c $，前提是$ n $足够大。 随后，伯尔给出了一种隐含的计算$ c $的方式，并指出了这一点 当$ n $以$ | h | $为$ n $时，就会发生长期行为。非常 最近，Bucić和Sudakov恢复了问题，并确定了一个 本质上是通过显示$ r（NH）$的$ n $的紧密束缚，遵循此行为 当副本数量只是一个指数时。我们提供 如果$ h $是稀疏图，大多数 值得注意的最大程度。这些与当前状态相关 艺术在$ r（h）$和（在某种程度上）紧密地界定。我们的方法依靠美丽 Graham，Rödl和Ruciński的经典证明，重点是 为有界度图开发有效的吸收方法。
For a graph $H$ and an integer $n$, we let $nH$ denote the disjoint union of $n$ copies of $H$. In 1975, Burr, Erdős, and Spencer initiated the study of Ramsey numbers for $nH$, one of few instances for which Ramsey numbers are now known precisely. They showed that there is a constant $c = c(H)$ such that $r(nH) = (2|H| - α(H))n + c$, provided $n$ is sufficiently large. Subsequently, Burr gave an implicit way of computing $c$ and noted that this long term behaviour occurs when $n$ is triply exponential in $|H|$. Very recently, Bucić and Sudakov revived the problem and established an essentially tight bound on $n$ by showing $r(nH)$ follows this behaviour already when the number of copies is just a single exponential. We provide significantly stronger bounds on $n$ in case $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)$ and (in a way) tight. Our methods rely on a beautiful classic proof of Graham, Rödl, and Ruciński, with the emphasis on developing an efficient absorbing method for bounded degree graphs.
