20 November 2007

Pattern avoidance

Here's a paper I found while Googling for something else a while ago: On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern, by Richard Arratia, from the Electronic Journal of Combinatorics, Volume 6(1) (1999), note N1.

Pattern avoidance in permutations is a beautiful little subject, about which I don't know that much -- but not that much is known. For example, see Bridget Tenner's remarkably short database of permutation pattern avoidance; okay, so the state of knowledge isn't quite as bad as this makes it look, but it's not that good either. (A good introduction to the area seems to be Miklos Bona's Combinatorics of Permutations, which has a couple chapters on the area. However, if you're at Penn I don't recommend Bona's book, because I have the library copy and I don't want to give it up.

Let p1 p2 ... pn be a permutation of the integers from 1 to n. We say a permutation is, for example, 231-avoiding if there is no i < j < k such that pk < pi < pj. That is, a 231-pattern in a permutation is a set of three letters in the word representing it which, when read from left to right, fall in the same order as the numbers 2, 3, 1; a permutation is 231-avoiding if it has no 231-patterns. So, for example, 26415837 is not a 231-avoiding permutation of [8], because 2, 6, 1 form a 231-pattern. A similar definition can be made of a σ-avoiding permutation for any permutation (called a "pattern") σ. Rather surprisingly, the number of patterns avoiding any permutation of length 3 is the same, and this can be proven bijectively. But some permutations of length 4, for example, are "easier" to avoid than others; what makes a pattern easy or difficult to avoid isn't totally clear. The Stanley-Wilf conjecture (now proven, by Gabor Tardos and Adam Marcus) states that if we let F(n, σ) be the number of permutations of [n] which avoid the pattern σ, then
\lim_{n \to \infty} F(n, \sigma)^{1/n}

exists and is finite. For example, 231-avoiding permutations are in bijection with Catalan trees of size n, so F(n, 231) is the nth Catalan number. Thus
F(n, 231) \sim {4^n \over \sqrt{\pi n^3}}

and so we get the constant 4 for the limit above. The Stanley-Wilf conjecture thus associates a constant with each permutation, but not too many of these constants are known. (I won't attempt to tabulate the known constants; I suspect someone out there has already done it. At the very least, there are a fair number of results scattered throughout the applicable chapters of Bona's textbook.)

Anyway, a natural question to ask is "how many σ-patterns does a permutation of [n] have, on average?" This is fairly obviously
{1 \over k!} {n \choose k}

since there are ${n \choose k}$possible sites for such patterns, and each site actually contains such a pattern with probability 1/k!; from playing around with a few small cases it looks like the variance of the number of σ-patterns is asymptotically cσn2k-1, where the constants cσ don't appear to be anything nice in general. (The only way I know how to compute these variances basically comes down to considering all the ways in which two instances of the same pattern in the same permutation can intersect and enumerating a large number of cases; it's not surprising the results are ugly. I've only done it in a couple simple cases, and I don't want to quote the results here because I haven't had the patience to check my computations.) In the case of inversions, which are just 21-patterns, these are the classical results that the average number of inversions of an n-permutation is asymptotically n2/4, with variance n3/36. I have a faint hope that there might be some relation between the constant "1/36" there and the fact that the number of 21-avoiding permutations of n is just 1n (that is, 1 -- this is the simplest case of the Stanley-Wilf conjecture, that there is only one inversion-free permutation) but I don't actually know enough of these constants to see what's going on.

Anyway, what I want to bring attention to is the conjecture of Alon at the end of this note:
Conjecture (Alon): The threshold length t(k), for a random permutation to contain all k-permutations with substantial probability, has t(k) ~ k^2/4.
Why should this be true? The note by Arratia gives some idea -- it relates this problem to the longest common subsequence problem -- but I want an argument that stays purely within the pattern avoidance realm. I'm working on it.

1 comment:

Michael Albert said...

From the "blowing ones own horn" department -- the area is significantly more active than it might appear (and certainly Herb Wilf could tell you lots about it ...)

Meantime, for "random" style methods on some related problems:

Permutations Containing Many Patterns (to appear shortly in the Annals of Combinatorics volume devoted to the Permutation Patterns conference in Iceland in 2006)

On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
Random Structures and Algorithms
Volume 31, Issue 2, Date: September 2007, Pages: 227-238