Edge-coloring $K_{n,n}$ with no 2-colored $C_{2k}$

Abstract

The generalized Ramsey number $r(G,H,q)$ is the minimum number of colors needed to color the edges of $G$ such that every isomorphic copy of $H$ has at least $q$ colors. In this note, we improve the upper and lower bounds on $r(K_{n,n},C_{2k},3)$. Our upper bound answers a question of Lane and Morrison. For $k=3$ we obtain the asymptotically sharp estimate $r(K_{n,n},C_6,3)=\frac{7}{20}n+o(n)$.

13 pages. Comments welcome!