A spectral approach to consecutive pattern-avoiding permutations

DOI10.4310/JOC.2011.V2.N3.A1zbMATH Open1247.05013arXiv1009.2119MaRDI QIDQ446004FDOQ446004

Authors: Richard Ehrenborg, Sergey Kitaev, Peter Perry 

Publication date: 28 August 2012

Published in: Journal of Combinatorics (Search for Journal in Brave)

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^2([0,1{]}^m)$, where the patterns in $S$ has length $m+1$. Kreu{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.

Full work available at URL: https://arxiv.org/abs/1009.2119

Recommendations

• A probabilistic approach to consecutive pattern avoiding in permutations
• Computational approaches to consecutive pattern avoidance in permutations
• A survey of consecutive patterns in permutations
• Pattern avoidance in partial permutations (extended abstract)
• The feasible regions for consecutive patterns of pattern-avoiding permutations
• Pattern avoidance in alternating permutations and tableaux (extended abstract)
• Enumerating pattern avoidance for affine permutations
• On pattern avoiding indecomposable permutations
• Extended abstract for enumerating pattern avoidance for affine permutations
• Consecutive patterns in restricted permutations and involutions

zbMATH Keywords

enumeration problemWarlimont's conjecture

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Symmetric groups (20B30)

Cited In (20)

• On uniquely \(k\)-determined permutations
• Stanley-Wilf limits for patterns in rooted labeled forests
• Cyclically Consecutive Permutation Avoidance
• Clusters, generating functions and asymptotics for consecutive patterns in permutations
• Asymptotics of permutations with nearly periodic patterns of rises and falls
• Cycles in the graph of overlapping permutations avoiding barred patterns
• Counting and generating permutations in regular classes
• On the generating function for consecutively weighted permutations
• Number of cycles in the graph of 312-avoiding permutations
• Descent pattern avoidance
• The \(f\)-vector of the descent polytope
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Consecutive pattern containment and c-Wilf equivalence
• Asymptotics of the Euler number of bipartite graphs
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• The boustrophedon transform for descent polytopes
• Wilf equivalences for patterns in rooted labeled forests
• The expectation of the Vandermonde product squared for uniform random variables
• A probabilistic approach to consecutive pattern avoiding in permutations
• Title not available (Why is that?)

This page was built for publication: A spectral approach to consecutive pattern-avoiding permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q446004)