Longest monotone subsequences and rare regions of pattern-avoiding permutations

Neal Madras¹ ; Gökhan Yıldırım

¹York University

The electronic journal of combinatorics, Tome 24 (2017) no. 4

Résumé

We consider the distributions of the lengths of the longest monotone and alternating subsequences in classes of permutations of size $n$ that avoid a specific pattern or set of patterns, with respect to the uniform distribution on each such class. We obtain exact results for any class that avoids two patterns of length 3, as well as results for some classes that avoid one pattern of length 4 or more. In our results, the longest monotone subsequences have expected length proportional to $n$ for pattern-avoiding classes, in contrast with the $\sqrt n$ behaviour that holds for unrestricted permutations. In addition, for a pattern $\tau$ of length $k$, we scale the plot of a random $\tau$-avoiding permutation down to the unit square and study the "rare region", which is the part of the square that is exponentially unlikely to contain any points. We prove that when $\tau_1>\tau_k$, the complement of the rare region is a closed set that contains the main diagonal of the unit square. For the case $\tau_1=k,$ we also show that the lower boundary of the part of the rare region above the main diagonal is a curve that is Lipschitz continuous and strictly increasing on $[0,1]$.

Détail

DOI : 10.37236/6402

Classification : 05A05, 05A16, 60F99
Mots-clés : pattern-avoiding permutations, longest increasing subsequence problem, longest alternating subsequence, rare regions