Pattern-avoiding permutation powers

DOI10.1016/J.DISC.2020.112017MaRDI QIDQ2198373zbMATH OpenOpenAlexFDO

Authors Amanda Burcroff, Colin Defant

Publication date 10 September 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

pattern avoidanceRobinson-Schensted-Knuth correspondencestrong pattern avoidancepermutation orderpermutation powersubgroup pattern avoidance

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: Recently, B'ona and Smith defined strong pattern avoidance, saying that a permutation $pi$ strongly avoids a pattern $au$ if $pi$ and $p{i}^2$ both avoid $au$. They conjectured that for every positive integer $k$, there is a permutation in $S_{k^3}$ that strongly avoids $123cdots(k+1)$. We use the Robinson--Schensted--Knuth correspondence to settle this conjecture, showing that the number of such permutations is at least $k^{k^3/2+O(k^3/logk)}$ and at most $k^{2k^3+O(k^3/logk)}$. We enumerate $231$-avoiding permutations of order $3$, and we give two further enumerative results concerning strong pattern avoidance. We also consider permutations whose powers all avoid a pattern $au$. Finally, we study subgroups of symmetric groups whose elements all avoid certain patterns. This leads to several new open problems connecting the group structures of symmetric groups with pattern avoidance.

Recommendations

• On a conjecture about strong pattern avoidance
• Pattern avoidance in permutations and their squares
• scientific article; zbMATH DE number 3895076
• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
• Symmetric permutations avoiding two patterns

Cites work

• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1507230 (Why is no real title available?)
• An upper bound on the number of \((132, 213)\)-avoiding cyclic permutations
• Combinatorics of permutations
• Composability of permutation classes
• Compositions of pattern restricted sets of permutations
• Cyclic permutations realized by signed shifts
• Enumerating \(r\)c-invariant permutations with no long decreasing subsequences
• Pattern avoidance in permutations and their squares
• Patterns in permutations and words.
• Permutation Involvement and Groups
• Permutation groups, pattern involvement, and Galois connections
• Quelques remarques sur une Construction de Schensted.
• Restricted permutations
• Spectral functions, special functions and the Selberg zeta function
• Two first-order logics of permutations

Cited in

(14)

• Rational generating series for affine permutation pattern avoidance
• On a conjecture about pattern avoidance of cyclic permutations
• Pattern-restricted permutations composed of 3-cycles
• Cyclic permutations avoiding patterns in both one-line and cycle forms
• Permutation groups arising from pattern involvement
• On a conjecture about strong pattern avoidance
• On pattern-avoiding Fishburn permutations
• Pattern avoidance and the fundamental bijection
• Powers of permutations that avoid chains of patterns
• scientific article; zbMATH DE number 1952889 (Why is no real title available?)
• On the permutations that strongly avoid the pattern 312 or 231
• Refinement permutations of prime power order
• scientific article; zbMATH DE number 7731168 (Why is no real title available?)
• Pattern-restricted permutations of small order

This page was built for publication: Pattern-avoiding permutation powers

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