## Abstract

For bipartite graphs G_{1}, G_{2}, . . . , G_{k}, the bipartite Ramsey number 6(G_{1}, G_{2}, . . . ,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_{1},G_{2}, . . .,G_{k}). If G_{i} ≅ K_{ni,ni} for each i, we let b(n1, n_{2}, . . ., 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^{2} + k - 1. The bipartite Ramsey number b(G_{1},G_{2}, . . . ,G_{k}) is investigated for various classes of graphs G_{i}.

Original language | English |
---|---|

Pages (from-to) | 217-230 |

Number of pages | 14 |

Journal | Utilitas Mathematica |

Volume | 53 |

Publication status | Published - May 1998 |

Externally published | Yes |

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty
- Applied Mathematics