The optimal drawings of \(K_{5,n}\)

César Hernández-Vélez ; Carolina Medina ; Gelasio Salazar

The electronic journal of combinatorics, Tome 21 (2014) no. 4

Résumé

Zarankiewicz's Conjecture (ZC) states that the crossing number cr$(K_{m,n})$ equals $Z(m,n):=\lfloor{\frac{m}{2}}\rfloor \lfloor{\frac{m-1}{2}}\rfloor \lfloor{\frac{n}{2}}\rfloor \lfloor{\frac{n-1}{2}}\rfloor$. Since Kleitman's verification of ZC for $K_{5,n}$ (from which ZC for $K_{6,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 $K_{5,n}$. The widely known natural drawings of $K_{m,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 $K_{m,2}$ has no crossings. Antipodal vertices also play a major role in Kleitman's inductive proof that cr$(K_{5,n}) = Z(5,n)$. We explore in depth the role of antipodal vertices in optimal drawings of $K_{5,n}$, for $n$ even. We prove that if {$n \equiv 2$ (mod $4$)}, then every optimal drawing of $K_{5,n}$ has antipodal vertices. We also exhibit a two-parameter family of optimal drawings $D_{r,s}$ of $K_{5,4(r+s)}$ (for $r,s\ge 0$), with no antipodal vertices, and show that if $n\equiv 0$ (mod $4$), then every optimal drawing of $K_{5,n}$ without antipodal vertices is (vertex rotation) isomorphic to $D_{r,s}$ for some integers $r,s$. As a corollary, we show that if $n$ is even, then every optimal drawing of $K_{5,n}$ is the superimposition of Zarankiewicz drawings with a drawing isomorphic to $D_{r,s}$ for some nonnegative integers $r,s$.

Détail

DOI : 10.37236/2777

Classification : 05C10, 05C62, 68R10
Mots-clés : crossing numbers, Turán's brickyard problem, Zarankiewicz conjecture, optimal drawings, antipodal vertices