Strongly Convex Chains

Abstract: It is a classical question to study the length of the longest monotone increasing subsequence in a random permutation on n elements, which has been studied for over half a century. From the geometric viewpoint, the question asks for the maximal number of points in a random sample of n uniform, independent points in a unit square which form an increasing chain. Based on this geometric intuition, one may study the maximal number of points (called the length) which form a convex chain, along with two fixed vertices of the unit square. In a joint work with Imre Bárány, we determined the asymptotic order of magnitude of the length of the longest convex chain, proved strong concentration estimates and a limit shape result. In a recent work, I studied the analogous question for higher order convexity, and managed to determine the expected length in this case as well (which turns out to be very aesthetic), along with concentration properties. In the talk I will give a survey of these results and present several open questions and further research directions.

mathematical physicsanalysis of PDEsclassical analysis and ODEscombinatoricscomplex variablesfunctional analysisinformation theorymetric geometryoptimization and controlprobability

Audience: researchers in the topic

Probability and Analysis Webinar

Series comments: Subscribe to our seminar for weekly announcements at sites.google.com/view/paw-seminar/subscribe Follow us on twitter twitter.com/PAW_seminar

Subscribe to our youtube channel to watch recorded talks www.youtube.com/channel/UCO7mXgeoAFYG2Q17XDRQobA