The Algebra of Set Partitions

A set partition of [n] = {1, 2, ...,n} is a collection of non-empty disjoint subsets of [n], called blocks, whose union is [n]. A block permutation of [n] consists of two set partitions A and B of [n] having the same number of blocks,and a bijection f : A --> B. We consider the set BPn = {f : A --> B |f is a block permutation}. The elements in BPn can be visualized as graphs having two rows of n labeled vertices, corresponding to A and B. The connected components of each row are determined by connecting the vertices within each block of A and B. We then connect each block of A to the block of B which it maps to under f. The product g · f of two block permutations f : A --> B and g : C --> D of [n] is obtained by gluing the bottom of a graph representing f to the top of a graph representing g, and connecting each block of A to a block in D. We show that BPn is closed under this operation, and hence is a monoid. We have found a set of generators and seek to find a presentation for BPn. We also describe a Hopf algebra structure on BPn.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.