Superlinear monotone path cover for dense point sets
Conjecture 1.4 · arXiv:2507.10840
Status open high confidence
Conjecture 1.4 from arXiv:2507.10840 asks whether covering the edge set of K_n[A] for some (possibly every) alpha-dense n-element point set A in general position requires a superlinear number of monotone paths. The source paper establishes an O(n^{3/2}) upper bound (Theorem 1.3) for alpha-dense point sets and an O(n log n) upper bound for random uniform point sets, while constructing worst-case point sets requiring Theta(n^2) paths; the gap between these bounds motivates the conjecture. No follow-up work resolving or making progress on the conjecture was found in four months of indexed literature since the paper's publication.
Reviewer notes. No follow-up found. The paper is very recent (January 2026) and the conjecture is a suspicion stated by the authors without supporting evidence beyond the upper/lower bound gap. No internal references were supplied. The paper was originally submitted July 2025 and revised January 2026.
Context
Theorem 1.3 shows that $O(n^{3/2})$ monotone paths suffice to cover $K_n[A]$ for any $\alpha$-dense point set $A$. The authors suspect this upper bound is not tight and that a superlinear lower bound holds. This is contrasted with the worst-case arbitrary point sets, for which a quadratic number of monotone paths is required.
Source paper
Covering Complete Geometric Graphs by Monotone Paths
Adrian Dumitrescu, János Pach, Morteza Saghafian, Alex Scott · 2026-01-10
https://arxiv.org/abs/2507.10840