[MathJax on]

11 Graph inverse semigroups

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

The functionality in Semigroups for graph inverse semigroups was written jointly by Zak Mesyan (UCCS) and J. D. Mitchell (St Andrews).

11.1 Creating graph inverse semigroups

11.1-1 GraphInverseSemigroup

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.

Let us describe E as a digraph E = (E ^ 0, E ^ 1, r, s), where E^0 is the set of vertices, E^1 is the set of edges, and r and s are functions E^1 -> E^0 giving the range and source of an edge, respectively. 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)

r(e) ⋅ e^-1 = e^-1 ⋅ s(e) =e^-1,

(CK1)

e^-1 ⋅ f = δ_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.

For a more complete description, see [MM16].

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]]);
<immutable 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

11.1-2 Range

Returns: A graph inverse semigroup element.

If x is an element of a graph inverse semigroup (i.e. it satisfies IsGraphInverseSemigroupElement (11.1-4)), then Range and Source give, respectively, the start and end vertices of x when viewed as a path in the digraph over which the semigroup is defined.

For a fuller description, see GraphInverseSemigroup (11.1-1).

gap> gr := Digraph([[], [1], [3]]);;
gap> S := GraphInverseSemigroup(gr);;
gap> e := S.1;
e_1
gap> Source(e);
v_2
gap> Range(e);
v_1

11.1-3 IsVertex

Returns: true or false.

If x is an element of a graph inverse semigroup (i.e. it satisfies IsGraphInverseSemigroupElement (11.1-4)), then this attribute returns true if x corresponds to a vertex in the digraph over which the semigroup is defined, and false otherwise.

For a fuller description, see GraphInverseSemigroup (11.1-1).

gap> gr := Digraph([[], [1], [3]]);;
gap> S := GraphInverseSemigroup(gr);;
gap> e := S.1;
e_1
gap> IsVertex(e);
false
gap> v := S.3;
v_1
gap> IsVertex(v);
true
gap> z := v * e;
0
gap> IsVertex(z);
false

11.1-4 IsGraphInverseSemigroup

Returns: true or false.

The category IsGraphInverseSemigroup contains any semigroup defined over a digraph using the GraphInverseSemigroup (11.1-1) operation. The category IsGraphInverseSemigroupElement contains any element contained in such a semigroup.

gap> gr := Digraph([[], [1], [3]]);;
gap> S := GraphInverseSemigroup(gr);
<infinite graph inverse semigroup with 3 vertices, 2 edges>
gap> IsGraphInverseSemigroup(S);
true
gap> x := GeneratorsOfSemigroup(S)[1];
e_1
gap> IsGraphInverseSemigroupElement(x);
true

11.1-5 GraphOfGraphInverseSemigroup

Returns: A digraph.

If S is a graph inverse semigroup (i.e. it satisfies IsGraphInverseSemigroup (11.1-4)), then this attribute returns the original digraph over which S was defined (most likely the argument given to GraphInverseSemigroup (11.1-1) to create S).

gap> gr := Digraph([[], [1], [3]]);
<immutable digraph with 3 vertices, 2 edges>
gap> S := GraphInverseSemigroup(gr);;
gap> GraphOfGraphInverseSemigroup(S);
<immutable digraph with 3 vertices, 2 edges>

11.1-6 IsGraphInverseSemigroupElementCollection

Every collection of elements of a graph inverse semigroup belongs to the category IsGraphInverseSemigroupElementCollection. For example, every graph inverse semigroup belongs to IsGraphInverseSemigroupElementCollection.

11.1-7 IsGraphInverseSubsemigroup

IsGraphInverseSubsemigroup is a synonym for IsSemigroup and IsInverseSemigroup and IsGraphInverseSemigroupElementCollection.

See IsGraphInverseSemigroupElementCollection (11.1-6) and IsInverseSemigroup (Reference: IsInverseSemigroup).

gap> gr := Digraph([[], [1], [2]]);
<immutable digraph with 3 vertices, 2 edges>
gap> S := GraphInverseSemigroup(gr);
<finite graph inverse semigroup with 3 vertices, 2 edges>
gap> Elements(S);
[ e_2^-1, e_1^-1, e_1^-1e_2^-1, 0, e_1, e_1e_1^-1, e_1e_1^-1e_2^-1, 
  e_2, e_2e_2^-1, e_2e_1, e_2e_1e_1^-1, e_2e_1e_1^-1e_2^-1, v_1, v_2, 
  v_3 ]
gap> T := InverseSemigroup(Elements(S){[3, 5]});;
gap> IsGraphInverseSubsemigroup(T);
true

generated by GAPDoc2HTML