mirage

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

 dc.contributor.author Klerk, Etienne de. dc.contributor.author Pasechnik, Dmitrii V. dc.contributor.author Maharry, J. dc.contributor.author Richter, R. B. dc.contributor.author Salazar, G. dc.date.accessioned 2011-05-11T02:55:36Z dc.date.available 2011-05-11T02:55:36Z dc.date.copyright 2006 dc.date.issued 2011-05-11T02:55:36Z dc.identifier.citation Klerk, E. D., Pasechnik, D. V., Maharry, J., Richter, R. B., & Salazar, G. (2006). Improved bounds for the crossing numbers of Km,n and Kn. SIAM Journal of Discrete Mathematics, 20(1), 189-202. dc.identifier.uri http://hdl.handle.net/10220/6787 dc.description.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. dc.language.iso en dc.relation.ispartofseries SIAM journal of discrete mathematics dc.rights © 2006 SIAM This paper was published in SIAM Journal of Discrete Mathematics and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics. The paper can be found at: [DOI: http://dx.doi.org/10.1137/S0895480104442741]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law. dc.subject DRNTU::Science::Mathematics::Applied mathematics. dc.title Improved bounds for the crossing numbers of Km,n and Kn. dc.type Journal Article dc.contributor.school School of Physical and Mathematical Sciences dc.identifier.doi http://dx.doi.org/10.1137/S0895480104442741 dc.description.version Published version

## Files in this item

Files Size Format View
8. Improved bou ... numbers of Km;n and Kn.pdf 202.1Kb PDF View/Open

# Statistics

## Total views

 All Items Views Improved bounds for the crossing numbers of Km,n and Kn. 542

 All Bitstreams Views 8. Improved bounds for the crossing numbers of Km;n and Kn.pdf 145