Crossing number of Kₙ minus t-matching
AX_crossing_number_kn_minus_matching
Source: arXiv:2009.03418 — On a conjecture by Anthony Hill
Conjecture 5 · arXiv:2009.03418
Status open medium confidence
Conjecture 5 from arXiv:2009.03418 posits that the crossing number of $M_{n,t}$ (the complete graph $K_n$ minus a matching of size $t$) equals $H(n) - \frac{1}{2}t(k-1)(k-2)$ where $k=\lfloor n/2\rfloor$. Mohar proves a matching upper bound via geodesic drawings built from strength-0 point sets, making the conjecture that this count is optimal. No paper resolving or making substantial progress on this specific conjecture was found in web searches; the underlying Hill conjecture for $K_n$ itself remains open, making resolution of this generalization unlikely to have been achieved unnoticed.
Reviewer notes. No follow-up paper specifically addressing Conjecture 5 of arXiv:2009.03418 was found. The conjecture is a natural extension of the long-standing open Hill conjecture (cr(K_n) = H(n)), which itself remains unresolved; the upper bound matching the conjectured value is established by Mohar via geodesic drawings of K_n minus a matching using strength-0 configurations. The paper appeared in a Springer proceedings volume (Graph Drawing 2020). Confidence is medium rather than high because the conjecture is ~6 years old and absence of web evidence for a conjecture with this level of notoriety is slightly suspicious, though consistent with the broader open status of Hill-type problems.
OpenAI manuscript collection partial progress
OpenAI's manuscript proves the $t = 0$ case, Hill's formula $\mathrm{cr}(K_n) = H(n)$; complete graphs minus a matching are not treated.
- The crossing number of complete graphs — main result formalized in Lean by OpenAI
Family 165: The Harary–Hill and Zarankiewicz crossing-number formulas · Lean formalization scope
These manuscripts were produced by an unreleased OpenAI model and released on 2026-10-06 in github.com/openai/math. They have not been peer reviewed. Lean formalizations are OpenAI's own and cover only the scope stated on their scope page; this project has not run or reviewed them. This is partial progress, so the status above is unchanged.
Context
Here $M_{n,t}$ denotes the graph obtained from $K_n$ by removing a matching of size $t$, and $k = \lfloor n/2 \rfloor$. Corollary 4 shows that geodesic drawings of $M_{n,t}$ built from sets of strength $0$ achieve this crossing count; the existence of many such sets of strength $0$ motivates the conjecture that this value is optimal.
Notes. PDF source; the algebraic expression is unambiguous.
Source paper
On a conjecture by Anthony Hill
Bojan Mohar · 2020-09-07
https://arxiv.org/abs/2009.03418
PDF source