Zarankiewicz Numbers and Bipartite Ramsey Numbers

Abstract

The Zarankiewicz number <em>z</em>(<em>b;</em> <em>s</em>) is the maximum size of a subgraph of <em>K</em>_{<em>b</em>,<em>b</em>} which does not contain <em>K</em>_{<em>s</em>,<em>s</em>} as a subgraph. The two-color bipartite Ramsey number <em>b</em>(<em>s</em>, <em>t</em>) is the smallest integer <em>b</em> such that any coloring of the edges of <em>K</em>_{<em>b</em>,<em>b</em>} with two colors contains a <em>K</em>_{<em>s</em>,<em>s</em>} in the rst color or a <em>K</em>_{<em>t</em>,<em>t</em>} in the second color.<br />In this work, we design and exploit a computational method for bounding and computing Zarankiewicz numbers. Using it, we obtain several new values and bounds on <em>z</em>(<em>b;</em> <em>s</em>) for 3≤s≤6. Our approach and new knowledge about <em>z</em>(<em>b;</em> <em>s</em>) permit us to improve some of the results on bipartite Ramsey numbers obtained by