The Möbius function of separable and decomposable permutations

DOI10.1016/J.JCTA.2011.06.002MaRDI QIDQ640846zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Alexander Burstein, Vít Jelínek, Einar Steingrímsson, Eva Jelínková

Publication date 21 October 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

decomposable permutationsMöbius functionpattern containmentpattern posetpermutation involvementseparable permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: We give a recursive formula for the Moebius function of an interval $[sigma,pi]$ in the poset of permutations ordered by pattern containment in the case where $pi$ is a decomposable permutation, that is, consists of two blocks where the first one contains all the letters 1, 2, ..., k for some k. This leads to many special cases of more explicit formulas. It also gives rise to a computationally efficient formula for the Moebius function in the case where $sigma$ and $pi$ are separable permutations. A permutation is separable if it can be generated from the permutation 1 by successive sums and skew sums or, equivalently, if it avoids the patterns 2413 and 3142. A consequence of the formula is that the Moebius function of such an interval $[sigma,pi]$ is bounded by the number of occurrences of $sigma$ as a pattern in $pi$. We also show that for any separable permutation $pi$ the Moebius function of $(1,pi)$ is either 0, 1 or -1.

Review text

Let \(S_n\) denote the permutations of \(\{1,\dots,n\}\); the union of all \(S_n\) (\(n \in \mathbb{N}\)) forms a poset with respect to pattern containment (also called permutation involvement). The paper is concerned with the Möbius function of this poset: first mentioned by \textit{H. Wilf} [``The patterns of permutations, Discrete Math. 257, No.\,2--3, 575--583 (2002; Zbl 1028.05002)], and studied by \textit{B. Sagan} and \textit{V. Vatter} for the case of layered permutations [``The Möbius function of a composition poset, J. Algebr. Comb. 24, No.\,2, 117--136 (2006; Zbl 1099.68081)]. Here, the authors consider the case of decomposable permutations (those expressible as direct sums of smaller permutations). They provide a recursive formula for the Möbius function of an interval \([\sigma,\pi]\) when \(\pi\) is decomposable. In the special case when \(\pi\) is separable (obtainable from \(1\) by successive sums and skew sums), the authors obtain a polynomial-time algorithm to compute the Möbius function. This leads to an alternative combinatorial interpretation for the Möbius function of separable permutations in terms of normal embeddings.

Recommendations

• scientific article; zbMATH DE number 6806830
• The Möbius function of the permutation pattern poset
• A formula for the Möbius function of the permutation poset based on a topological decomposition
• The Möbius function of permutations with an indecomposable lower bound
• A formula for the Möbius function of the permutation poset based on a topological decomposition

Cites work

• scientific article; zbMATH DE number 2186865 (Why is no real title available?)
• scientific article; zbMATH DE number 4158687 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• Parallel algorithms for separable permutations
• Pattern matching for permutations
• The Möbius function of a composition poset
• The Möbius function of factor order
• The Möbius function of the permutation pattern poset
• The patterns of permutations

Cited in

(21)

• Vincular pattern posets and the Möbius function of the quasi-consecutive pattern poset
• The Möbius function of permutations with an indecomposable lower bound
• Pattern posets
• On the growth of the Möbius function of permutations
• Enumeration of some classes of pattern avoiding matchings, with a glimpse into the matching pattern poset
• Generalized Dold sequences on partially-ordered sets
• The poset of mesh patterns
• 2413-balloon permutations and the growth of the Möbius function
• The poset of graphs ordered by induced containment
• On the topology of the permutation pattern poset
• A formula for the Möbius function of the permutation poset based on a topological decomposition
• On the Möbius function of permutations with one descent
• The Möbius function of generalized subword order
• Product decompositions of the symmetric group induced by separable permutations
• scientific article; zbMATH DE number 6806830 (Why is no real title available?)
• Intervals of permutations with a fixed number of descents are shellable
• On intervals of the consecutive pattern poset
• A formula for the Möbius function of the permutation poset based on a topological decomposition
• Zeros of the Möbius function of permutations
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Interview with Einar Steingrímsson

This page was built for publication: The Möbius function of separable and decomposable permutations

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