-
Zarankiewicz%27s Conjecture (ZC) states that the crossing number cr(Km,n) equals (Formula Presented). Since Kleitman%27s verification of ZC for K5,n (from which ZC for K6,n easily follows), very little progress has been made around ZC; the most notable exceptions involve computer-aided results. With the aim of gaining a more profound understanding of this notoriously difficult conjecture, we investigate the optimal (that is, crossing-minimal) drawings of K5,n. The widely known natural drawings of Km,n (the so-called Zarankiewicz drawings) with Z(m,n) crossings contain antipodal vertices, that is, pairs of degree-m vertices such that their induced drawing of Km,2 has no crossings. Antipodal vertices also play a major role in Kleitman%27s inductive proof that cr(K5,n)=Z(5,n). We explore in depth the role of antipodal vertices in optimal drawings of K5,n, for n even. We prove that if {n≡2 (mod 4)}, then every optimal drawing of K5,n has antipodal vertices. We also exhibit a two-parameter family of optimal drawings Dr,s of K5,4(r%2bs) (for r, s ≥ 0), with no antipodal vertices, and show that if n≡0 (mod 4), then every optimal drawing of K5,n without antipodal vertices is (vertex rotation) isomorphic to Dr,s for some integers r,s. As a corollary, we show that if n is even, then every optimal drawing of K5,n is the superimposition of Zarankiewicz drawings with a drawing isomorphic to Dr,s for some nonnegative integers r,s. © 2014, Australian National University. All rights reserved.
-
Zarankiewicz's Conjecture (ZC) states that the crossing number cr(Km,n) equals (Formula Presented). Since Kleitman's verification of ZC for K5,n (from which ZC for K6,n easily follows), very little progress has been made around ZC; the most notable exceptions involve computer-aided results. With the aim of gaining a more profound understanding of this notoriously difficult conjecture, we investigate the optimal (that is, crossing-minimal) drawings of K5,n. The widely known natural drawings of Km,n (the so-called Zarankiewicz drawings) with Z(m,n) crossings contain antipodal vertices, that is, pairs of degree-m vertices such that their induced drawing of Km,2 has no crossings. Antipodal vertices also play a major role in Kleitman's inductive proof that cr(K5,n)=Z(5,n). We explore in depth the role of antipodal vertices in optimal drawings of K5,n, for n even. We prove that if {n≡2 (mod 4)}, then every optimal drawing of K5,n has antipodal vertices. We also exhibit a two-parameter family of optimal drawings Dr,s of K5,4(r%2bs) (for r, s ≥ 0), with no antipodal vertices, and show that if n≡0 (mod 4), then every optimal drawing of K5,n without antipodal vertices is (vertex rotation) isomorphic to Dr,s for some integers r,s. As a corollary, we show that if n is even, then every optimal drawing of K5,n is the superimposition of Zarankiewicz drawings with a drawing isomorphic to Dr,s for some nonnegative integers r,s. © 2014, Australian National University. All rights reserved.
... more
