Lower Bounds for Book Ramsey Numbers

2024/10/04 by Wesley, William J. · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2410.03625

Abstract

We prove new bounds for Ramsey numbers for book graphs B_n. In particular, we show that R(B_n-1,B_n) = 4n-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).

Cited by

• New bounds for some small multicolor Ramsey numbers
• Asymptotically Smaller Encodings for Graph Problems and Scheduling

Related

• Small Ramsey numbers for books, wheels, and generalizations
• The Ramsey number of the 4-cycle versus a book graph
• New bounds for Ramsey numbers R(K_k-e,K_l-e)
• Ramsey numbers of quadrilateral versus books
• Ramsey numbers of books and quasirandomness