Drawings of complete graphs in the projective plane
Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. 2021. Drawings of complete graphs in the projective plane. Journal of Graph Theory. 97(3), 426β440.
Download (ext.)
https://arxiv.org/abs/2002.02287
[Preprint]
Journal Article
| Published
| English
Scopus indexed
Author
Arroyo Guevara, Alan MISTA ;
Mcquillan, Dan;
Richter, R. Bruce;
Salazar, Gelasio;
Sullivan, Matthew
Department
Abstract
Hill's Conjecture states that the crossing number cr(πΎπ) of the complete graph πΎπ in the plane (equivalently, the sphere) is 14βπ2ββπβ12ββπβ22ββπβ32β=π4/64+π(π3) . Moon proved that the expected number of crossings in a spherical drawing in which the points are randomly distributed and joined by geodesics is precisely π4/64+π(π3) , thus matching asymptotically the conjectured value of cr(πΎπ) . Let crπ(πΊ) denote the crossing number of a graph πΊ in the projective plane. Recently, Elkies proved that the expected number of crossings in a naturally defined random projective plane drawing of πΎπ is (π4/8π2)+π(π3) . In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if limπβββcrπ(πΎπ)/π4=1/8π2 . We construct drawings of πΎπ in the projective plane that disprove this.
Publishing Year
Date Published
2021-03-23
Journal Title
Journal of Graph Theory
Publisher
Wiley
Acknowledgement
We thank two reviewers for their corrections and suggestions on the original version of this
paper. This project has received funding from NSERC Grant 50503-10940-500 and from the European Unionβs Horizon 2020 research and innovation programme under the Marie SkΕodowskaCurie grant agreement No 754411, IST, Klosterneuburg, Austria.
Volume
97
Issue
3
Page
426-440
ISSN
eISSN
IST-REx-ID
Cite this
Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. Drawings of complete graphs in the projective plane. Journal of Graph Theory. 2021;97(3):426-440. doi:10.1002/jgt.22665
Arroyo Guevara, A. M., Mcquillan, D., Richter, R. B., Salazar, G., & Sullivan, M. (2021). Drawings of complete graphs in the projective plane. Journal of Graph Theory. Wiley. https://doi.org/10.1002/jgt.22665
Arroyo Guevara, Alan M, Dan Mcquillan, R. Bruce Richter, Gelasio Salazar, and Matthew Sullivan. βDrawings of Complete Graphs in the Projective Plane.β Journal of Graph Theory. Wiley, 2021. https://doi.org/10.1002/jgt.22665.
A. M. Arroyo Guevara, D. Mcquillan, R. B. Richter, G. Salazar, and M. Sullivan, βDrawings of complete graphs in the projective plane,β Journal of Graph Theory, vol. 97, no. 3. Wiley, pp. 426β440, 2021.
Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. 2021. Drawings of complete graphs in the projective plane. Journal of Graph Theory. 97(3), 426β440.
Arroyo Guevara, Alan M., et al. βDrawings of Complete Graphs in the Projective Plane.β Journal of Graph Theory, vol. 97, no. 3, Wiley, 2021, pp. 426β40, doi:10.1002/jgt.22665.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Web of Science
View record in Web of Science®Sources
arXiv 2002.02287