A spectral approach to consecutive pattern-avoiding permutations

Sergey Kitaev, Richard Ehrenborg, Peter Perry

Research output: Contribution to journalArticle

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.
LanguageEnglish
Pages305-353
Number of pages49
JournalJournal of Combinatorics
Volume2
Issue number3
DOIs
Publication statusPublished - 2011

Fingerprint

Pattern-avoiding Permutation
Consecutive
Permutation
Perron-Frobenius Theory
Nonnegative Matrices
Spectral Theory
Symmetric group
Integral Operator
Enumeration
Asymptotic Expansion
Corollary
Infinity
Tend
Computing
Term

Keywords

  • pattern avoiding permutation
  • enumerating permutations
  • non-negative matrices

Cite this

Kitaev, Sergey ; Ehrenborg, Richard ; Perry, Peter. / A spectral approach to consecutive pattern-avoiding permutations. In: Journal of Combinatorics. 2011 ; Vol. 2, No. 3. pp. 305-353.
@article{6525b1c949244578bd78c7710f716074,
title = "A spectral approach to consecutive pattern-avoiding permutations",
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.",
keywords = "pattern avoiding permutation, enumerating permutations, non-negative matrices",
author = "Sergey Kitaev and Richard Ehrenborg and Peter Perry",
year = "2011",
doi = "10.4310/JOC.2011.v2.n3.a1",
language = "English",
volume = "2",
pages = "305--353",
journal = "Journal of Combinatorics",
issn = "2156-3527",
number = "3",

}

A spectral approach to consecutive pattern-avoiding permutations. / Kitaev, Sergey; Ehrenborg, Richard; Perry, Peter.

In: Journal of Combinatorics, Vol. 2, No. 3, 2011, p. 305-353.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A spectral approach to consecutive pattern-avoiding permutations

AU - Kitaev, Sergey

AU - Ehrenborg, Richard

AU - Perry, Peter

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - pattern avoiding permutation

KW - enumerating permutations

KW - non-negative matrices

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/spectral.pdf

U2 - 10.4310/JOC.2011.v2.n3.a1

DO - 10.4310/JOC.2011.v2.n3.a1

M3 - Article

VL - 2

SP - 305

EP - 353

JO - Journal of Combinatorics

T2 - Journal of Combinatorics

JF - Journal of Combinatorics

SN - 2156-3527

IS - 3

ER -