Longest k-monotone chains

Ambrus, Gergely (2021) Longest k-monotone chains. RANDOM STRUCTURES & ALGORITHMS. ISSN 1042-9832

Preview

Text 2009.pdf Available under License Creative Commons Attribution. Download (409kB) | Preview

Abstract

We study higher order convexity properties of random point sets in the unit square. Given n uniform i.i.d random points, we derive asymptotic estimates for the maximal number of them which are in k-monotone position, subject to mild boundary conditions. Besides determining the order of magnitude of the expectation, we also prove strong concentration estimates. We provide a general framework that includes the previously studied cases of k = 1 (longest increasing sequences) and k = 2 (longest convex chains).

Actions (login required)

Edit Item