turkmath.org

In this survey talk, I will review some interesting results related to the longest increasing subsequence problem such as Erdös-Szekeres Lemma, patience-sorting algorithm, Young tableaux and Schensted correspondence. We will also see how the problem can be reformulated as an interacting particle process. Another reformulation of the problem in permutation-patterns context will be discussed along with some open problems. The talk will be based on the following survey paper: Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc. (N.S.) 36 (1999), no. 4 by Aldous and Diaconis.