A "pattern of length k" is simply a permutation of {1,..,k}.

This pattern is said to be contained in a permutation of {1,...,N} (for N>k) if there is a subsequence of k elements of the (long) permutation that appears in the same relative order as the pattern.

(E.g. the pattern 312 is contained in the permutation 2463175 because the latter contains the subsequence 615.) A permutation avoids the pattern P if it does not contain P.

For a given P, let AV[N;P] be the set of permutations of {1,..,N} that avoid P. The cardinality of AV[N;P] has been extensively studied by combinatorialists.

This talk looks at properties of permutations drawn uniformly at random from AV[N;P] for large N. When such a permutation is graphed as a function from {1,..,N} to itself, some striking structure appears. I shall describe what is known probabilistically about such structure, including

(a) clustering and large empty regions in the graph, and

(b) long monotone subsequences.