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.