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

DSpace/Manakin Repository


Search DR-NTU

Advanced Search Subject Search


My Account

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

Show simple item record

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

This item appears in the following Collection(s)

Show simple item record


Total views

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

Total downloads

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

Top country downloads

Country Code Views
United States of America 85
China 41
Singapore 18
Saudi Arabia 7
France 5

Top city downloads

city Views
Mountain View 64
Singapore 18
Beijing 6
Seattle 3
Shenzhen 2