标题： 稀疏图与路径或环的Ramsey数 显示英文标题

标题： Ramsey numbers for sparse graphs versus path or cycle

摘要： 对于任何整数$k\ge3$，令$G$是一个具有$n\ge \Omega(k^4)$个顶点且边数不超过$(1+\frac{1}{ck^2})n$的连通图，其中$c>0$是一个常数，而$P_k$或$C_k$是一个具有$k$个顶点的路径或环。 在本文中我们证明，如果$k$是奇数，则$r(G,C_k)=2n-1$。 此外，\[ r(G,P_k)=\max\left\{n+\left\lfloor\frac k2\right\rfloor-1, n+k-2-\alpha'-\gamma\right\}, \]其中$\alpha'$是适当子图$G$的独立数，而$\gamma=0$如果$k-1$整除$n+k-3-\alpha'$，否则$\gamma=1$。 我们在$n$方面的界限相对于$k$显著优于 Burr、Erdős、Faudree、Rousseau 和 Schelp ({\em 美国数学学会通报}269 (1982), 501--512) 建立的先前界限$n\ge \Omega(k^{10})$（第一个结果）和$n\ge \Omega(k^{12})$（第二个结果）。此外，对$G$中边数的限制被放宽。这是40多年来首次取得改进。 显示英文摘要

摘要： For any integer $k\ge3$, let $G$ be a connected graph with $n\ge \Omega(k^4)$ vertices and no more than $(1+\frac{1}{ck^2})n$ edges where $c>0$ is a constant, and $P_k$ or $C_k$ a path or cycle with $k$ vertices. In this paper we prove that if $k$ is odd then $r(G,C_k)=2n-1$. Moreover, \[ r(G,P_k)=\max\left\{n+\left\lfloor\frac k2\right\rfloor-1, n+k-2-\alpha'-\gamma\right\}, \] where $\alpha'$ is the independence number of an appropriate subgraph of $G$ and $\gamma=0$ if $k-1$ divides $n+k-3-\alpha'$ and $\gamma=1$ otherwise. Our bound on $n$ in terms of $k$ significantly improves upon the previous bounds $n\ge \Omega(k^{10})$ (from the first result) and $n\ge \Omega(k^{12})$ (from the second result) established by Burr, Erd\H{o}s, Faudree, Rousseau and Schelp ({\em Trans. Amer. Math. Soc.} 269 (1982), 501--512). % Moreover, the restriction on the number of edges in $G$ is relaxed. This is the first improvement in over 40 years.