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