Posets of shuffles
type: Item
instance of: scholarly article
title: Posets of shuffles
zbMATH Open document ID: 0659.06001
DOI: 10.1016/0097-3165(88)90018-0
author: Curtis Greene
published in: Journal of Combinatorial Theory. Series A
publication date: 1988-01-01T00:00:00Z
review text: A poset of shuffles is defined as follows: Let \b{x}\(=x_ 1x_ 2...x_ m\) and \b{y}\(=y_ 1y_ 2...y_ m\) be words, where it is assumed that the letters occurring in \b{x} and \b{y} are all distinct. Let \(W_{\underline x,\underline y}\) denote the set of all words \b{w} with letters from \b{x} and \b{y} such that the restriction of \b{w} to the letters of \b{x} resp. of \b{y} is a subword of \b{x} resp. of \b{y}. \(W_{\underline x,\underline y}\) becomes a poset if one defines \b{w}\(\leq \underline w'\) if and only if \b{w}' can be obtained from \b{w} by deleting letters of \b{x} and adding letters of \b{y}. The author establishes a lot of nice properties of this poset, for example, \(W_{\underline x,\underline y}\) is a lattice with rank function, it possesses a symmetric chain decomposition and it is supersolvable. Furthermore he derives formulas and generating functions for many combinatorial invariants such as the number of elements, the rank generating function, the number of maximal chains, the Möbius function, the zeta polynomial and the characteristic polynomial. All these invariants can be expressed in a simple way using evaluations of a certain family of polynomials which are related to classical Jacobi polynomials. The key idea for the proof of many facts is a certain canonical decomposition of \(W_{\underline x,\underline y}\) into Boolean sublattices, where the words \b{w} are classified with respect to their interface, i.e. the set of all letters x, y, where \(x\in \underline x\) and \(y\in \underline y\), and x immediately follows y in \b{w}.
reviewed by: Konrad Engel
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 4077288
zbMATH Keywords: generating functions for combinatorial invariants
zbMATH Keywords: poset of shuffles
MaRDI profile type: Publication
full work available at URL: 0097-3165(88)90018-0
OpenAlex ID: W2042008900
cites work: Shellable and Cohen-Macaulay Partially Ordered Sets
cites work: Q3952144
cites work: Q5805073
cites work: Q4196436
cites work: Q4509227
cites work: Generating Functions for Bessel and Related Polynomials
cites work: On the foundations of combinatorial theory I. Theory of M�bius Functions
cites work: Supersolvable lattices
cites work: Q3748279
cites work: General methods of sequence comparison
description: scientific article; zbMATH DE number 4077288