Small Ramsey Numbers for Books, Wheels, and Generalizations

Abstract

We describe applications of a range of different computational methods to Ramsey numbers. We use flag algebras, local search, bottom-up generation, and enumeration of polycirculant graphs.

These methods are applied to Ramsey numbers for books and wheels. We also initiate the study of generalized small Ramsey numbers. Let $GR(r,K_s,t)$ denote the minimum number of vertices $n$ such that any $r$-edge-coloring of $K_n$ has a copy of $K_s$ with at most $t$ colors.

We establish over 20 new bounds including exact determination of the Ramsey numbers $R(W_5, W_7) = 15$, $R(W_5, W_9) = 18$, $R(B_2, B_8) = 21$, $R(B_3, B_7) = 20$, $GR(3,K_4,2) = 10$, and $GR(4,K_4,3) = 10$.