The Zarankiewicz number $Z_{2,2}(m, n)$ is usually defined as the maximum number of edges in a bipartite graph with parts of sizes $m$ and $n$ that has no 4-cycle. An equivalent definition is that $Z_{2,2}(m, n)$ is the greatest number of block-point incidences in a partial pairwise balanced design with $m$ points and $n$ blocks. Here, a partial pairwise balanced design on a set $V$ of points is a collection of subsets of $V$ (called blocks) such that each pair of points occur together in at most one block. The equivalence of the two definitions can be seen by considering the bipartite incidence graph of the partial pairwise balanced design. It can be shown that $Z_{2,2}\left(m,\left(\overset{\displaystyle m}{2}\right)/\left(\overset{\displaystyle k}{2}\right)\right) = \frac{m(m-1)}{k-1}$ if and only if an $(m, k, 1)$-design exists. A simple argument determines the exact value of $Z_{2,2}(m, n)$ whenever $n \ge \left( \overset{\displaystyle M}{2} \right)$. Using partial Steiner triple systems, Guy was able to extend this determination to all $n \ge \left( \overset{\displaystyle M}{2} \right)/3 + \frac{m+1}{3}$. This talk discusses how we can find, for large $m$, the exact value of $Z_{2,2}(m, n)$ in almost all of the remaining cases where $n = \Theta(m^{2})$.

We accomplish this by viewing the problem through the lens of pairwise balanced designs. We establish a new family of upper bounds on $Z_{2,2}(m, n)$ which complements a family already obtained by Roman, and then prove that the floor of the best of these bounds is almost always achieved. We also show that there are cases in which this floor cannot be achieved and others in which determining whether it is achieved is equivalent to determining the existence of a finite projective plane of non prime power order. Our results can be generalised to the Zarankiewicz numbers $Z_{2,\lambda+1}(m, n)$ by considering pairwise balanced designs of index $\lambda$.

Bio: Daniel received his Ph.D. in 2008 from the University of Queensland. He then held postdoctoral positions at Memorial University of Newfoundland and Arizona State University, before being hired as a lecturer at Monash University. He is currently an Associate Professor and ARC Future Fellow at Monash. His research interests include block designs, edge decomposition problems in graphs, covering and packing problems, and covering arrays and their variants.