---
OA_place: repository
OA_type: green
_id: '22176'
abstract:
- lang: eng
  text: "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.\r\nUsing 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 δ.\r\n"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
  full_name: Fox, Jacob
  last_name: Fox
- first_name: Xiaoyu
  full_name: He, Xiaoyu
  last_name: He
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Fox J, He X, Wigderson Y. Ramsey goodness of books revisited. <i>Advances in
    Combinatorics</i>. 2023. doi:<a href="https://doi.org/10.19086/aic.2023.4">10.19086/aic.2023.4</a>
  apa: Fox, J., He, X., &#38; Wigderson, Y. (2023). Ramsey goodness of books revisited.
    <i>Advances in Combinatorics</i>. Alliance of Diamond Open Access Journals. <a
    href="https://doi.org/10.19086/aic.2023.4">https://doi.org/10.19086/aic.2023.4</a>
  chicago: Fox, Jacob, Xiaoyu He, and Yuval Wigderson. “Ramsey Goodness of Books Revisited.”
    <i>Advances in Combinatorics</i>. Alliance of Diamond Open Access Journals, 2023.
    <a href="https://doi.org/10.19086/aic.2023.4">https://doi.org/10.19086/aic.2023.4</a>.
  ieee: J. Fox, X. He, and Y. Wigderson, “Ramsey goodness of books revisited,” <i>Advances
    in Combinatorics</i>. Alliance of Diamond Open Access Journals, 2023.
  ista: Fox J, He X, Wigderson Y. 2023. Ramsey goodness of books revisited. Advances
    in Combinatorics.
  mla: Fox, Jacob, et al. “Ramsey Goodness of Books Revisited.” <i>Advances in Combinatorics</i>,
    Alliance of Diamond Open Access Journals, 2023, doi:<a href="https://doi.org/10.19086/aic.2023.4">10.19086/aic.2023.4</a>.
  short: J. Fox, X. He, Y. Wigderson, Advances in Combinatorics (2023).
date_created: 2026-06-29T10:58:11Z
date_published: 2023-07-29T00:00:00Z
date_updated: 2026-07-14T09:05:44Z
day: '29'
doi: 10.19086/aic.2023.4
extern: '1'
external_id:
  arxiv:
  - '2109.09205'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2109.09205
month: '07'
oa: 1
oa_version: Preprint
publication: Advances in Combinatorics
publication_identifier:
  eissn:
  - 2517-5599
publication_status: published
publisher: Alliance of Diamond Open Access Journals
quality_controlled: '1'
scopus_import: '1'
status: public
title: Ramsey goodness of books revisited
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...