Longest convex chains

Gergely Ambrus
Mon, Jun 11, 2012
PIMS, University of British Columbia
PIMS-MPrime Summer School in Probability

A classical problem in probability is to determine the length of the longest increasing subsequence in a random permutation. Geometrically, the question can be formulated as follows: given n independent, uniform random points in the unit square, find the longest increasing chain (polygonal path through the given points) connecting two diagonally opposite corner of the square, where "length" means the number of points on the chain. The variant of the problem I am going to talk about asks for the length of the longest convex chain connecting two vertices. We determine the asymptotic expectation up to a constant factor, and derive strong concentration and limit shape results. We also prove an ergodic result as well as giving a heuristic argument for the exact asymptotics of the expectation. Some of these results are joint with Imre Barany.