Non-crossing Monotonic Paths in Labeled Point Sets on the Plane

Let n be a positive integer, and let P be a set of n points in general position on the plane with labels 1,2, . . . , n. The label of each p ∈ P will be denoted by l(p). A polygonal line connecting k elements p1, p2, . . . , pk of P in this order is called a monotonic path of length k if the sequence l(p1), l(p2), . . . , l(pk) is monotonically increasing or decreasing in this order. We show that P contains a vertex set of a noncrossing monotonic path of length at least c( √ n −1),