On Some Zarankiewicz Numbers and Bipartite Ramsey Numbers for Quadrilateral

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,\dots ,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\le i\le 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)$.