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
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: 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, ...
Returns the product of the list of elements inside
.
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
Bases: sage.categories.category.Category
The category of sub/quotient semi-groups.
Let and
be two semi-groups and
and
be two maps such that:
is the identity of
.
- for any two
the identity
holds.
The category SubQuotient implements the product from
and
and the product of
.
is supposed to belongs the category
Semigroups().SubQuotients() and to specify
under the name
S.ambient() and to implement
and
under the names S.lift(x) and S.retract(y).
Returns an example of sub quotient of a semigroup
EXAMPLES:
sage: Semigroups().SubQuotients().example()
An example of a subquotient semigroup: a subquotient of the left zero semigroup
EXAMPLES:
sage: Semigroups().SubQuotients().super_categories()
[Category of semigroups]
An example of a semigroup.
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')
EXAMPLES:
sage: Semigroups().super_categories()
[Category of magmas]