





















Let $n\geqν$, let $T$ be an $n$-vertex tree with bipartition class sizes $t_1\geq t_2$, and let $S$ be a $ν$-vertex tree with bipartition class sizes $τ_1\geqτ_2$. Using four natural constructions, we show that the Ramsey number $R(T,S)$ is lower bounded by $\underline{R}(T,S)=\max\{n+τ_2,ν+\min\{t_2,ν\},\min\{2t_1,2ν\},2τ_1\}-1$. Our main result shows that there exists a constant $c>0$, such that for all sufficiently large integers $n\geqν$, if (i) $Δ(T)\leq cn/\log n$ and $Δ(S)\leq cν/\logν$, (ii) $τ_2\geq t_2$, and (iii) $ν\geq t_1$, then $R(T,S)=\underline{R}(T,S)$. In particular, this determines the exact Ramsey numbers for a large family of pairs of trees. We also provide examples showing that $R(T,S)$ can exceed $\underline{R}(T,S)$ if any one of the three assumptions (i), (ii), and (iii) is removed.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。