Ramsey goodness of books revisited

DOI10.19086/AIC.2023.4MaRDI QIDQ6378019zbMATH OpenFDO

Authors Jacob Fox, Xiaoyu He, Yuval Wigderson

Publication date 19 September 2021

Full work available at URL https://doi.org/10.19086/AIC.2023.4

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 $ngeqkgeq1$, the $k$-book $B_{k,n}$ is the graph on $n$ vertices consisting of a copy of $K_k$, 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(K_p,H)=(p-1)(n-1)+1$. Nikiforov and Rousseau proved that if $n$ is sufficiently large in terms of $p$ and $k$, then $B_{k,n}$ is $p$-good. Their proof uses Szemer'edi'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 $B_{k,n}$ with $ngeq{2}^{k^{10p}}$ is $p$-good. Using Szemer'edi'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)|<delta|V(H)|$ for a small constant $delta>0$. Using our techniques, we prove a new result of this type, showing that $r(G,H)=(p-1)(n-1)+1$ when $H=B_{k,n}$ and $G$ is a complete $p$-partite graph whose first $p-1$ parts have constant size and whose last part has size $deltan$, for some small absolute constant $delta>0$.

This page was built for publication: Ramsey goodness of books revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6378019)