Whitney numbers of the second kind for the star poset
type: Item
instance of: scholarly article
title: Whitney numbers of the second kind for the star poset
zbMATH Open document ID: 0706.06006
DOI: 10.1016/S0195-6698(13)80127-8
author: Frederick J. Portier
author: Theresa P. Vaughan
published in: European Journal of Combinatorics
publication date: 1990-01-01T00:00:00Z
review text: A rank r on a (finite) poset (p,\(\leq)\) is a function with non-negative integer values such that if \(a\leq^*b\) (a is covered by b), then \(r(b)=r(a)+1\). The Cayley graph G(n) of the symmetric group \(V(n)=S_ n\) relative to the set of transpositions \(T=\{(1,n),...,(n-1,n)\}\) has an edge-set \(E(n)=\{e=(p_ 1,p_ 2)|\) \(p_ 1\pi =p_ 2\) for some \(\pi\in T\}\). The star-poset is defined on V(n) by assigning \(p_ 1\leq^*p_ 2\) iff \(e=(p_ 1,p_ 2)\in E(n)\) and \(d(p_ 1,I)<d(p_ 2,I)\), where I is the identity of \(S_ n\) and d is the usual graph distance. If a poset is ranked, the number of elements of rank k is denoted by \(W_ k\) and called a Whitney number of the second kind. If \(W_{n,k}\) is \(W_ k\) for G(n), then it is shown, after some detailed computations, which are structurally revealing, that if \(W_ n(X)=\sum W_{n,k}X^ k\), then \(G(Y)=(1-XY)^{-X-1}e^{Y-X^ 2Y}\) where \(G(Y)=\sum W_ k(X)Y^{k-1}/(k-1)!\) is the exponential generating function for \(\{W_ n(X)\}\). Using standard techniques and special information on the poset through a series of technical lemmas, a recurrence (Theorem 3.9) is obtained whence the formula is established. Combining subsets of ingredients obtained to the point of the derivation of the formula for G(Y) in a variety of ways, several other corollaries and formulas are obtained as well. Star posets are thus a nice class of interesting ranked posets which can be considered as combinatorially well understood examples. This paper is therefore certainly a useful addition to this type of literature.
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 4158686
zbMATH Keywords: rank on a poset
zbMATH Keywords: Cayley graph
zbMATH Keywords: symmetric group
zbMATH Keywords: star-poset
zbMATH Keywords: Whitney number
zbMATH Keywords: ranked posets
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Q4187840
cites work: Q3243274
cites work: Q3869280
description: scientific article; zbMATH DE number 4158686