Middle East Technical University General Seminars

Longest increasing subsequences in pattern-avoiding permutations
Gökhan Yıldırım
Bilkent University, Turkey
Özet : 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).
  Tarih : 08.11.2018
  Saat : 15:40
  Yer : Gündüz İkeda Seminar Room
  Dil : English