Mathematics – Combinatorics
Scientific paper
2004-04-06
SIAM J. Discr. Math. 20(2006), 189--202
Mathematics
Combinatorics
LaTeX, 18 pages, 2 figures
Scientific paper
10.1137/S0895480104442741
It has been long--conjectured that the crossing number cr(K_m,n) of the complete bipartite graph K_m,n equals the Zarankiewicz Number Z(m,n):= floor((m-1)/2) floor(m/2) floor((n-1)/2) floor(n/2). Another long--standing conjecture states that the crossing number cr(K_n) of the complete graph K_n equals Z(n):= floor(n/2) floor((n-1)/2) floor((n-2)/2) floor((n-3)/2)/4. 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, lim_{n->infty} cr(K_m,n)/Z(m,n) >= 0.83m/(m-1); (ii) lim_{n->infty} cr(K_n,n)/Z(n,n) >= 0.83; and (iii) lim_{n->infty} cr(K_n)/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(K_{7,n}) >= 2.1796n^2 - 4.5n. To obtain this improved lower bound for cr(K_{7,n}), we use some elementary topological facts on drawings of K_{2,7} to set up a quadratic program on 6! variables whose minimum p satisfies cr(K_{7,n}) >= (p/2)n^2 - 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.
Klerk Etienne de
Maharry J.
Pasechnik Dmitrii V.
Richter Bruce R.
Salazar Gelasio
No associations
LandOfFree
Improved bounds for the crossing numbers of K_m,n and K_n does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improved bounds for the crossing numbers of K_m,n and K_n, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved bounds for the crossing numbers of K_m,n and K_n will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-243962