Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423877 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
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.