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

Summary: 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 \textit{optimal} (that is, crossing-minimal) drawings of \(K_{5,n}\). The widely known natural drawings of \(K_{m,n}\) (the so-called \textit{Zarankiewicz drawings}) with \(Z(m,n)\) crossings contain \textit{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\geq 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\).