Improved bounds for the crossing numbers of Km,n and Kn.

Abstract

It has been long conjectured that the crossing number cr(Km,n) of the complete bipartite graph Km,n equals the Zarankiewicz number Z(m, n) :=[(m-1)/2][m/2][(n-1)/2][n/2]. Another longstanding conjecture states that the crossing number cr(Kn) of the complete graph Kn equals Z(n):=(1/4)[n/2][(n-1)/2][(n-2)/2][(n-3)/2]. In this paper we show the following improved bounds on the asymptotic ratios of these crossing numbers and their conjectured values: (i) for each fixed m ≥ 9, limn→∞ cr(Km,n)/Z(m, n) ≥ 0.83m/(m − 1); (ii) limn→∞ cr(Kn,n)/Z(n, n) ≥ 0.83; and iii) limn→∞ cr(Kn)/Z(n) ≥ 0.83. The previous best known lower bounds were 0.8m/(m−1), 0.8, and 0.8, respectively. These improved bounds are obtained as a consequence of the new bound cr(K7,n) ≥ 2.1796n2 −4.5n2. To obtain this improved lower bound for cr(K7,n), we use some elementary topological facts on drawings of K2,7 to set up a quadratic program on 6! variables whose minimum p satisfies cr(K7,n) ≥ (p/2)n2−4.5n, and then use state-of-the-art quadratic optimization techniques combined with a bit of invariant theory of permutation groups to show that p ≥ 4.3593.