论文标题
在拉姆西尺寸线性图和相关问题上
On Ramsey size-linear graphs and related questions
论文作者
论文摘要
在本文中，我们证明了Ramsey数字$ R（H，F）的固定图$ H $和大图$ F $的几个结果，尤其是$ f = k_n $。这些结果扩展了Erdős，Faudree，Rousseau和Schelp以及Balister，Schelp和Simonovits在所谓的Ramsey尺寸线性图上的早期工作。除其他外，我们表明，如果$ h $是$ k_4 $的细分，至少是$ 6 $ vertices，则每个图$ f $ $ r（h，f）= o（v（f） + e（f））$。我们还猜想，如果$ h $是$ e（h） - v（h）\ leq \ binom {k+1} {2} {2} {2} -2 $，则$ r（h，k_n）= o（n^k）$。 Case $ K = 2 $由Erdős，Faudree，Rousseau和Schelp证明。我们证明了$ k = 3 $的情况。
In this paper we prove several results on Ramsey numbers $R(H,F)$ for a fixed graph $H$ and a large graph $F$, in particular for $F = K_n$. These results extend earlier work of Erdős, Faudree, Rousseau and Schelp and of Balister, Schelp and Simonovits on so-called Ramsey size-linear graphs. Among others, we show that if $H$ is a subdivision of $K_4$ with at least $6$ vertices, then $R(H,F) = O(v(F) + e(F))$ for every graph $F$. We also conjecture that if $H$ is a connected graph with $e(H) - v(H) \leq \binom{k+1}{2} - 2$, then $R(H,K_n) = O(n^k)$. The case $k=2$ was proved by Erdős, Faudree, Rousseau and Schelp. We prove the case $k=3$.
