Zarankiewicz numbers near the triple system threshold

Abstract

For positive integers $m$ and $n$, the Zarankiewicz number $Z_{2,2}(m,n)$ can be defined as the maximum total degree of a linear hypergraph with $m$ vertices and $n$ edges. Guy determined $Z_{2,2}(m,n)$ for all $n\ge \left(\genfrac{}{}{0ex}{}{m}{2}\right)/3+O(m)$. Here, we extend this by determining $Z_{2,2}(m,n)$ for all $n\ge \left(\genfrac{}{}{0ex}{}{m}{2}\right)/3$ and, when $m$ is large, for all $n\ge \left(\genfrac{}{}{0ex}{}{m}{2}\right)/6+O(m)$.

18 pages, 4 figures