TY - JOUR
ID - 7943
TI - Zarankiewicz Numbers and Bipartite Ramsey Numbers
JO - Journal of Algorithms and Computation
JA - JAC
LA - en
SN - 2476-2776
AU - Collins, Alex F.
AU - Riasanovsky, Alexander W. N.
AU - Wallace, John C.
AU - Radziszowski, Stanis law P.
AD - Rochester Institute of Technology, School of Mathematical Sciences, Rochester, NY 14623
AD - University of Pennsylvania, Department of Mathematics, Philadelphia, PA 19104, USA
AD - Trinity College, Department of Mathematics, Hartford, CT 06106, USA
AD - Rochester Institute of Technology, Department of Computer Science, Rochester, NY 14623
Y1 - 2016
PY - 2016
VL - 47
IS - 1
SP - 63
EP - 78
KW - Zarankiewicz number
KW - bipartite Ramsey number
DO -
N2 - 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
UR - https://jac.ut.ac.ir/article_7943.html
L1 - https://jac.ut.ac.ir/article_7943_0d5d2a7f40f78dfe0e529df98f3049dd.pdf
ER -