TY - JOUR
T1 - Crossing numbers of complete bipartite graphs
AU - Balogh, József
AU - Lidický, Bernard
AU - Norin, Sergey
AU - Pfender, Florian
AU - Salazar, Gelasio
AU - Spiro, Sam
N1 - 1 Balogh was supported in part by NSF grants DMS-1764123, RTG DMS-1937241 and FRG DMS-2152488, the Arnold O. Beckman Research 1 Balogh was supported in part by NSF grants DMS-1764123, RTG DMS-1937241 and FRG DMS-2152488, the Arnold O. Beckman Research Research of this author is supported in part by NSF grant DMS-2152490 and Scott Hanna fellowship. 2 Supported by an NSERC Discovery Grant. Supporté par le Programme de subventions à la recherche du CRSNG.
43 Supported by an NSERC Discovery Grant. Supporté par le Programme de subventions à la recherche du CRSNG.
This work was developed over the course of two AIM SQuaRE Workshops “Crossing numbers of complete and complete bipartite graphs”. The first one was held online on April 19-23, 2021, and the second one at the facilities of the American Institute of Mathematics on September 19-23, 2022. The authors thank AIM for hosting them. The authors thank Carolina Medina for discussions. This work used the computing resources at the Center for Computational Mathematics, University of Colorado Denver, including the Alderaan cluster, supported by the National Science Foundation award OAC-2019089.
PY - 2023
Y1 - 2023
N2 - 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,nis at least 0.987 •Z(n,n)+ o(n4). Finally, we show that if a drawing of Kn,nhas no K3,4that 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.
AB - 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,nis at least 0.987 •Z(n,n)+ o(n4). Finally, we show that if a drawing of Kn,nhas no K3,4that 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.
KW - Zarankiewicz
KW - complete bipartite graph
KW - crossing number
KW - flag algebras
UR - http://www.scopus.com/inward/record.url?scp=85174407760&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85174407760&partnerID=8YFLogxK
U2 - 10.1016/j.procs.2023.08.216
DO - 10.1016/j.procs.2023.08.216
M3 - Conference article
AN - SCOPUS:85174407760
SN - 1877-0509
VL - 223
SP - 78
EP - 87
JO - Procedia Computer Science
JF - Procedia Computer Science
T2 - 12th Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2023
Y2 - 18 September 2023 through 22 September 2023
ER -