Some open problems on permutation patterns

DOI10.1017/CBO9781139506748.007MaRDI QIDQ2875859zbMATH OpenOpenAlexFDO

Authors Einar Steingrímsson

Publication date 12 August 2014

Published in Surveys in Combinatorics 2013 (Search for Journal in Brave)

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

zbMATH Keywords

growth rates of permutation classesMöbius functionposet of permutations

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Permutations, words, matrices (05A05)

Abstract: This is a brief survey of some open problems on permutation patterns, with an emphasis on subjects not covered in the recent book by Kitaev, emph{Patterns in Permutations and words}. I first survey recent developments on the enumeration and asymptotics of the pattern 1324, the last pattern of length 4 whose asymptotic growth is unknown, and related issues such as upper bounds for the number of avoiders of any pattern of length $k$ for any given $k$. Other subjects treated are the M"obius function, topological properties and other algebraic aspects of the poset of permutations, ordered by containment, and also the study of growth rates of permutation classes, which are containment closed subsets of this poset.

Recommendations

• Permutations avoiding certain patterns: The case of length 4 and some generalizations
• Permutations avoiding 1324 and patterns in Łukasiewicz paths
• Pattern-avoiding involutions: exact and asymptotic enumeration
• The Möbius function of the permutation pattern poset
• Large deviations and ratio limit theorems for pattern-avoiding permutations

Cited in

(18)

• On a pattern sequencing problem to minimize the maximum number of open stacks
• Reduced word manipulation: patterns and enumeration
• Equidistributions of mesh patterns of length two and Kitaev and Zhang's conjectures
• Lower bounds for superpatterns and universal sequences
• A structural characterisation of \(\mathrm{Av}(1324)\) and new bounds on its growth rate
• A viewpoint for permutations with a low density of patterns
• On the topology of the permutation pattern poset
• Extremal functions of forbidden multidimensional matrices
• 1324-avoiding permutations revisited
• Permutations avoiding 1324 and patterns in Łukasiewicz paths
• Using functional equations to enumerate 1324-avoiding permutations
• On the Möbius function of permutations with one descent
• Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations
• On intervals of the consecutive pattern poset
• A formula for the Möbius function of the permutation poset based on a topological decomposition
• Pattern-avoiding polytopes
• Preface to the special issue of Permutation Patterns 2021 (PP2021)
• Poset pattern-avoidance problems posed by Yakoubov

This page was built for publication: Some open problems on permutation patterns

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