The Partition monoid

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia

Last update: 9 April 2013

The Partition monoid

For k>0, let

Ak = { set partitions of {1,2,,k,1,2,,k} } ,and Ak+12 = { dAk+1 (k+1)and (k+1) are in the same block } . (1.1)

The propogating number of dAk is

pn(d) = ( the number of blocksdthat contain both an element of{1,2,,k}and an element of{1,2,,k} ) . (1.2)

For convenience, represent a set partition dAk by a graph with k vertices in the top row, labeled 1,,k left to right, and k vertices in the bottom row, labeled 1,,k left to right, with vertex i and vertex j connected by a path if i and j are in the same block of the set partition d. For example,

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 represents { {1,2,4,2,5}, {3}, {5,6,7,3,4,6,7}, {8,8}, {1} } ,

and has propagating number 3. The graph representing d is not unique.

Define the composition d1d2 of partition diagrams d1,d2Ak to be the set partition d1d2Ak obtained by placing d1 above d2 and identifying the bottom dots of d1 with the top dots of d2, removing any connected components that live entirely in the middle row.

For example,

ifd1= andd2= then d1d2= = .

Diagram multiplication makes Ak into an associative monoid with identity, 1 = . The propagating number satisfies

pn(d1d2) min(pn(d1),pn(d2)). (1.3)

A set partition is planar [Jon1993] if it can be represented as a graph without edge crossings inside of the rectangle formed by its vertices. For each k12>0, the following are submonoids of the partition monoid Ak:

Sk = {dAkpn(d)=k}, Ik = {dAkpn(d)<k}, Pk = {dAkdis planar}, Bk = {dAkall blocks ofdhave size 2},and Tk = PkBk. (1.4)

Examples are

I7, I6+12, P7, P6+12, B7, T7, S7.

For k12>0, there is an isomorphism of monoids

Pk1-1 T2k, (1.5)

which is best illustrated by examples. For k=7 we have


and for k=6+12 we have


Let k>0. By permuting the vertices in the top row and in the bottom row each dAk can be written as a product d=σ1tσ2, with σ1,σ2Sk and tPk, and so Ak=SkPkSk.

For example,

= . (1.6)

For >0, define

theBell number, B() = (the number of set partitions of{1,2,,}), theCatalan number, C() = 1+1 (2)= (2)- (2+1), (2)!!= (2-1)· (2-3) 5·3·1,and !=· (-1)2·1, (1.7)

with generating functions (see [Sta1997, 1.24f, and 6.2]),

0B() z!=exp (ez-1), 0C (-1)z= 1-1-4z2z, 0 (2(-1))!! z!= 1-1-2z2z, 0 !z!= 11-z. (1.8)


fork12>0 , Card(Ak)=B(2k) andCard(Pk)= Card(T2k)=C(2k), fork>0, Card(Bk)= (2k)!!,and Card(Sk)=k!. (1.9)

Presentation of the partition monoid

In this section, for convenience, we will write

d1d2=d1d2, ford1,d2 Ak.

Let k>0. For 1ik-1 and 1jk, define

pi+12 = i i+1 ,pj= j , ei = i i+1 ,si= i i+1 . (1.10)

Note that ei=pi+12pipi+1pi+12.

Theorem 1.11.

  1. The monoid Tk is presented by generators e1,,ek-1 and relations ei2=ei, eiei±1ei =ei,and eiej=ejei ,for i-j>1.
  2. The monoid Pk is presented by generators p12, p1, p32, ,pk and relations pi2=pi, pipi±12 pi=pi, andpi pj=pjpi, for i-j>1/2.
  3. The group Sk is presented by generators s1,,sk-1 and relations si2=1,si si+1si= si+1sisi+1 ,andsisj =sjsi,for i-j>1.
  4. The monoid Ak is presented by generators s1,,sk-1 and p12,p1,p32,,pk and relations in (b) and (c) and sipipi+1 si=pipi+1, sipi+12 =pi+12si= pi+12,si pisi=pi+1, sisi+1 pi+12 si+1si= pi+32, andsi pj=pjsi, forji-12 ,o,i+12,i+1, i+32.


Parts (a) and (c) are standard. See [GHJ1989, Proposition 2.8.1] and [Bou1968, Chapter IV, Section 1.3, Example 2], respectively. Part (b) is a consequence of (a) and the monoid isomorphism in (1.5).

(d) The right way to think of this is to realize that Ak is defined as a presentation by the generators dAk and the relations which specify the composition of diagrams. To prove the presentation in the statement of the theorem we need to establish that the generators and relations in each of these two presentations can be derived from each other. Thus it is sufficient to show that

  1. The generators in (1.10) satisfy the relations in Theorem 1.11.
  2. Every set partition dAk can be written as a product of the generators in (1.10).
  3. Any product d1d2 can be computed using the relations in Theorem 1.11.

(1) is established by a direct check using the definition of the multiplication of diagrams. (2) follows from (b) and (c) and the fact (1.6) that Ak=SkPkSk. The bulk of the work is in proving (3).

Step 1. First note that the relations in (a)–(d) imply the following relations:

(e1) pi+12 si-1 pi+12 = pi+12si si-1pi+12 = pi+12si si-1pi+12 si-1sisi si-1 = pi-12 pi+12 sisi-1 = pi-12 pi+12 si-1= pi+12 pi-12 si-1 = pi+12 pi-12. (e2) pisipi= sisipisi pi=si pi+1pi= pi+1pi. (f1) pipi+12 pi+1=pi pi+12si pi+1=pi pi+12pi si=pisi. (f2) pi+1pi+12 pi=pi+1si pi+12pi= sipipi+12 pi=sipi.

Step 2. Analyze how elements of Pk can be efficiently expressed in terms of the generators.

Let tPk. The blocks of t partition {1,,k} into top blocks and partition {1,,k} into bottom blocks. In t, some top blocks are connected to bottom blocks by an edge, but no top block is connected to two bottom blocks, for then by transitivity the two bottom blocks are actually a single block. Draw the diagram of t, such that if a top block connects to a bottom block, then it connects with a single edge joining the leftmost vertices in each block. The element tPk can be decomposed in block form as

t= ( pi1+12 pir+12 ) (pj1pjs)τ (p1pm) ( pr1+12 prn+12 ) (1.12)

with τSk, i1<i2<<ir, j1<j2<<js, 1<2<<m, and r1<r2<<rn. The left product of pis corresponds to the top blocks of t, the right product of pis corresponds to the bottom blocks of t, and the permutation τ corresponds to the propagation pattern of the edges connecting top blocks of t to bottom blocks of t. For example,

t= = = = = ( p212 p312 p612 ) (p3p4p6p7)τ (p2p3p4p7) ( p112 p212 ) , = ( p212 p312 p612 ) (p3p4p6p7) s2s3s5s4 (p2p3p4p7) ( p112 p212 ) .

The dashed edges of τ are “non-propagating” edges, and they may be chosen so that they do not cross each other. The propagating edges of τ do not cross, since t is planar.

Using the relations (f1) and (f2), the non-propagating edges of τ can be “removed”, leaving a planar diagram which is written in terms of the generators pi and pi+12. In our example, this process will replace τ by p212p2 p312p3 p512p5 p412p4, so that

t= = = ( p212 p312 p612 ) (p3p4p6p7)τ · p212p2 p312p3 p512p5 p412p4 · (p2p3p4p7) ( p112 p212 ) .

Step 3. If tPk and σ1Sk which permutes the top blocks of the planar diagram t, then there is a permutation σ2 of the bottom blocks of t such that σ1tσ2 is planar. Furthermore, this can be accomplished using the relations. For example, suppose

t = AAAAT1 AAT2 AAAAAAB1 AAAAB2 = ( p112 p212 ) (p2p3) T1 (p612) (p7) T2 p4p5s5 (p2p3p4) ( p112 p212 p312 ) B1 (p6p7) ( p512 p612 ) B2

is a planar diagram with top blocks T1 and T2 connected respectively to bottom blocks B1 and B2 and

σ1= so that σ1t= = AAT2 AAAAT1 AAAAAAB1 AAAAB2 =t,

then transposition of B1 and B2 can be accomplished with the permutation

σ1= so that σ1t=σ2 =tσ2= = AAT2 AAAAT1 AAAAB2 AAAAAAB1

which is planar. It is possible to accomplish these products using the relations from the statement of the theorem. In our example, with σ1= s2s1s3s2 s4s3s5s2 s4s6s1s3 s5s2s4s3 and with σ2= s4s5s6s3 s4s5s2s3 s4s1s2s3 ,

σ1T1T2p4 p5s5B1B2 σ2 = ( σ1T1T2 p4p5σ1-1 ) (σ1s5σ2) ( σ2-1B1 B2σ2 ) = T2T1 p3p4s4 B2B1,

where T2T1= (p112p2) ( p512 p612 p6p7 ) and B2B1= ( p2p3 p112 p212 ) ( p5p6p7 p412 p512 p612 ) .

Step 4. Let t,bPk and let πSk. Then tπb=txσ where xPk and σSk, and this transformation can be accomplished using the relations in (b), (c), and (d).

Suppose T is a block of bottom dots of t containing more than one dot and which is connected, by edges of π, to two top blocks B1 and B2 of b. Using Step 3 find permutations γ1,γ2Sk and σ1,σ2Sk such that

t=γ1tγ2 andb=σ1 bσ2

are planar diagrams with T as the leftmost bottom block of t and B1 and B2 as the two leftmost top blocks of b. Then

tπb = γ1-1t γ2-1π σ1-1b σ2-1 = γ1-1t ( γ2-1π σ1-1 ) bσ2-1 = γ1-1t ( γ2-1π σ1-1 ) bσ2-1 = tπσ1-1b σ2-1,

where b is a planar diagram with fewer top blocks than b has. This is best seen from the following picture, where tπb equals

t π b T B1 B2 = γ1-1 t γ2-1 π σ1-1 b σ2-1 T B1 B2 = γ1-1 t b σ2-1 γ2-1πσ1-1 T B1 B2 = γ1-1 t b σ2-1 γ2-1πσ1-1 T B1 B2

and the last equality uses the relations pi+12=pi+122 and the fourth relation in (d) (multiple times). Then tπb= γ1-1t γ2πσ1-1 bσ2-1 = tπb σ2-1, where π=πσ1-1.

By iteration of this process it is sufficient to assume that in proving Step 4 we are analyzing tπb where each bottom block of t connects to a single top block of b. Then, since π is a permutation, the bottom blocks of t must have the same sizes as the top blocks of b and π is the permutation that permutes the bottom blocks of t to the top blocks of b. Thus, by Step 1, there is σSk such that x=πbσ-1 is planar and

tπb=t(πbσ-1) =txσ.

Completion of the proof. If d1,d2Ak then use the decomposition Ak=SkPkSk (from (1.6)) to write d1 and d2 in the form

d1=π1tπ2 andd2=σ1b σ2,witht,b Pk,π1,π2, σ1,σ2Sk,

and use (b) and (c) to write these products in terms of the generators. Let π=π2σ1. Then Step 4 tells us that the relations give σSk and xPk such that

d1d2=π1t π2σ1bσ2= π1tπbσ2= π1txσσ2.

Using Step 2 and that Ak=SkPkSk, this product can be identified with the product diagram d1d2. Thus, the relations are sufficient to compose any two elements of Ak.

Notes and References

This is an excerpt of a paper entitled Partition algebras, written by Tom Halverson (Mathematics and Computer Science, Macalester College, Saint Paul, MN 55105, United States) and Arun Ram.

This research was supported in part by National Science Foundation Grant DMS-0100975. This research was also supported in part by the National Science Foundation (DMS-0097977) and the National Security Agency (MDA904-01-1-0032).

page history