Semigroups

class sage.categories.semigroups.Semigroups(s=None)

Bases: sage.categories.category.Category

The category of (multiplicative) semigroups, i.e. sets with an associative operation *.

EXAMPLES:

sage: Semigroups()
Category of semigroups
sage: Semigroups().super_categories()
[Category of magmas]
sage: Semigroups().all_super_categories()
[Category of semigroups, Category of magmas, Category of sets, Category of sets with partial maps, Category of objects]

TESTS:

sage: C = Semigroups()
sage: TestSuite(C).run(verbose=True)
running ._test_category() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . pass

class Algebras(base_category, base_ring)

Bases: sage.categories.algebra_functor.AlgebrasCategory

ParentMethods

alias of Algebras.ParentMethods

extra_super_categories()

EXAMPLES:

sage: Semigroups().Algebras(QQ).extra_super_categories()
[Category of algebras with basis over Rational Field]
sage: Semigroups().Algebras(QQ).super_categories()
[Category of algebras with basis over Rational Field, Category of set algebras over Rational Field]

sage: Semigroups().example().algebra(ZZ).categories()
[Category of semigroup algebras over Integer Ring,
 Category of algebras with basis over Integer Ring,
 ...
 Category of objects]

FIXME: that should be non unital algebras!

class Semigroups.CartesianProducts(category, *args)

Bases: sage.categories.cartesian_product.CartesianProductsCategory

extra_super_categories()

EXAMPLES:

sage: Semigroups().CartesianProducts().extra_super_categories()
[Category of semigroups]
sage: Semigroups().CartesianProducts().super_categories()
[Category of semigroups, Category of Cartesian products of magmas]

class Semigroups.ElementMethods

class Semigroups.ParentMethods

cayley_graph(side='right', simple=False, elements=None, generators=None, connecting_set=None)

Returns the Cayley graph for this finite semigroup.

INPUT:

- ``side`` -- "left", "right", or "twosided":
  the side on which the generators act (default:"right")
- ``simple`` -- boolean (default:False):
  if True, returns a simple graph (no loops, no labels,
  no multiple edges)
- ``generators`` -- a list, tuple, or family of elements of ``self``
  (default: ``self.semigroup_generators()``)
- ``connecting_set`` -- alias for ``generators``; deprecated
- ``elements`` -- a list (or iterable) of elements of ``self``

OUTPUT:

- :class:`DiGraph`

EXAMPLES:

We start with the (right) Cayley graphs of some classical groups:

sage: D4 = DihedralGroup(4); D4
Dihedral group of order 8 as a permutation group
sage: G = D4.cayley_graph()
sage: show(G, color_by_label=True, edge_labels=True)
sage: A5 = AlternatingGroup(5); A5
Alternating group of order 5!/2 as a permutation group
sage: G = A5.cayley_graph()
sage: G.show3d(color_by_label=True, edge_size=0.01, edge_size2=0.02, vertex_size=0.03)
sage: G.show3d(vertex_size=0.03, edge_size=0.01, edge_size2=0.02, vertex_colors={(1,1,1):G.vertices()}, bgcolor=(0,0,0), color_by_label=True, xres=700, yres=700, iterations=200) # long time (less than a minute)
sage: G.num_edges()
120

sage: w = WeylGroup(['A',3])
sage: d = w.cayley_graph(); d
Digraph on 24 vertices
sage: d.show3d(color_by_label=True, edge_size=0.01, vertex_size=0.03)

Alternative generators may be specified:

sage: G = A5.cayley_graph(generators=[A5.gens()[0]])
sage: G.num_edges()
60
sage: g=PermutationGroup([(i+1,j+1) for i in range(5) for j in range(5) if j!=i])
sage: g.cayley_graph(generators=[(1,2),(2,3)])
Digraph on 120 vertices

If elements is specified, then only the subgraph induced and those elements is returned. Here we use it to display the Cayley graph of the free monoid truncated on the elements of length at most 3:

sage: M = Monoids().example(); M
An example of a monoid: the free monoid generated by ('a', 'b', 'c', 'd')
sage: elements = [ M.prod(w) for w in sum((list(Words(M.semigroup_generators(),k)) for k in range(4)),[]) ]
sage: G = M.cayley_graph(elements = elements)
sage: G.num_verts(), G.num_edges()
(85, 84)
sage: G.show3d(color_by_label=True, edge_size=0.001, vertex_size=0.01)

We now illustrate the side and simple options on a semigroup:

sage: S = FiniteSemigroups().example(alphabet=('a','b'))
sage: g = S.cayley_graph(simple=True)
sage: g.vertices()
['a', 'ab', 'b', 'ba']
sage: g.edges()
[('a', 'ab', None), ('b', 'ba', None)]

sage: g = S.cayley_graph(side="left", simple=True)
sage: g.vertices()
['a', 'ab', 'b', 'ba']
sage: g.edges()
[('a', 'ba', None), ('ab', 'ba', None), ('b', 'ab', None),
('ba', 'ab', None)]

sage: g = S.cayley_graph(side="twosided", simple=True)
sage: g.vertices()
['a', 'ab', 'b', 'ba']
sage: g.edges()
[('a', 'ab', None), ('a', 'ba', None), ('ab', 'ba', None),
('b', 'ab', None), ('b', 'ba', None), ('ba', 'ab', None)]

sage: g = S.cayley_graph(side="twosided")
sage: g.vertices()
['a', 'ab', 'b', 'ba']
sage: g.edges()
[('a', 'a', (0, 'left')), ('a', 'a', (0, 'right')), ('a', 'ab', (1, 'right')), ('a', 'ba', (1, 'left')), ('ab', 'ab', (0, 'left')), ('ab', 'ab', (0, 'right')), ('ab', 'ab', (1, 'right')), ('ab', 'ba', (1, 'left')), ('b', 'ab', (0, 'left')), ('b', 'b', (1, 'left')), ('b', 'b', (1, 'right')), ('b', 'ba', (0, 'right')), ('ba', 'ab', (0, 'left')), ('ba', 'ba', (0, 'right')), ('ba', 'ba', (1, 'left')), ('ba', 'ba', (1, 'right'))]

sage: s1 = SymmetricGroup(1); s = s1.cayley_graph(); s.vertices()
[()]

TODO:

• Add more options for constructing subgraphs of the Cayley graph, handling the standard use cases when exploring large/infinite semigroups (a predicate, generators of an ideal, a maximal length in term of the generators)
• Specify good default layout/plot/latex options in the graph
• Generalize to combinatorial modules with module generators / operators

AUTHORS:

• Bobby Moretti (2007-08-10)
• Robert Miller (2008-05-01): editing
• Nicolas M. Thiery (2008-12): extension to semigroups, side, simple, and elements options, ...

prod(args)

Returns the product of the list of elements args inside self.

EXAMPLES:

sage: S = Semigroups().example("free")
sage: S.prod([S('a'), S('b'), S('c')])
'abc'
sage: S.prod([])
...
AssertionError: Cannot compute an empty product in a semigroup

class Semigroups.Quotients(category, *args)

Bases: sage.categories.quotients.QuotientsCategory

ParentMethods

alias of Quotients.ParentMethods

example()

Returns an example of quotient of a semigroup, as per Category.example().

EXAMPLES:

sage: Semigroups().Quotients().example()
An example of a (sub)quotient semigroup: a quotient of the left zero semigroup

class Semigroups.Subquotients(category, *args)

Bases: sage.categories.subquotients.SubquotientsCategory

The category of sub/quotient semi-groups.

EXAMPLES:

sage: Semigroups().Subquotients().all_super_categories()
[Category of subquotients of semigroups,
 Category of semigroups,
 Category of subquotients of magmas,
 Category of magmas,
 Category of subquotients of sets,
 Category of sets,
 Category of sets with partial maps,
 Category of objects]

example()

Returns an example of sub quotient of a semigroup, as per Category.example().

EXAMPLES:

sage: Semigroups().Subquotients().example()
An example of a (sub)quotient semigroup: a quotient of the left zero semigroup

Semigroups.example(choice='leftzero', **kwds)

Returns an example of a semigroup, as per Category.example().

INPUT:

- ``choice`` -- str [default: 'leftzero']. Can be either 'leftzero'
  for the left zero semigroup, or 'free' for the free semigroup.
- ``**kwds`` -- keyword arguments passed onto the constructor for the
  chosen semigroup.

EXAMPLES:

sage: Semigroups().example(choice='leftzero')
An example of a semigroup: the left zero semigroup
sage: Semigroups().example(choice='free')
An example of a semigroup: the free semigroup generated by ('a', 'b', 'c', 'd')
sage: Semigroups().example(choice='free', alphabet=('a','b'))
An example of a semigroup: the free semigroup generated by ('a', 'b')

Semigroups.super_categories(*args, **kwds)

EXAMPLES:

sage: Semigroups().super_categories()
[Category of magmas]