Zarankiewicz Numbers and Bipartite Ramsey Numbers

Document Type : Research Paper

Authors

1 Rochester Institute of Technology, School of Mathematical Sciences, Rochester, NY 14623

2 University of Pennsylvania, Department of Mathematics, Philadelphia, PA 19104, USA

3 Trinity College, Department of Mathematics, Hartford, CT 06106, USA

4 Rochester Institute of Technology, Department of Computer Science, Rochester, NY 14623

Abstract

The Zarankiewicz number z(b; s) is the maximum size of a subgraph of Kb,b which does not contain Ks,s as a subgraph. The two-color bipartite Ramsey number b(s, t) is the smallest integer b such that any coloring of the edges of Kb,b with two colors contains a Ks,s in the rst color or a Kt,t in the second color.
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 z(b; s) for 3≤s≤6. Our approach and new knowledge about z(b; s) permit us to improve some of the results on bipartite Ramsey numbers obtained by

Keywords

Files

Share

How to cite

Statistics