Zarankiewicz Problem

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $m,n,s,t\in\mathbb N$. A bipartite graph $G=(L\sqcup R,E)$ has fixed partite sets with $|L|=m$, $|R|=n$, and edges only between $L$ and $R$. In the standard partite-respecting Zarankiewicz convention, a forbidden $K_{s,t}$ consists of $S\subseteq L$, $T\subseteq R$, $|S|=s$, $|T|=t$, such that every pair in $S\times T$ is an edge. Equivalently, the $m\times n$ bipartite adjacency matrix is a zero--one matrix with no all-one $s\times t$ submatrix obtained by choosing rows and columns; the rows and columns need not be consecutive. Define \[ z(m,n;s,t)=\max\{|E(G)|:G\text{ has these partite sizes and no such }K_{s,t}\}. \] This fixes the roles of the two partite sets, as in the source's matrix definition; it gives $z(m,n;s,t)=z(n,m;t,s)$.

Statement recorded in the supplied source.

Determine $z(m,n;s,t)$ for all positive integers $m,n,s,t$, including the unresolved exact finite values and sharp extremal behavior. The request is for the full four-parameter extremal function, rather than only the equal-part case or one fixed forbidden graph. [S2]

Short English statement

Determine the greatest number of edges between two prescribed vertex classes when no chosen s vertices in the first class and t in the second are all joined to each other.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1427 (GRAPH-040). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Vladimir Nikiforov, A Contribution to the Zarankiewicz Problem, arXiv:0903.5350v1 (2009), abstract and section “The matrix Zarankiewicz problem”, pages 1--2. https://arxiv.org/pdf/0903.5350v1.