Semigroups

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

Bases: sage.categories.category_singleton.Category_singleton

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_category_graph() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . pass
class Algebras(base_category, base_ring)

Bases: sage.categories.algebra_functor.AlgebrasCategory

EXAMPLES:

sage: C = Semigroups().Algebras(QQ)
sage: C
Category of semigroup algebras over Rational Field
sage: C.base_category()
Category of semigroups
sage: C.super_categories()
[Category of algebras with basis over Rational Field, Category of set algebras over Rational Field]

TESTS:

sage: C._short_name()
'Algebras'
sage: latex(C) # todo: improve that
\mathbf{Algebras}(\mathbf{Semigroups})
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

TESTS:

sage: from sage.categories.covariant_functorial_construction import CovariantConstructionCategory
sage: class FooBars(CovariantConstructionCategory):
...       _functor_category = "FooBars"
sage: Category.FooBars = lambda self: FooBars.category_of(self)
sage: C = FooBars(ModulesWithBasis(ZZ))
sage: C
Category of foo bars of modules with basis over Integer Ring
sage: C.base_category()
Category of modules with basis over Integer Ring
sage: latex(C)
\mathbf{FooBars}(\mathbf{ModulesWithBasis}_{\Bold{Z}})
sage: import __main__; __main__.FooBars = FooBars # Fake FooBars being defined in a python module
sage: TestSuite(C).run()
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()
[()]

TESTS:

sage: SymmetricGroup(2).cayley_graph(side="both")
Traceback (most recent call last):
...
ValueError: option 'side' must be 'left', 'right' or 'twosided'

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([])
Traceback (most recent call last):
...
AssertionError: Cannot compute an empty product in a semigroup
class Semigroups.Quotients(category, *args)

Bases: sage.categories.quotients.QuotientsCategory

TESTS:

sage: from sage.categories.covariant_functorial_construction import CovariantConstructionCategory
sage: class FooBars(CovariantConstructionCategory):
...       _functor_category = "FooBars"
sage: Category.FooBars = lambda self: FooBars.category_of(self)
sage: C = FooBars(ModulesWithBasis(ZZ))
sage: C
Category of foo bars of modules with basis over Integer Ring
sage: C.base_category()
Category of modules with basis over Integer Ring
sage: latex(C)
\mathbf{FooBars}(\mathbf{ModulesWithBasis}_{\Bold{Z}})
sage: import __main__; __main__.FooBars = FooBars # Fake FooBars being defined in a python module
sage: TestSuite(C).run()
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]

[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()

EXAMPLES:

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

Previous topic

Schemes

Next topic

Semirings

This Page