## Physical Sciences 2

#### Presentation Title

Economical Generating Sets of the Monoid of Order-Preserving Partial Permutations

Dr. Scott Annin

#### Start Date

18-11-2017 11:30 AM

#### End Date

18-11-2017 11:45 AM

9-285

#### Session

Physical Sciences 2

Oral Talk

#### Subject Area

physical_mathematical_sciences

#### Abstract

Semigroups and monoids are important in such fields as computer science, cryptography, abstract algebra and other branches of mathematics. In this research project we seek to determine economical generating sets for the monoid of order-preserving injections of an n-element set, POI(n) A generating set for any semigroup or monoid is a collection of elements S such that every element of the semigroup or monoid can be expressed as a product of elements from S. Generating sets are of fundamental importance in fields across math and science, and mathematicians have great interest in studying generating sets of a variety of algebraic structures. By an economical generating set, we refer to a generating set containing as few elements as possible.

Using the algebra software package Groups, Algorithms, and Programming, GAP, we examine the key features of various generating sets of POI(n) including their sizes, the domains and ranges of the injections arising in them, and more. We confirm that every generating set of POI(n) contains at least n elements, a fact that follows from another theorem characterizing these generating sets according to the domain and ranges of the elements of the generating sets. Also, we make a conjecture about the number of generating sets for POI(n).

#### Summary of research results to be presented

Our results characterize the nature of the most economical generating sets of the monoid of order-preserving partial injections of an n-element set; POI(n):

Theorem 1: Let X be a subset of n elements in POI(n) of rank n-1. X generates POI(n) only if X has no partial identities, no two L-related elements, now two R-related elements. (Note that elements in POI(n) are L-related if and only if they share the same range, and they are R-related if and only if they share the same domain.)

Theorem 2: With X as in Theorem 1, we observe that X is a generating set for POI(n) if and only if X does not contain any subset that generates POI(T) for some proper subset T of {1,2,3,...,n}.

#### Share

COinS

Nov 18th, 11:30 AM Nov 18th, 11:45 AM

Economical Generating Sets of the Monoid of Order-Preserving Partial Permutations

9-285

Semigroups and monoids are important in such fields as computer science, cryptography, abstract algebra and other branches of mathematics. In this research project we seek to determine economical generating sets for the monoid of order-preserving injections of an n-element set, POI(n) A generating set for any semigroup or monoid is a collection of elements S such that every element of the semigroup or monoid can be expressed as a product of elements from S. Generating sets are of fundamental importance in fields across math and science, and mathematicians have great interest in studying generating sets of a variety of algebraic structures. By an economical generating set, we refer to a generating set containing as few elements as possible.

Using the algebra software package Groups, Algorithms, and Programming, GAP, we examine the key features of various generating sets of POI(n) including their sizes, the domains and ranges of the injections arising in them, and more. We confirm that every generating set of POI(n) contains at least n elements, a fact that follows from another theorem characterizing these generating sets according to the domain and ranges of the elements of the generating sets. Also, we make a conjecture about the number of generating sets for POI(n).