Counting pattern avoiding permutations via integral operators

Abstract: A permutation \pi=(\pi_{1},\ldots,\pi_{n}) is consecutive 123-avoiding if there is no sequence of the form \pi_{i} < \pi_{i+1} < \pi_{i+2}. More generally, for S a collection of permutations on m+1 elements, this definition extends to define consecutive S-avoiding permutations. We show that the spectrum of an associated integral operator on the space L^{2}[0,1]^{m} determines the asymptotics of the number of consecutive S-avoiding permutations. Moreover, using an operator version of the classical Frobenius-Perron theorem due to Krein and Rutman, we prove asymptotic results for large classes of patterns S. This extends previously known results of Elizalde. This is joint work with Sergey Kitaev and Peter Perry.

Refreshments will be served at 2:45 p.m. (MATX 1115, Math Lounge).