Stirling posets
- PDF / 352,665 Bytes
- 35 Pages / 429.408 x 636.768 pts Page_size
- 66 Downloads / 184 Views
STIRLING POSETS BY
Mahir Bilen Can Department of Mathematics, Tulane University, New Orleans, LA 70118, USA e-mail: [email protected] AND
Yonah Cherniavsky Department of Mathematics, Ariel University, Kiryat Hamada, Ariel 40700 e-mail: [email protected]
ABSTRACT
We define combinatorially a partial order on the set partitions and show that it is equivalent to the Bruhat–Chevalley–Renner order on the upper triangular matrices. By considering subposets consisting of set partitions with a fixed number of blocks, we introduce and investigate “Stirling posets.” As we show, the Stirling posets have a hierarchy and they glue together to give the whole set partition poset. Moreover, we show that they (Stirling posets) are graded and EL-shellable. We offer various reformulations of their length functions and determine the recurrences for their length generating series.
1. Introduction Let n be a nonnegative integer. A collection S1 , . . . , Sr of non-empty subsets of an n-element set S is said to be a set partition of S if Si ’s (i = 1, . . . , r) are mutually disjoint and ri=1 Si = S. In this case, Si ’s are called the blocks of the partition. If n > 0 and S = {1, . . . , n}, the collection of all set partitions of S is denoted by Πn . We will often drop set parentheses and commas and just put vertical bars between blocks. If B1 , . . . , Bk are the blocks of a set partition π Received February 8, 2018 and in revised form June 11, 2019
185
186
M. B. CAN AND Y. CHERNIAVSKY
Isr. J. Math.
from Πn , then the standard form of π is defined as B1 |B2 | · · · |Bk , where we assume that min B1 < · · · < min Bk and the elements of each block are listed in increasing order. For example, π = 136|2459|78 is a set partition from Π9 . The set Πn is known to be a host to many interesting algebraic and combinatorial structures. Among these structures is the following well studied partial ordering: let A and A be two set partitions of S; A is said to refine A if each block of A is contained in some block of A . This “refinement ordering” makes Πn into a lattice, called the partition lattice, and by a result of Pudlak and Tuma (see [18]) it is known that every lattice is isomorphic to a sublattice of Πn for some n. A property that is shared by all partition lattices is that their order complexes have the homotopy type of a wedge of spheres. This important combinatorial topological property is seen by analyzing the labelings of the covering relations of the refinement ordering. Indeed, it follows as a consequence of the fact that the refinement ordering is an “edge lexicographically shellable” (EL-shellable for short) poset as shown by Gessel (mentioned in [2]) and by Wachs in [25]. We postpone the proper definition of EL-shellability to our preliminaries section but let us only mention very briefly that the property of EL-shellability of a graded poset is a way of linearly ordering the maximal faces of the associated order k−1 complex, say F1 , . . . , Fm , in such a way that Fk ∩( i=1 Fi ) is a nonempty union of maximal proper
Data Loading...
