Random ubiquitous transformation semigroups
Julius Jonušas, Sascha Troscheit · Semigroup Forum · 2019
A smallest generating set of a semigroup is a generating set of the smallest cardinality. Similarly, an irredundant generating set X is a generating set such that no proper subset of X is also a generating set. A semigroup S is ubiquitous if every irredundant generating set of S is of the same cardinality. We are motivated by a naïve algorithm to find a small generating set for a semigroup, which in practice often outputs a smallest generating set. We give a sufficient condition for a transformation semigroup to be ubiquitous and show that a transformation semigroup generated by k randomly chosen transformations asymptotically satisfies the sufficient condition. Finally, we show that under this condition the output of the previously mentioned naïve algorithm is irredundant.