Harary–Hill conjecture for the crossing number of complete graphs
Let be the complete graph on vertices, and define
Here denotes the minimum number of crossings in a plane drawing of a graph . Harary–Hill conjecture.
The formula is achieved by Hill's drawing of and is conjectured to be optimal; determining the crossing number of complete graphs remains a central open problem in topological graph theory.
References
Primary source
Ruy Fabila-Monroy, Rosna Paul, Jenifer Viafara-Chanchi and Alexandra Weinberger, “On the rectilinear crossing number of complete balanced multipartite graphs and layered graphs”, arXiv:2404.13155 (2025).
Additional references
5 papers in this index state this conjecture (2013–2024). The statement above is taken from the most recent of them; the others are arXiv:1907.07796, arXiv:1805.06780, arXiv:1803.07515, arXiv:1307.3297.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 1
RemarkAI-assistedClaimed by OpenAI.See full solution
Claimed by OpenAI.
Claims the ordinary crossing number of K_n equals one quarter of floor(n/2) floor((n-1)/2) floor((n-2)/2) floor((n-3)/2) for every positive integer n, with unrestricted vertex positions and edge routes.
Repository: https://github.com/openai/math
- OpenAI-165-01-The-crossing-number-of-complete-graphs.pdfOpen