Crossing-free path cover lower bound cn

AX_geometric_graph_plane_path_cover_bound

Source: arXiv:2507.10840 — Covering Complete Geometric Graphs by Monotone Paths

Problem 5.1 · arXiv:2507.10840

arXiv Problem high confidence— first stated 2026-01-10

Authors: Adrian Dumitrescu, János Pach, Morteza Saghafian, Alex Scott

Status ai-proved high confidence

An odd regular polygon with a central cluster yields point sets requiring at least 3n/4 - O(sqrt(n)) crossing-free paths.

Auto-reviewed 2026-09-17 with gpt-6-astra.

AI-generated write-up ai-proved

Open the PDF write-up

This is a model-generated research artifact, not a peer-reviewed publication or a formally verified proof.

Problem. Does there exist a constant $c>1/2$ with the property that, for infinitely many values of $n$, there are $n$-element point sets $A$ in the plane such that every covering of the edge set of $K_{n}[A]$ by crossing-free paths requires at least $cn$ paths?

Context

Pach, Saghafian, and Schnider proved that every complete convex geometric graph can be decomposed into $n/2 + o(n)$ plane subgraphs. It is open whether a linear lower bound strictly above $n/2$ holds for crossing-free path coverings over general point sets.

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