Bipartite Ramsey theory

For bipartite graphs G₁, G₂, . . . , G_k, the bipartite Ramsey number 6(G₁, G₂, . . . ,G_k) is the least positive integer b so that any colouring of the edges of K_b,b with k colours will result in a copy of G_i in the ith colour for some i. If G_i = G for each i, we let b_k(G) = b(G₁,G₂, . . .,G_k). If G_i ≅ K_ni,ni for each i, we let b(n1, n₂, . . ., n_k) = b(K_n1,n1,K_n2,n2, . . . K_nk,nk). For all integers n ≥ 1, b(1, n) = n. Beineke and Schwenk [1] showed that b(2, 2) = 5 and b(3, 3) = 17. We show that b(2, 3) = 9 and b(2, 4) = 14. To date these are the only known values for b(m, n) for 1 ≤ m ≤ n. Using the probabilistic method, and a result of Irving [14] or Thomason [20], we show that the value lim b(n, n)^1/n lies between √2 and 2. Determination of this limit is an open problem. For integers m ≥ 2 and n ≥ 2, we show that b(m, n) ≤ b(m - 1, n) + b(m, n - 1) + 1. We show that for every two positive integers m and n, (matrix presented). When n is large compared with m, there has been no serious improvement of this upper bound for the value of b(m, n). For all integers k ≥ 2, we show that b_k(K_2,2) ≤ k² + k - 1. The bipartite Ramsey number b(G₁,G₂, . . . ,G_k) is investigated for various classes of graphs G_i.