Star-critical Ramsey numbers involving large generalized books

Source abstract

For graphs $F$, $G$, and $H$, we write $F \to (G, H)$ if every red/blue edge-coloring of $F$ contains either a red copy of $G$ or a blue copy of $H$. The Ramsey number $R(G, H)$ is the smallest integer $N$ such that $K_N \to (G, H)$. Let $H := K_k + nK_h$ be the generalized book graph, and let $G := K_{p+1}(a_1, a_2, \dots, a_{p+1})$ be a complete $(p+1)$-partite graph satisfying $a_1 = 1$, $a_2 \mid (nh-1)$, and $a_i \le a_{i+1}$. In this paper, avoiding the use of Szemerédi's regularity lemma, we prove that for any fixed $h, p \ge 1$, $k \ge 2$, and sufficiently large $n$, $K_{p(nh + a_2k - 1) + 1} \setminus K_{1, nh - a_2(h-2) - 1}\to(G, H).$ This result yields the star-critical Ramsey number $r_*(G, H) = (p-1)(nh + a_2k - 1) + a_2(k + h - 2) + 1.$