Algebraic Graph Theory - Daniel Horsley

Title: Exact Zarankiewicz numbers through linear hypergraphs

Abstract: The \emph{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 $K_{2,2}$ subgraph. An equivalent definition is that $Z_{2,2}(m,n)$ is the greatest total degree of a linear hypergraph with $m$ vertices and $n$ edges. A hypergraph is \emph{linear} if each pair of vertices appear together in at most one edge. The equivalence of the two definitions can be seen by considering the bipartite incidence graph of the linear hypergraph.

A simple argument determines the exact value of $Z_{2,2}(m,n)$ whenever $n \geq \binom{m}{2}$. Guy was able to extend this determination to all $n \geq \binom{m}{2}/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)$. Our results can be generalised to the Zarankiewicz numbers $Z_{2,\lambda+1}(m,n)$ by considering hypergraphs in which each pair of vertices appear together in at most $\lambda$ edges.