Longest convex chains

PIMS-MPrime Summer School in Probability

授课人:Gergely Ambrus

机构:Pacific Institute for the Mathematical Sciences(PIMS)

关键词: Scientific;    Mathematics;    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.

【 授权许可】

CC BY-NC-ND   
Except where explicitly noted elsewhere, the works on this site are licensed under a Creative Commons License: CC BY-NC-ND