×

Bipartite Ramsey numbers and Zarankiewicz numbers. (English) Zbl 0953.05051

Authors’ 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 read \(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\leq 6\).

MSC:

05C55 Generalized Ramsey theory
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI