Bipartite Ramsey theory

Johannes H. Hattingh, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

50 Citations (Scopus)

Abstract

For bipartite graphs G1, G2, . . . , Gk, the bipartite Ramsey number 6(G1, G2, . . . ,Gk) is the least positive integer b so that any colouring of the edges of Kb,b with k colours will result in a copy of Gi in the ith colour for some i. If Gi = G for each i, we let bk(G) = b(G1,G2, . . .,Gk). If Gi ≅ Kni,ni for each i, we let b(n1, n2, . . ., nk) = b(Kn1,n1,Kn2,n2, . . . Knk,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 bk(K2,2) ≤ k2 + k - 1. The bipartite Ramsey number b(G1,G2, . . . ,Gk) is investigated for various classes of graphs Gi.

Original languageEnglish
Pages (from-to)217-230
Number of pages14
JournalUtilitas Mathematica
Volume53
Publication statusPublished - May 1998
Externally publishedYes

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Bipartite Ramsey theory'. Together they form a unique fingerprint.

Cite this