The optimal drawings of \(K_{5,n}\)
type: Item
instance of: scholarly article
title: The optimal drawings of \(K_{5,n}\)
zbMATH Open document ID: 1298.05086
author: César Hernández-Vélez
author: Carolina Medina
author: Gelasio Salazar
published in: The Electronic Journal of Combinatorics
publication date: 2014-10-23T00:00:00Z
full work available at URL: https://arxiv.org/abs/1210.1988
full work available at URL: v21i4p1
review text: 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\).
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6360676
zbMATH Keywords: crossing numbers
zbMATH Keywords: Turán's brickyard problem
zbMATH Keywords: Zarankiewicz conjecture
zbMATH Keywords: optimal drawings
zbMATH Keywords: antipodal vertices
MaRDI profile type: Publication
arXiv ID: 1210.1988
cites work: Zarankiewicz's conjecture is finite for each fixed \(m\)
cites work: Improved lower bounds for the 2-page crossing numbers of \(K_{m,n}\) and \(K_n\) via semidefinite programming
cites work: Improved Bounds for the Crossing Numbers of Km,n and Kn
cites work: Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
cites work: Q5587734
cites work: The crossing number of K5,n
cites work: Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
cites work: On a problem of P. Turan concerning graphs
Recommended article: Q4826137
Recommended article: Packing of \(K_{v}\) with certain graphs of five vertices
Recommended article: Drawing \(K_{2,n}\): A lower bound
Recommended article: Geometric drawings of \(K_{n}\) with few crossings
Recommended article: Q4694750
Recommended article: A (5,5)-Colouring of Kn with Few Colours
Recommended article: Maximizing five-cycles in \(K_r\)-free graphs
Recommended article: Five-coloring graphs on the Klein bottle
Recommended article: Q5488362
Recommended article: K5-Subdivisions in Graphs
description: scientific article; zbMATH DE number 6360676