Algebraic Combinatorics Seminar - Neal Madras

Thursday, January 30, 2020 2:30 pm - 2:30 pm EST (GMT -05:00)

Title: Random Pattern-Avoiding Permutations

Speaker: Neal Madras
Affiliation: York University
Room: MC 5417


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 plotted as a function from {1,..,N} to itself, some striking structure appears.  I shall describe what is known probabilistically about such structure, including clustering and large empty regions in the plot.

I shall also describe an attempt (with Justin Troyka) to study these plots under periodic boundary conditions, inspired by work in statistical physics.  This led us to consider affine permutations on the integers with a new boundedness condition.