Mathematics – Combinatorics
Scientific paper
2011-10-21
Mathematics
Combinatorics
20 pages (ignore pages 21 and 22 produced by the arxive.org script, with copies of pictures inserted elsewhere in the text)
Scientific paper
It has been long conjectured that the crossing numbers of the complete bipartite graph K_{m,n} and of the complete graph K_n equal Z(m,n) (the value conjectured by Zarankiewicz, who came up with a drawing reaching this value) and Z(n) :=Z(n,n-2)/4, respectively. In a 2-page drawing of a graph, the vertices are drawn on a straight line (the spine), and each edge is contained in one of the half-planes of the spine. The 2-page crossing number v_2(G) of a graph G is the minimum number of crossings in a 2-page drawing of G. Somewhat surprisingly, there are 2-page drawings of K_{m,n} (respectively, K_n) with exactly Z(m, n) (respectively, Z(n)) crossings, thus yielding the conjectures (I) v_2(Km,n) =Z(m,n), and (II) v_2(Kn) = Z(n). It is known that (I) holds for min{m, n} <=6, and that (II) holds for n<=14. In this paper we prove that (I) holds asymptotically (that is, lim_n v_2 (K_{m,n})/Z (m, n) = 1) for m=7 and 8. We also prove (II) for 15<=n<=18 and n=20,24, and establish the asymptotic estimate lim_n v_2(K_n)/Z(n) >= 0.9253. The previous best-known lower bound involved the constant 0.8594.
Klerk Etienne de
Pasechnik Dmitrii V.
No associations
LandOfFree
Improved lower bounds for the 2-page crossing numbers of K_{m,n} and K_n via semidefinite programming 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 lower bounds for the 2-page crossing numbers of K_{m,n} and K_n via semidefinite programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved lower bounds for the 2-page crossing numbers of K_{m,n} and K_n via semidefinite programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-85568