# Examples¶

This page contains the documentation for various examples of presentations of finitely presented semigroups and monoids.

Presentations from the following sources are implemented: [GH19]; [God09]; [Eas21]; [MM07]; [AR00]; [KM07]; [Bur12]; [GM09]; [CEK+01]; [CRRT94]; [AR22]; [EEF07]; [Fit03]; [Eas11]; ; [Rus95]; [Aiz58]; [CM79]; [Knu70]; ; [Moo97]; [Aiz62]; [Fer22]; [FP22].

type libsemigroups::fpsemigroup::author

The values in this enum class are used to specify the authors of a presentation. Where there are different presentations by different authors, values of this type can be passed as an argument to disambiguate which presentation is wanted.

inline author libsemigroups::fpsemigroup::operator+(author auth1, author auth2)

This operator can be used arbitrarily to combine author values (see author).

std::ostringstream &libsemigroups::fpsemigroup::operator<<(std::ostringstream &oss, author val)

This operator can be used to produce string representations of author values.

## Contents¶

 symmetric_group() A presentation for the symmetric group. alternating_group() A presentation for the alternating group. full_transformation_monoid() A presentation for the full transformation monoid. partial_transformation_monoid() A presentation for the partial transformation monoid. symmetric_inverse_monoid() A presentation for the symmetric inverse monoid. dual_symmetric_inverse_monoid() A presentation for the dual symmetric inverse monoid. uniform_block_bijection_monoid() A presentation for the uniform block bijection monoid. partition_monoid() A presentation for the partition monoid. brauer_monoid() A presentation for the Brauer monoid. rectangular_band() A presentation for a rectangular band. stellar_monoid() A presentation for the stellar monoid. chinese_monoid() A presentation for the Chinese monoid. monogenic_semigroup() A presentation for a monogenic semigroup. plactic_monoid() A presentation for the plactic monoid. stylic_monoid() A presentation for the stylic monoid. fibonacci_semigroup() A presentation for a Fibonacci semigroup. temperley_lieb_monoid() A presentation for the Temperley-Lieb monoid. singular_brauer_monoid() A presentation for the singular part of the Brauer monoid. orientation_preserving_monoid() A presentation for the monoid of orientation preserving mappings. orientation_reversing_monoid() A presentation for the monoid of orientation reversing mappings. order_preserving_monoid() A presentation for the monoid of order preserving mappings. cyclic_inverse_monoid() A presentation for the cyclic inverse monoid. order_preserving_cyclic_inverse_monoid() A presentation for the order-preserving part of the cyclic inverse monoid. partial_isometries_cycle_graph_monoid() A presentation for the monoid of partial isometries of a cycle graph. not_symmetric_group() A non-presentation for the symmetric group.

## Full API¶

std::vector<relation_type> libsemigroups::fpsemigroup::symmetric_group(size_t n, author val = author::Carmichael, size_t index = 0)

A presentation for the symmetric group.

Returns a vector of relations giving a monoid presentation for the symmetric group. The argument val determines the specific presentation which is returned. The options are:

Author

Index

No. generators

No. relations

Reference

author::Burnside + author::Miller

0

$$n - 1$$

$$n^3 - 5n^2 + 9n - 5$$

p.464 of 10.1017/CBO9781139237253

author::Carmichael

0

$$n - 1$$

$$(n - 1)^2$$

Comment 9.5.2 of 10.1007/978-1-84800-281-4

author::Coxeter + author::Moser

0

$$n - 1$$

$$n(n + 1)/2$$

Ch.3, Prop 1.2 of hdl.handle.net/10023/2821

author::Moore

0

$$2$$

$$n + 1$$

Ch. 3, Prop 1.1 of hdl.handle.net/10023/2821

1

$$n - 1$$

$$n(n + 1)/2$$

Comment 9.5.3 of 10.1007/978-1-84800-281-4

The default for val is author::Carmichael. The default for index is 0.

Parameters
• n – the degree of the symmetric group

• val – the author of the presentation

Throws
Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::alternating_group(size_t n, author val = author::Moore)

A presentation for the alternating group.

Returns a vector of relations giving a monoid presentation defining the alternating group of degree n. The argument val determines the specific presentation which is returned. The options are:

The default for val is author::Moore.

Parameters
• n – the degree of the alternating group

• val – the author of the presentation

Throws
Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::full_transformation_monoid(size_t n, author val = author::Iwahori)

A presentation for the full transformation monoid.

Returns a vector of relations giving a monoid presentation defining the full transformation monoid. The argument val determines the specific presentation which is returned. The options are:

The default for val is author::Iwahori.

Parameters
• n – the degree of the full transformation monoid

• val – the author of the presentation

Throws
Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::partial_transformation_monoid(size_t n, author val = author::Sutov)

A presentation for the partial transformation monoid.

Returns a vector of relations giving a monoid presentation defining the partial transformation monoid. The argument val determines the specific presentation which is returned. The options are:

The default for val is author::Sutov.

Parameters
• n – the degree of the partial transformation monoid

• val – the author of the presentation

Throws

LibsemigroupsException – if val is not listed above (modulo order of author)

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::symmetric_inverse_monoid(size_t n, author val = author::Sutov)

A presentation for the symmetric inverse monoid.

Returns a vector of relations giving a monoid presentation defining the symmetric inverse monoid. The argument val determines the specific presentation which is returned. The options are:

The default for val is the only option above.

Parameters
• n – the degree of the symmetric inverse monoid

• val – the author of the presentation

Throws

LibsemigroupsException – if val is not listed above (modulo order of author)

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::dual_symmetric_inverse_monoid(size_t n, author val = author::Easdown + author::East + author::FitzGerald)

A presentation for the dual symmetric inverse monoid.

Returns a vector of relations giving a semigroup presentation defining the dual symmetric inverse monoid of degree n. The argument val determines the specific presentation which is returned. The options are:

The default for val is the only option above.

Parameters
• n – the degree

• val – the author of the presentation

Throws
Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::uniform_block_bijection_monoid(size_t n, author val = author::FitzGerald)

A presentation for the uniform block bijection monoid.

Returns a vector of relations giving a semigroup presentation defining the uniform block bijection monoid of degree n. The argument val determines the specific presentation which is returned. The only option is:

The default for val is the only option above.

Parameters
• n – the degree

• val – the author of the presentation

Throws
Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::partition_monoid(size_t n, author val = author::East)

A presentation for the partition monoid.

Returns a vector of relations giving a semigroup presentation defining the partition monoid of degree n. The argument val determines the specific presentation which is returned. The options are:

The default for val is author::East.

Parameters
• n – the degree

• val – the author of the presentation

Throws
Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::brauer_monoid(size_t n)

A presentation for the Brauer monoid.

Returns a vector of relations giving a semigroup presentation defining the Brauer monoid of degree n, as described in Theorem 3.1 of the paper 10.2478/s11533-006-0017-6.

This function is noexcept and is guaranteed never to throw.

Parameters

n – the degree

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::rectangular_band(size_t m, size_t n)

A presentation for a rectangular band.

Returns a vector of relations giving a semigroup presentation defining the m by n rectangular band, as given in Proposition 4.2 of 10.1007/s002339910016.

Parameters
• m – the number of rows

• n – the number of columns

Throws
Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::stellar_monoid(size_t l)

A presentation for the stellar monoid.

Returns a vector of relations giving a semigroup presentation defining the stellar monoid with l generators, as in Theorem 4.39 of 10.48550/arXiv.1910.11740.

Parameters

l – the number of generators

Throws

LibsemigroupsException – if l < 2

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::chinese_monoid(size_t n)

A presentation for the Chinese monoid.

Returns a vector of relations giving a semigroup presentation defining the Chinese monoid, as described in 10.1142/S0218196701000425.

Parameters

n – the number of generators

Throws

LibsemigroupsException – if n < 2

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::monogenic_semigroup(size_t m, size_t r)

A presentation for a monogenic semigroup.

Returns a vector of relations giving a semigroup presentation defining the monogenic semigroup defined by the presentation $$\langle a \mid a^{m + r} = a^m \rangle$$.

Parameters
• m – the index

• r – the period

Throws

LibsemigroupsException – if r = 0

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::plactic_monoid(size_t n)

A presentation for the plactic monoid.

Returns a vector of relations giving a semigroup presentation defining the plactic monoid with n generators (see Section 3 of 10.1007/s00233-022-10285-3).

Parameters

n – the number of generators

Throws

LibsemigroupsException – if n < 2

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::stylic_monoid(size_t n)

A presentation for the stylic monoid.

Returns a vector of relations giving a semigroup presentation defining the stylic monoid with n generators (see Theorem 8.1 of 10.1007/s00233-022-10285-3).

Parameters

n – the number of generators

Throws

LibsemigroupsException – if n < 2

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::fibonacci_semigroup(size_t r, size_t n)

A presentation for a Fibonacci semigroup.

Returns a vector of relations giving a semigroup presentation defining the Fibonacci semigroup $$F(r, n)$$, as described in 10.1016/0022-4049(94)90005-1.

Parameters
• r – the length of the left hand sides of the relations

• n – the number of generators

Throws
Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::temperley_lieb_monoid(size_t n)

A presentation for the Temperley-Lieb monoid.

Returns a vector of relations giving a semigroup presentation defining the Temperley-Lieb monoid with n generators, as described in Theorem 2.2 of 10.1093/qmath/haab001.

Parameters

n – the number of generators

Throws

LibsemigroupsException – if n < 3

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::singular_brauer_monoid(size_t n)

A presentation for the singular part of the Brauer monoid.

Returns a vector of relations giving a semigroup presentation for the singular part of the Brauer monoid of degree n, as in Theorem 5 of 10.21136/MB.2007.134125).

Parameters

n – the degree

Throws

LibsemigroupsException – if n < 3

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::orientation_preserving_monoid(size_t n)

A presentation for the monoid of orientation preserving mappings.

Returns a vector of relations giving a semigroup presentation defining the monoid of orientation preserving mappings on a finite chain of order n, as described in 10.1007/s10012-000-0001-1.

Parameters

n – the order of the chain

Throws

LibsemigroupsException – if n < 3

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::orientation_reversing_monoid(size_t n)

A presentation for the monoid of orientation reversing mappings.

Returns a vector of relations giving a semigroup presentation defining the monoid of orientation reversing mappings on a finite chain of order n, as described in 10.1007/s10012-000-0001-1.

Parameters

n – the order of the chain

Throws

LibsemigroupsException – if n < 3

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::order_preserving_monoid(size_t n)

A presentation for the monoid of order-preserving mappings.

Returns a vector of relations giving a semigroup presentation defining the monoid of order-preserving transformations of degree n, as described in Section 2 of the paper 10.1007/s10012-000-0001-1.

This presentation has $$2n - 2$$ generators and $$n^2$$ relations.

Parameters
• n – the degree

• val – the author

Throws

LibsemigroupsException – if n < 3

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::cyclic_inverse_monoid(size_t n, author val = author::Fernandes, size_t index = 1)

A presentation for the cyclic inverse monoid.

Returns a vector of relations giving a monoid presentation defining the cyclic inverse monoid of degree n.

The combination of val and index determines the specific presentation which is returned. The options for these are:

The presentation with val = author::Fernandes and index = 0 has $$n + 1$$ generators and $$\frac{1}{2} \left(n^2 + 3n + 4\right)$$ relations.

The presentation with val = author::Fernandes and index = 1 has $$2$$ generators and $$\frac{1}{2}\left(n^2 - n + 6\right)$$ relations.

Parameters
• n – the degree

• val – the author

• index – the index

Throws
Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::order_preserving_cyclic_inverse_monoid(size_t n)

A presentation for the order-preserving part of the cyclic inverse monoid.

Returns a vector of relations giving a semigroup presentation defining the order-preserving part of the cyclic inverse monoid of degree n, as described in Theorem 2.17 of the paper 10.48550/arxiv.2211.02155.

Parameters

n – the degree

Throws

LibsemigroupsException – if n < 3

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::partial_isometries_cycle_graph_monoid(size_t n)

A presentation for the monoid of partial isometries of a cycle graph.

Returns a vector of relations giving a monoid presentation defining the monoid of partial isometries of an $$n$$-cycle graph, as described in Theorem 2.8 of 10.48550/arxiv.2205.02196.

Parameters

n – the number of vertices of the cycle graph

Throws

LibsemigroupsException – if n < 3

Returns

A std::vector<relation_type>

std::vector<relation_type> libsemigroups::fpsemigroup::not_symmetric_group(size_t n, author val = author::Guralnick + author::Kantor + author::Kassabov + author::Lubotzky)

A non-presentation for the symmetric group.

Returns a vector of relations giving a monoid presentation which is claimed to define the symmetric group of degree n, but does not. The argument val determines the specific presentation which is returned. The options are:

The default for val is the only option above.

Parameters
• n – the claimed degree of the symmetric group

• val – the author of the presentation

Throws
Returns

A std::vector<relation_type>