Superlinear monotone-path covering conjecture for dense point sets
Statement
Let be a dense -element point set in general position in the plane, and let denote the complete geometric graph induced by . 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 -element point set in general position in the plane, covering the edge set of requires a superlinear number of monotone paths; possibly, this holds for every such point set. The preceding theorem gives an 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.