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(Km,n) of the complete bipartite graph cr(Km,n) is Z(m,n):=⌊m−12⌋⌊m2⌋⌊n−12⌋⌊n2⌋. 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(Km,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(Km,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 limn→∞cr(Km,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.