You are here

The shape of a random pattern-avoiding permutation

Christopher Hoffman, University of Washington
Wednesday, February 19, 2020 - 3:30pm to 5:00pm
PDL C-401
Christopher Hoffman

A permutation that avoids the pattern 4321 has a longest decreasing sequence of length 3. We fix \$n\$, choose \$\sigma\$ a 4321-avoiding permutation uniformly at random and plot the points of the form \$(i/n,\sigma(i)/n)\$ for \$1 \leq i \leq n\$. Looking at this plot it is clear that the indices 1 through \$n\$ can be partitioned into three sets. By linear interpolation from these three sets we can generate three functions. We show that the scaling limit of this measure on triples of functions is given by the eigenvalues of a ensemble of random matrices. We also discuss the scaling limits of other patterns.

4321-avoiding permutation example