Cycle-trail decomposition for partial permutations

Speaker: James East

Affiliation: University of Western Sydney

Time: Monday 28/04/2014 from 14:00 to 15:00

Venue: Access Grid UWS. Presented from Parramatta (EB.1.32), accessible from Campbelltown (26.1.50) and Penrith (Y239).

Abstract:

Everyone knows that a permutation can be written as a product of cycles; this is the cycle decomposition. For partial permutations, we also need trails. For example, $[1,2,3]$ means that $1$ maps to $2$, $2$ maps to $3$, but $3$ is mapped nowhere, and nothing is mapped to $1$.

Everyone also knows that a permutation can be written as a product of $2$-cycles (also known as transpositions). A partial permutation can be written as a product of $2$-cycles and $2$-trails. The question of when two such products represent the same (partial) permutation leads to consideration of presentations.

We give a presentation for the semigroup of all partial permutations of a finite set with respect to the generating set of all $2$-cycles and $2$-trails. We also give a presentation for the singular part of this semigroup with respect to the generating set of all $2$-trails.

Biography: James is a member of the Centre for Research in Mathematics and a lecturer with the School of Computing, Engineering and Mathematics.