@article{22176,
  abstract     = {The Ramsey number r(G,H) is the minimum N such that every graph on N vertices contains G as a subgraph or its complement contains H as a subgraph. For integers n≥k≥1, the k-book Bk,n is the graph on n vertices consisting of a copy of Kk, called the spine, as well as n−k additional vertices each adjacent to every vertex of the spine and non-adjacent to each other. A connected graph H on n vertices is called p-good if r(Kp,H)=(p−1)(n−1)+1. Nikiforov and Rousseau proved that if n is sufficiently large in terms of p and k, then Bk,n is p-good. Their proof uses Szemerédi's regularity lemma and gives a tower-type bound on n. We give a short new proof that avoids using the regularity method and shows that every Bk,n with n≥2k10p is p-good.
Using Szemerédi's regularity lemma, Nikiforov and Rousseau also proved much more general goodness-type results, proving a tight bound on r(G,H) for several families of sparse graphs G and H as long as |V(G)|<δ|V(H)| for a small constant δ>0. Using our techniques, we prove a new result of this type, showing that r(G,H)=(p−1)(n−1)+1 when H=Bk,n and G is a complete p-partite graph whose first p−1 parts have constant size and whose last part has size δn, for some small constant δ>0. Again, our proof does not use the regularity method, and thus yields double-exponential bounds on δ.
},
  author       = {Fox, Jacob and He, Xiaoyu and Wigderson, Yuval},
  issn         = {2517-5599},
  journal      = {Advances in Combinatorics},
  publisher    = {Alliance of Diamond Open Access Journals},
  title        = {{Ramsey goodness of books revisited}},
  doi          = {10.19086/aic.2023.4},
  year         = {2023},
}