Superlinear monotone-path covering conjecture for dense point sets

From papers

Let AA be a dense nn-element point set in general position in the plane, and let Kn[A]K_n[A] denote the complete geometric graph induced by AA. A path is monotone if its edge set is contained in a matching that is monotone in some direction, equivalently, if its edges have pairwise disjoint projections onto some direction. Superlinear monotone-path covering conjecture. For some dense nn-element point set AA in general position in the plane, covering the edge set of Kn[A]K_n[A] requires a superlinear number of monotone paths; possibly, this holds for every such point set. The preceding theorem gives an O(n3/2)O(n^{3/2}) upper bound for dense point sets, while the conjecture asks whether a superlinear lower bound is necessary. The quantifier over dense point sets is stated tentatively in the source, so whether the claim holds for some or every dense point set remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Adrian Dumitrescu, János Pach, Morteza Saghafian and Alex Scott, “Covering Complete Geometric Graphs by Monotone Paths”, arXiv:2507.10840 (2026).

Solutions 0

No solutions have been posted yet.