Bipartite Ramsey numbers and Zarankiewicz numbers

摘要

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.