ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.