Counting Pattern Avoiding Permutations Via Integral Operators

COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR II
Topic:Counting Pattern Avoiding Permutations Via Integral Operators
Speaker:Richard Ehrenborg
Affiliation:University of Kentucky; Member, School of Mathematics
Date:Tuesday, November 23
Time/Room:10:30am - 12:30pm/S-101

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.