A spectral approach to consecutive pattern-avoiding permutations

Kitaev, Sergey and Ehrenborg, Richard and Perry, Peter (2011) A spectral approach to consecutive pattern-avoiding permutations. Journal of Combinatorics, 2 (3). pp. 305-353. ISSN 2156-3527 (https://doi.org/10.4310/JOC.2011.v2.n3.a1)

Full text not available in this repository.Request a copy

Abstract

We consider the problem of enumerating permutations in the symmetric group on n elements which avoid a given set of consecutive patterns S, and in particular computing asymptotics as n tends to infinity. We develop a general method which solves this enumeration problem using the spectral theory of integral operators onL2([0,1]m), where the patterns in S have length m+1.Kre\u{\i}n and Rutman’s generalization of the Perron–Frobenius theory of non-negative matrices plays a central role. Our methods give detailed asymptotic expansions and allow for explicit computation of leading terms in many cases.As a corollary to our results,we settle a conjecture of Warlimont on asymptotics for the number of permutations avoiding a consecutive pattern.

ORCID iDs

Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647, Ehrenborg, Richard and Perry, Peter;
CORE (COnnecting REpositories)