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 language | English |
---|---|
Pages (from-to) | 85-95 |
Number of pages | 11 |
Journal | Discrete Mathematics |
Volume | 219 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 28 May 2000 |
Externally published | Yes |
Keywords
- Bicliques
- Bipartite Ramsey numbers
- Graphs
- Zarankiewicz
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics