Asymptotically settling Zarankiewicz's Conjecture in finite time, for each m Article uri icon

abstract

  • Perhaps the most notorious open problem in crossing numbers is Zarankiewicz%27s Conjecture, which states that the crossing number cr(Km,n) of the complete bipartite graph cr(Km,n) is Z(m,n):={box drawings light up and right}m-1/2{box drawings light up and left}{box drawings light up and right}m/2{box drawings light up and left}{box drawings light up and right}n-1/2{box drawings light up and left}{box drawings light up and right}n/2{box drawings light up and left}. 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%27s 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%27s 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%27s Conjecture can be settled in finite time. © 2011 Elsevier B.V.
  • 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):={box drawings light up and right}m-1/2{box drawings light up and left}{box drawings light up and right}m/2{box drawings light up and left}{box drawings light up and right}n-1/2{box drawings light up and left}{box drawings light up and right}n/2{box drawings light up and left}. 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. © 2011 Elsevier B.V.

publication date

  • 2011-01-01