Minimal Generating Sets of the Monoid of Partial Order-Preserving Injections

Abstract

Monoids arise in such fields as computer science, physics, and numerous branches of mathematics including abstract algebra, cryptography and operator theory. In this research project we seek to determine minimal generating sets for the monoid of partial order-preserving injections of an n-element set, POI(n). A generating set for a monoid is a collection of elements S such that every element of the monoid can be expressed as a product of elements from S. Generating sets are of fundamental importance across math and science, and mathematicians have great interest in studying generating sets of a variety of algebraic structures. By a minimal generating set, we refer to a generating set for which no proper subset is a generating set. In this paper, we provide necessary and sufficient conditions for a set to be a minimal generating set for POI(n), and we show that there are exactly (n-1)! minimal generating sets for POI(n).