Zarankiewicz Numbers and Bipartite Ramsey Numbers
نویسندگان
1 University of Pennsylvania, Department of Mathematics, Philadelphia, PA 19104, USA
2 Trinity College, Department of Mathematics, Hartford, CT 06106, USA
3 Rochester Institute of Technology, Department of Computer Science, Rochester, NY 14623
4 Rochester Institute of Technology, School of Mathematical Sciences, Rochester, NY 14623
doi
10.22059/jac.2016.7943چکیده
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
