A Spectral Approach to Consecutive Pattern-Avoiding Permutations - Mathematics > CombinatoricsReportar como inadecuado




A Spectral Approach to Consecutive Pattern-Avoiding Permutations - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We consider the problem of enumerating permutations in the symmetric group on$n$ elements which avoid a given set of consecutive pattern $S$, and inparticular computing asymptotics as $n$ tends to infinity. We develop a generalmethod which solves this enumeration problem using the spectral theory ofintegral operators on $L^{2}0,1^{m}$, where the patterns in $S$ has length$m+1$. Kre\u{\i}n and Rutman-s generalization of the Perron-Frobenius theoryof non-negative matrices plays a central role. Our methods give detailedasymptotic expansions and allow for explicit computation of leading terms inmany cases. As a corollary to our results, we settle a conjecture of Warlimonton asymptotics for the number of permutations avoiding a consecutive pattern.



Autor: Richard Ehrenborg, Sergey Kitaev, Peter Perry

Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados