Seminar

A classical problem in probability, that emerged in the 1970\'s, is to describe the behaviour of the length of the longest increasing subsequence in a random permutation. By now, this task has been fully accomplished: not only the expectation and the variance is known, but also the properly scaled limit distribution has been determined. 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 treated in the talk asks for the length of the longest convex chain. We determine the asymptotic expectation up to a constant factor, and derive strong concentration results. This is a joint work with Imre Barany.