Document Type : Research Paper

Authors

• Alex F. Collins ¹
• Alexander W. N. Riasanovsky ²
• John C. Wallace ³
• Stanis law P. Radziszowski ⁴

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

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

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

⁴ 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 K_b,b which does not contain K_s,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 K_b,b with two colors contains a K_s,s in the rst color or a K_t,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

• Zarankiewicz number
• bipartite Ramsey number