Crossing numbers of complete bipartite graphs
Date
2023-09-13
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier B.V.
Abstract
The long standing Zarankiewicz's conjecture states that the crossing number cr(Km,n) of the complete bipartite graph is Z(m,n):= [m/2][m-1/2][n/2][n-1/2]. Using flag algebras we show that cr(Kn,n) ≥ 0.9118 • Z(n, n) + o(n4). We also show that the rectilinear crossing number cr-(Kn,n) of Kn,n is at least 0.987 • Z(n,n) + o(n4). Finally, we show that if a drawing of Kn,n has no K3,4 that has exactly two crossings, and these crossings share exactly one vertex, then it has at least Z(n,n) + o(n4) crossings. This is a local restriction inspired by Turán type problems that gives an asymptotically tight result.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
Presentation
Comments
This proceeding is published as Balogh, József, Bernard Lidický, Sergey Norin, Florian Pfender, Gelasio Salazar, and Sam Spiro. "Crossing numbers of complete bipartite graphs." Procedia Computer Science 223 (2023): 78-87. doi:10.1016/j.procs.2023.08.216. © 2023 The Authors. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0).