turkmath.org

Let $S_n$ denote the set of all permutations of length $n$ on the set $[n]:=\{1,2,\cdots,n\}$. The Ulam's problem, the longest increasing subsequence problem for uniformly random permutations, has a long and interesting history.

In the first part of the talk, I will briefly review the solution of this problem in its classical setting, and then present some new results for some pattern-avoiding permutation classes.

For permutations $\tau=\tau_1\tau_2\cdots\tau_k\in S_k$ and $\sigma = \sigma_1 \sigma_2 \cdots \sigma_n \in S_n$, we say that $\tau$ appears as a pattern in $\sigma$ if there exists a subset of indices $1 \leq i_1 < i_2 < \cdots < i_k \leq n$ such that $\sigma_{i_s} < \sigma_{i_t}$ if and only if $\tau_s< \tau_t$ for all $1 \leq s,t \leq k$.

For example, the permutation $213$ appears as a pattern in $24315$ because it has the subsequences $2--15$, $-43-5$ or $--315$. If $\tau$ does not appear as a pattern in $\sigma$, then $\sigma$ is called a $\tau$ avoiding permutation. We denote by $S_n(\tau)$ the set of all $\tau$-avoiding permutations of length $n$. Pattern-avoiding permutations have interesting applications in computer science and biology, and have been studied extensively in combinatorics and recently in the field of probability.

The talk will be accessible to non-specialists.

The talk is based on a joint work with N. Madras (York University); and on a different joint work with T. Mansour (University of Haifa).