Shape and pattern containment of separable permutations.

MaRDI QIDQ2829071zbMATH OpenFDO

Authors Andrew Crites, Greta Panova, Gregory S. Warrington

Publication date 26 October 2016

Published in Ars Combinatoria (Search for Journal in Brave)

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

zbMATH Keywords

patternspermutationsseparable permutationsshape of permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: Every word has a shape determined by its image under the Robinson-Schensted-Knuth correspondence. We show that when a word w contains a separable (i.e., 3142- and 2413-avoiding) permutation sigma as a pattern, the shape of w contains the shape of sigma. As an application, we exhibit lower bounds for the lengths of supersequences of sets containing separable permutations.

Review text

The authors assume that the terms used are known and use them to formulate the main result of the paper, which is given in Theorem 1, the statement of which is:NEWLINENEWLINE``If a word \(w\) contains a separable permutation \(\sigma\) as a pattern, then \(\mathrm{sh}(w)\!\supseteq\mathrm{sh}(\sigma)\),NEWLINENEWLINEwhere \(\mathrm{sh}(w)\) is the shape of the permutation \(w\), i.e. the sequence of lengths of the cycles in the representation of \(w\) as a product of disjoint cycles.NEWLINENEWLINEA word \(w\) is a supersequence of a set of permutation if, for all \(\sigma\) from this set, \(\sigma\) is a subsequence of \(w\). As an application of Theorem 1, the authors provide lower bounds for the lengths of supersequences of sets containing separable permutations.

Recommendations

• Simple permutations, alternating permutations, and the superpatterns that contain them.
• Subclasses of the separable permutations
• Pattern containment in circular permutations
• The patterns of permutations
• Patterns in permutations and words.

Cited in

(2)

• Permutation patterns, Stanley symmetric functions, and generalized Specht modules
• Interview with Greta Panova

This page was built for publication: Shape and pattern containment of separable permutations.

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