Article ID Journal Published Year Pages File Type
6423877 Electronic Notes in Discrete Mathematics 2011 6 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,