turkmath.org

A permutation σ is an arrangement of the numbers in [n]:={1,2,…,n}. The set of all permutations on [n] is denoted by S_n. A pattern of length k is simply a permutation τ in S_k. This pattern is said to be contained in a permutation σ in S_n if there is a subsequence of σ of k elements that appears in the same relative order as the pattern τ. For example, the pattern 231 is contained in the permutation 246315 because the latter contains the subsequence 463 or 261. We say that σ avoids the pattern τ if σ does not contain τ. I will describe what we can prove about probabilistic properties of pattern-avoiding permutation classes. Specifically, I will present some results on the famous ``longest increasing subsequence problem" in this context. Collaborator: Neal Madras (Department of Mathematics and Statistics, York University, Canada)