DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Counting pattern avoiding permutations via integral operators

Speaker: Richard Ehrenborg, University of Kentucky and Institute for Advanced Study

Date: Thursday, February 24, 2011 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

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.