Math Conjectures

Zarankiewicz Problem for K4,4K_{4,4}

OPENMajorOpen problemProposed 1951 · Canonical special case

Canonical statement

Determine the asymptotic order of
ex⁡(n,K4,4), \operatorname{ex}(n,K_{4,4}),
the largest number of edges in an nn-vertex graph containing no copy of the complete bipartite graph K4,4K_{4,4}.
View source LaTeX
Determine the asymptotic order of
\[
  \operatorname{ex}(n,K_{4,4}),
\]
the largest number of edges in an \(n\)-vertex graph containing no copy of the complete bipartite graph \(K_{4,4}\).
GRAPH-030:[KovariSosTuran1954][Furedi1996Zarankiewicz][FurediSimonovits2013Degenerate]
Graph theoryCombinatorics

Notes

The Zarankiewicz problem asks for extremal numbers of complete bipartite graphs. The Kővári–Sós–Turán upper bound gives ex⁡(n,K4,4)=O(n7/4)\operatorname{ex}(n,K_{4,4})=O(n^{7/4}) [KovariSosTuran1954], while algebraic constructions give order at least n5/3n^{5/3}. No exponent between these bounds is known to be exact [Furedi1996Zarankiewicz] [FurediSimonovits2013Degenerate], making K4,4K_{4,4} a canonical unresolved finite parameter case.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.