Large book--cycle Ramsey numbers


Abstract in English

Let $B_n^{(k)}$ be the book graph which consists of $n$ copies of $K_{k+1}$ all sharing a common $K_k$, and let $C_m$ be a cycle of length $m$. In this paper, we first determine the exact value of $r(B_n^{(2)}, C_m)$ for $frac{8}{9}n+112le mle lceilfrac{3n}{2}rceil+1$ and $n geq 1000$. This answers a question of Faudree, Rousseau and Sheehan (Cycle--book Ramsey numbers, {it Ars Combin.,} {bf 31} (1991), 239--248) in a stronger form when $m$ and $n$ are large. Building upon this exact result, we are able to determine the asymptotic value of $r(B_n^{(k)}, C_n)$ for each $k geq 3$. Namely, we prove that for each $k geq 3$, $r(B_n^{(k)}, C_n)= (k+1+o_k(1))n.$ This extends a result due to Rousseau and Sheehan (A class of Ramsey problems involving trees, {it J.~London Math.~Soc.,} {bf 18} (1978), 392--396).

Download