← All problems

Zarankiewicz conjecture and Hill’s conjecture

For all positive integers m,nm,n, the crossing number of the complete bipartite graph Km,nK_{m,n} is

cr⁡(Km,n)=⌊m2⌋⌊m−12⌋⌊n2⌋⌊n−12⌋.\operatorname{cr}(K_{m,n})=\left\lfloor\frac{m}{2}\right\rfloor\left\lfloor\frac{m-1}{2}\right\rfloor\left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor.
References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

An unrefereed new paper brings two long-standing graph-drawing predictions closer to the truth, but proves neither.

The Zarankiewicz and Hill conjectures predict exact formulas for crossing numbers of complete bipartite and complete graphs. Both remain unresolved in general.

Known results

  • Hill’s conjecture was verified only through n≤12n\le 12; Balogh, Lidický, and Salazar (2018) proved an asymptotic ratio exceeding 0.985598950.98559895.
  • Zarankiewicz’s conjecture is known for m≤4m\le 4, for K5,nK_{5,n}, and several additional small cases; a 2019 survey records these results.
  • Earlier flag-algebra work gave asymptotic lower bounds exceeding 0.9050.905 for complete graphs and 0.91180.9118 for balanced complete bipartite graphs.

October 18, 2026 flag-algebra update

A new preprint reports lower bounds of 0.96936Z(n,n)0.96936Z(n,n) for Kn,nK_{n,n} and 0.9899H(n)0.9899H(n) for KnK_n, narrowing both asymptotic gaps. These are claimed advances, not exact proofs; the preprint is unrefereed and the reported constants lack independent corroboration in the scan.

Current status (as of October 2026): Both exact conjectures remain open; the October bounds are claimed progress from an unrefereed preprint.

Sources

Solutions 0

No solutions have been posted yet.