Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

13 Graph inverse semigroups
 13.1 Creating graph inverse semigroups

13 Graph inverse semigroups

In this chapter we describe a class of semigroups arising from directed graphs.

13.1 Creating graph inverse semigroups

13.1-1 GraphInverseSemigroup
‣ GraphInverseSemigroup( E )( operation )

Returns: A graph inverse semigroup.

If E is a digraph (i.e. it satisfies IsDigraph (Digraphs: IsDigraph)) then GraphInverseSemigroup returns the graph inverse semigroup G(E) where, roughly speaking, elements correspond to paths in the graph E.

Given a digraph E = (E ^ 0, E ^ 1, r, s) the graph inverse semigroup G(E) of E is the semigroup with zero generated by the sets E ^ 0 and E ^ 1, together with a set of variables {e ^ -1 ∣ e∈ E ^ 1}, satisfying the following relations for all v, w∈ E ^ 0 and e, f∈ E ^ 1:

(V)

vw = δ_v,w⋅ v,

(E1)

s(e)⋅ e=e⋅ r(e)=e,

(E2)

s(e)⋅ e = e⋅ r(e) =e,

(CK1)

e^-1f=δ_e,f⋅ r(e).

(Here δ is the Kronecker delta.) We define v^-1=v for each v ∈ E^0, and for any path y=e_1dots e_n (e_1dots e_n ∈ E^1) we let y^-1 = e_n^-1 dots e_1^-1. With this notation, every nonzero element of G(E) can be written uniquely as xy^-1 for some paths x, y in E, by the CK1 relation.

gap> gr := Digraph([[2, 5, 8, 10], [2, 3, 4, 5, 6, 8, 9, 10], [1], 
>                   [3, 5, 7, 8, 10], [2, 5, 7], [3, 6, 7, 9, 10], 
>                   [1, 4], [1, 5, 9], [1, 2, 7, 8], [3, 5]]);
<digraph with 10 vertices, 37 edges>
gap> S := GraphInverseSemigroup(gr);
<infinite graph inverse semigroup with 10 vertices, 37 edges>
gap> GeneratorsOfInverseSemigroup(S);
[ e_1, e_2, e_3, e_4, e_5, e_6, e_7, e_8, e_9, e_10, e_11, e_12, 
  e_13, e_14, e_15, e_16, e_17, e_18, e_19, e_20, e_21, e_22, e_23, 
  e_24, e_25, e_26, e_27, e_28, e_29, e_30, e_31, e_32, e_33, e_34, 
  e_35, e_36, e_37, v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8, v_9, v_10 
 ]
gap> AssignGeneratorVariables(S);
gap> e_1 * e_1 ^ -1;
e_1e_1^-1
gap> e_1 ^ -1 * e_1 ^ -1;
0
gap> e_1 ^ -1 * e_1;
v_2

13.1-2 Range
‣ Range( x )( attribute )
‣ Source( x )( attribute )

13.1-3 IsVertex
‣ IsVertex( x )( attribute )

13.1-4 IsGraphInverseSemigroup
‣ IsGraphInverseSemigroup( x )( filter )
‣ IsGraphInverseSemigroupElement( x )( filter )

13.1-5 GraphOfGraphInverseSemigroup
‣ GraphOfGraphInverseSemigroup( x )( filter )
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Bib Ind

generated by GAPDoc2HTML