On the longest monotone and alternating subsequences of pattern-avoiding permutations

Neal Madras, Gökhan Yıldırım

Published 2016-08-22Version 1

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 classes that avoid one pattern of length 4 or more. Typically, 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. As a byproduct, we derive some new properties of the "rare region" in the graph of a random permutation avoiding a pattern $\tau$ of length $k$ of the form $k\tau_2\cdots\tau_k$.