On Some Zarankiewicz Numbers and Bipartite Ramsey Numbers for Quadrilateral

Janusz Dybizbariski1, Tomasz Dzido1
1Institute of Informatics, University of Gdarisk Wita Stwosza 57, 80-952 Gdarisk, Poland

Abstract

The Zarankiewicz number \(z(m, n; s, t)\) is the maximum number of edges in a subgraph of \(K_{m,n}\) that does not contain \(K_{s,t}\) as a subgraph. The \emph{bipartite Ramsey number} \(b(n_1, \ldots, n_k)\) is the least positive integer \(b\) such that any coloring of the edges of \(K_{b,b}\) with \(k\) colors will result in a monochromatic copy of \(K_{n_i,n_i}\) in the \(i\)-th color, for some \(i\), \(1 \leq i \leq k\). If \(n_i = m\) for all \(i\), we denote this number by \(b_k(m)\). In this paper, we obtain the exact values of some Zarankiewicz numbers for quadrilaterals (\(s = t = 2\)), and derive new bounds for diagonal multicolor bipartite Ramsey numbers avoiding quadrilaterals. Specifically, we prove that \(b_4(2) = 19\) and establish new general lower and upper bounds on \(b_k(2)\).