Computer Science/Discrete Mathematics Seminar II

A permutation pi=(pi_{1},...,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 and settles a conjecture of Warlimont. This is joint work with Sergey Kitaev and Peter Perry.