Lower Bounds for Book Ramsey Numbers

William J. Wesley

doi:10.1016/j.disc.2025.114913

paper

Lower Bounds for Book Ramsey Numbers

arXiv:2410.03625 · doi:10.1016/j.disc.2025.114913

Abstract

We prove new bounds for Ramsey numbers for book graphs $B_{n}$ . In particular, we show that $R (B_{n - 1}, B_{n}) = 4 n - 1$ for an infinite family of $n$ using a block-circulant construction similar to Paley graphs. We obtain improved bounds for several other values of $R (B_{r}, B_{s})$ using different block-circulant graphs from SAT and integer programming (IP) solvers. Finally, we enumerate the number of critical graphs for $R (B_{r}, B_{s})$ for small $r$ and $s$ using SAT modulo symmetries (SMS).

Some minor edits and typo corrections. R(B2,B13) added