Asymptotically settling Zarankiewiczʼs Conjecture in finite time, for each m

Perhaps the most notorious open problem in crossing numbers is Zarankiewiczʼs Conjecture, which states that the crossing number cr ( K m , n ) of the complete bipartite graph cr ( K m , n ) is Z ( m , n ) : = ⌊ m − 1 2 ⌋ ⌊ m 2 ⌋ ⌊ n − 1 2 ⌋ ⌊ n 2 ⌋ . This has been verified only for min { m , n } ⩽ 6 and for a few special cases. We have proved that, for each m, there is an integer N ( m ) with the following property: if cr ( K m , n ) = Z ( m , n ) for all n ⩽ N ( m ) , then cr ( K ) = Z ( m , n ) for all n. This yields, for each fixed m, an algorithm that either decides that Zarankiewiczʼs Conjeture cr ( K m , n ) = Z ( m , n ) is true for all n, or else finds a counterexample. To illustrate our techniques, we consider the Asymptotic Zarankiewiczʼs Conjecture (let m be a fixed positive integer; then lim n → ∞ cr ( K m , n ) / Z ( m , n ) = 1 ). We give a detailed sketch of the proof that the Asymptotic Zarankiewiczʼs Conjecture can be settled in finite time.