Counting pattern avoiding permutations via integral operators

Richard Ehrenborg

University of Kentucky

Brandeis University

Thursday, September 14, 2006

Talk at 4:30 p.m. in 317 Goldsmith Hall

Tea at 4:00 p.m. in 300 Goldsmith Hall

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 Kre\u{\i}n 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.

Home Web page: Alexandru I. Suciu Posted: August 22, 2006
Comments to: URL: