Last update: 9 April 2013
The propogating number of is
For convenience, represent a set partition by a graph with vertices in the top row, labeled left to right, and vertices in the bottom row, labeled left to right, with vertex and vertex connected by a path if and are in the same block of the set partition For example,
and has propagating number 3. The graph representing is not unique.
Define the composition of partition diagrams to be the set partition obtained by placing above and identifying the bottom dots of with the top dots of removing any connected components that live entirely in the middle row.
Diagram multiplication makes into an associative monoid with identity, 1 = . The propagating number satisfies
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 the following are submonoids of the partition monoid
For there is an isomorphism of monoids
which is best illustrated by examples. For we have
and for we have
Let By permuting the vertices in the top row and in the bottom row each can be written as a product with and and so
with generating functions (see [Sta1997, 1.24f, and 6.2]),
Presentation of the partition monoid
In this section, for convenience, we will write
Let For and define
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 is defined as a presentation by the generators 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) 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 The bulk of the work is in proving (3).
Step 1. First note that the relations in (a)–(d) imply the following relations:
Step 2. Analyze how elements of can be efficiently expressed in terms of the generators.
Let The blocks of partition into top blocks and partition into bottom blocks. In 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 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 can be decomposed in block form as
with and The left product of corresponds to the top blocks of the right product of corresponds to the bottom blocks of and the permutation corresponds to the propagation pattern of the edges connecting top blocks of to bottom blocks of For example,
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 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 and In our example, this process will replace by so that
Step 3. If and which permutes the top blocks of the planar diagram then there is a permutation of the bottom blocks of such that is planar. Furthermore, this can be accomplished using the relations. For example, suppose
is a planar diagram with top blocks and connected respectively to bottom blocks and and
then transposition of and can be accomplished with the permutation
which is planar. It is possible to accomplish these products using the relations from the statement of the theorem. In our example, with and with
Step 4. Let and let Then where and and this transformation can be accomplished using the relations in (b), (c), and (d).
Suppose is a block of bottom dots of containing more than one dot and which is connected, by edges of to two top blocks and of Using Step 3 find permutations and such that
are planar diagrams with as the leftmost bottom block of and and as the two leftmost top blocks of Then
where is a planar diagram with fewer top blocks than has. This is best seen from the following picture, where equals
and the last equality uses the relations and the fourth relation in (d) (multiple times). Then where
By iteration of this process it is sufficient to assume that in proving Step 4 we are analyzing where each bottom block of connects to a single top block of Then, since is a permutation, the bottom blocks of must have the same sizes as the top blocks of and is the permutation that permutes the bottom blocks of to the top blocks of Thus, by Step 1, there is such that is planar and
Completion of the proof. If then use the decomposition (from (1.6)) to write and in the form
and use (b) and (c) to write these products in terms of the generators. Let Then Step 4 tells us that the relations give and such that
Using Step 2 and that this product can be identified with the product diagram Thus, the relations are sufficient to compose any two elements of
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).