On the Ramsey problem for multicolor bipartite graphs

Given i,j positive integers, let K-i,K-j denote a bipartite complete graph and let R-r(m, n) be the smallest integer a such that for any r-coloring of the edges of K-a,K-a one can always find a monochromatic subgraph isomorphic to K-m,K-n. In other words, if a greater than or equal to R-r(m, n) then every matrix a x a with entries in {0, 1,..., r - 1} always contains a submatrix m x n or n x m whose entries are i, 0 less than or equal to i less than or equal to r - 1. We shall prove that R-2(m, n) less than or equal to 2(m)(n - 1) + 2(m-1) - 1, Which generalizes the previous results R-2(2, n) less than or equal to 4n - 3 and R-2(3, n) less than or equal to 8n - 5 due to Beineke and Schwenk. Moreover, we find a class of lower bounds based on properties of orthogonal Latin squares which establishes that lim(r --> infinity) R-r(2, 2)r(-2) = 1. (C) 1999 Academic Press.