论文标题
关于所有周期的拉姆齐的大小与路径
On the size Ramsey number of all cycles versus a path
论文作者
论文摘要
我们说$ g \ to（\ Mathcal {c}，p_n）$如果$ g-e（f）$包含$ n $ -VERTEX PATH $ P_N $对于任何分散的森林$ f \ subset g $。大小ramsey编号$ \ hat {r}（\ Mathcal {c}，p_n）$是最小的整数$ m $，因此存在一个图$ g $，带有$ m $ edges，$ g \ to $ g \ to（\ nathcal {c}，p_n）$。 Dudek，Khoeini和Prałat证明，对于足够大的$ n $，$ 2.0036n \ le \ hat {r}（\ Mathcal {c}，p_n）\ le 31n $。在本说明中，我们将下限和上限提高到$ 2.066n \ le \ hat {r}（\ Mathcal {C}，p_n），p_n）\ le 5.25n+o（1）。$我们的上界的构造与dudek，khoeini和prałat的构造完全不同。我们还有一个计算机辅助证明上限$ \ hat {r}（\ mathcal {c}，p_n）\ le \ frac {75} {19} {19} n +o（1）<3.947n $。
We say $G\to (\mathcal{C}, P_n)$ if $G-E(F)$ contains an $n$-vertex path $P_n$ for any spanning forest $F\subset G$. The size Ramsey number $\hat{R}(\mathcal{C}, P_n)$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges for which $G\to (\mathcal{C}, P_n)$. Dudek, Khoeini and Prałat proved that for sufficiently large $n$, $2.0036n \le \hat{R}(\mathcal{C}, P_n)\le 31n$. In this note, we improve both the lower and upper bounds to $2.066n\le \hat{R}(\mathcal{C}, P_n)\le 5.25n+O(1).$ Our construction for the upper bound is completely different than the one considered by Dudek, Khoeini and Prałat. We also have a computer assisted proof of the upper bound $\hat{R}(\mathcal{C}, P_n)\le \frac{75}{19}n +O(1) < 3.947n $.
