turkmath.org

Türkiye'deki Matematiksel Etkinlikler


08 Kasım 2018, 15:40


Orta Doğu Teknik Üniversitesi Genel Seminer

Longest increasing subsequences in pattern-avoiding permutations

Gökhan Yıldırım
Bilkent University, Türkiye

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).
Çizge Kuramı ve Kombinatorik İngilizce
Gündüz İkeda Seminar Room

odtu 08.11.2018

Yaklaşan Seminerler Seminer Arşivi
 

İLETİŞİM

Akademik biriminizin ya da çalışma grubunuzun ülkemizde gerçekleşen etkinliklerini, ilan etmek istediğiniz burs, ödül, akademik iş imkanlarını veya konuk ettiğiniz matematikçileri basit bir veri girişi ile kolayca turkmath.org sitesinde ücretsiz duyurabilirsiniz. Sisteme giriş yapmak için gerekli bilgileri almak ya da görüş ve önerilerinizi bildirmek için iletişime geçmekten çekinmeyiniz. Katkı verenler listesi için tıklayınız.

Özkan Değer ozkandeger@gmail.com

DESTEK VERENLER

ja2019

31. Journees Arithmetiques Konferansı Organizasyon Komitesi

Web sitesinin masraflarının karşılanması ve hizmetine devam edebilmesi için siz de bağış yapmak, sponsor olmak veya reklam vermek için lütfen iletişime geçiniz.

ONLİNE ZİYARETÇİLER


©2013-2020 turkmath.org
Tüm hakları saklıdır