Conference
Crossing numbers of complete bipartite graphs
| العنوان: | Crossing numbers of complete bipartite graphs |
|---|---|
| المؤلفون: | Balogh, József, Lidicky, Bernard, Norin, Sergey, Pfender, Florian, Salazar, Gelasio, Spiro, Sam |
| المساهمون: | Mathematics |
| المصدر: | https://doi.org/10.1016/j.procs.2023.08.216. |
| بيانات النشر: | Elsevier B.V. |
| سنة النشر: | 2023 |
| المجموعة: | Digital Repository @ Iowa State University |
| مصطلحات موضوعية: | DegreeDisciplines::Physical Sciences and Mathematics::Mathematics, Zarankiewicz, crossing number, complete bipartite graph, flag algebras |
| الوصف: | 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. ; 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). |
| نوع الوثيقة: | conference object |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | https://dr.lib.iastate.edu/handle/20.500.12876/jrl8QWMr |
| الاتاحة: | https://dr.lib.iastate.edu/handle/20.500.12876/jrl8QWMr https://hdl.handle.net/20.500.12876/jrl8QWMr |
| رقم الانضمام: | edsbas.E7E25531 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |