On Zero-sum Ramsey numbers of complete bipartite graphs

Abstract

For an integer $q\ge 2$ and a graph $F$ satisfying $q\mid e(F)$, the zero-sum Ramsey number $R(F,{\mathbb{Z}}_q)$ is the least integer $n$ such that every edge-labeling $w:E(K_n)\to {\mathbb{Z}}_q$ contains a copy of $F$ whose edge-label sum is zero in ${\mathbb{Z}}_q$. Write $K_{s,t}$ for the complete bipartite graph with $s$ vertices on one side and $t$ vertices on the other side. We prove that for every $q\ge 2$, there is an explicit threshold $S(q)$ such that $R(K_{s,qk},{\mathbb{Z}}_q)=s+qk$ for all $s\ge S(q)$ and all $k\ge 1$. We also determine the zero-sum Ramsey number of $K_{s,3k}$ over ${\mathbb{Z}}_3$ for all $s\ge 2$ and $k\ge 1$. We prove that $R(K_{s,3k},{\mathbb{Z}}_3)=s+3k$, except when $s=2$ and $k\ge 1$, or when $s\in \{3,4,5,7\}$ and $k=1$. In these exceptional cases, $R(K_{s,3k},{\mathbb{Z}}_3)=s+3k+1$. In particular, this shows that the threshold $S(q)$ is best possible for \(q=3\).