Partially ordered sets associated with permutations
Let \(\Sigma\) be a set of permutations of \([n]=\{1,...,n\}\). A poset P is called chain-permutational with respect to \(\Sigma\) iff the edges of the Hasse diagram of P can be labeled with labels from [n] so that the sequence of labels along each maximal chain of P is a permutation in \(\Sigma\), each permutation in \(\Sigma\) arises exactly once in this way and the cardinality of P is minimal with respect to this property. The author has shown that a chain-permutational poset is unique up to isomorphism for given \(\Sigma\), yielding the notation P(\(\Sigma)\). Further, P(\(\Sigma)\) is distributive if \(\Sigma\) is the family of linear extensions of some poset Q. The author studies in detail P(\(\Sigma)\) for 3 types of subsets \(\Sigma\) of the symmetric group \(S_ n:\) \(\Sigma^ 1_ n:=\{\sigma \in S_ n:\) \(\sigma^ 2=id\},\) \(\Sigma^ 2_ n:=\{\sigma \in S_ n:\) for no \(1\leq i_ 1<i_ 2<i_ 3\leq n\), \(\sigma (i_ 1)<\sigma (i_ 2)<\sigma (i_ 3)\},\) \(\Sigma^ 3_ n:=\{\sigma \in S_ n:\) for no \(1\leq i_ 1<i_ 2<i_ 3\leq n\), \(\sigma (i_ 1)<\sigma (i_ 2)\) and \(\sigma (i_ 1)<\sigma (i_ 3)\) and \(\sigma (i_ 2)>\sigma (i_ 3)\}.\) Recursive constructions for \(P(\Sigma^ i_ n)\), \(i=1,2,3\), are given, and the following properties are proved among other things: \(P(\Sigma^ 1_ n)\) is rank symmetric and rank unimodal, \(P(\Sigma^ i_ n)\) are lattices, \(i=2\), 3, \(P(\Sigma^ 2_ n)\) is supersolvable, \(P(\Sigma^ 3_ n)\) is edgewise lexicographically shellable. The Zeta polynomial of \(P(\Sigma^ 2_ n)\) and of \(P(\Sigma^ 3_ n)\) equals \((1-t)^{-n- 1}\cdot t\cdot \sum_{j\geq 0}C_{n-j}\left( \begin{matrix} n-j\\ j\end{matrix} \right)(t-1)^ j\), where \(C_ k\) is the kth Catalan number. The characteristic polynomial of \(P(\Sigma^ 2_ k)\) and of \(P(\Sigma^ 3_ n)\) equals \(t^{n-2}(t-1)(t-n+1)\).
- Finite automata for languages of combinatorial interest: An order theoretical point of view
- scientific article; zbMATH DE number 4045761 (Why is no real title available?)
- scientific article; zbMATH DE number 3771666 (Why is no real title available?)
- scientific article; zbMATH DE number 3443655 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- Permutations, matrices, and generalized Young tableaux
- Restricted permutations
- Supersolvable lattices
- Posets of shuffles
- Tableaux and chains in a new partial order of \(S_ n\)
- Orbits of antichains in ranked posets
- Deformation of chains via a local symmetric group action
- An ordering in \(\mathbb{R}^ n\) of a set of permutations
- Permutation lattices revisited
- A permutation group determined by an ordered set
- Finite automata for languages of combinatorial interest: An order theoretical point of view
- EL-labelings, supersolvability and 0-Hecke algebra actions on posets
- An order on circular permutations
- The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations
- FOUNTAIN-GOULD ORDERS IN ASSOCIATIVE PAIRS
- Some Results on the Sarkovskii Partial Ordering of Permutations
- scientific article; zbMATH DE number 496228 (Why is no real title available?)
- scientific article; zbMATH DE number 1047885 (Why is no real title available?)
- Decomposing labeled interval orders as pairs of permutations
- scientific article; zbMATH DE number 218835 (Why is no real title available?)
- The permutahedron of series-parallel posets
- Sign-balanced posets
- Sort-invariant non-messing-up
- 2-chains: An interesting family of posets
- Linear extensions of finite posets and a conjecture of G. Kreweras on permutations
- The enumeration of permutations whose posets have a maximum element
- Omitting parentheses from the cyclic notation
This page was built for publication: Partially ordered sets associated with permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1122600)
