A Spectral Approach to Consecutive Pattern-Avoiding Permutations

2010/09/10 by Richard Ehrenborg, Ehrenborg, Richard, Sergey Kitaev +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Spectral Theory (math.SP) #math.CO #math.SP

paper · pdf · doi:10.48550/arxiv.1009.2119

a reference is added; corrected typos; to appear in Journal of Combinatorics

arxiv created 2011/10/11 · arxiv updated 2011/10/13

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 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 on L²([0,1]^m), where the patterns in S has length m+1. Kre\uı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.

Related

• Asymptotic enumeration of permutations avoiding generalized patterns
• Cyclically consecutive permutation avoidance
• A probabilistic approach to consecutive pattern avoiding in permutations
• Increasing and Decreasing Subsequences of Permutations and Their Variants
• A survey of consecutive patterns in permutations