Bipartite Ramsey numbers and Zarankiewicz numbers

Wayne Goddard, Michael A. Henning, Ortrud R. Oellermann

Research output: Contribution to journalArticlepeer-review

25 Citations (Scopus)

Abstract

The Zarankiewicz number z(s, m) is the maximum number of edges in a subgraph of K(s,s) that does not contain K(m,m) as a subgraph. The bipartite Ramsey number b(m,n) is the least positive integer b such that if the edges of K(b,b) are coloured with red and blue, then there always exists a blue K(m,m) or a red K(n,n). In this paper we calculate small exact values of z(s,2) and determine bounds for Zarankiewicz numbers in general. The latter are used to bound b(m,n) for m,n≤6.

Original languageEnglish
Pages (from-to)85-95
Number of pages11
JournalDiscrete Mathematics
Volume219
Issue number1-3
DOIs
Publication statusPublished - 28 May 2000
Externally publishedYes

Keywords

  • Bicliques
  • Bipartite Ramsey numbers
  • Graphs
  • Zarankiewicz

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

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

Cite this