A New View of Bipartite Ramsey Numbers

Abstract

For a bipartite graph $G$ and a positive integer $s$, the $s$-bipartite Ramsey number $B{R}_s(G)$ of $G$ is the minimum integer $t$ with $t\ge s$ for which every red-blue coloring of $K_{s,t}$ results in a monochromatic $G$. A formula is established for $B{R}_s(K_{r,r})$ when $s\in \{2r–1,2r\}$ when $r\ge 2$. The $s$-bipartite Ramsey numbers are studied for $K_{3,3}$ and various values of $s$. In particular, it is shown that $B{R}_5(K_{3,3})=41$ when $s\in \{5,6\}$, $B{R}_s(K_{3,3})=29$ when $s\in \{7,8\}$, and $17\le B{R}_{10}(K_{3,3})\le 23$.