Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Bib Ind

### 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
 ‣ 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(\textit{E})$$ where, roughly speaking, elements correspond to paths in the graph E.

Let us describe E as a digraph $$\textit{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 \to E^0$$ giving the range and source of an edge, respectively. The graph inverse semigroup $$G(\textit{E})$$ of $$E$$ is the semigroup-with-zero generated by the sets $$\textit{E} ^ 0$$ and $$\textit{E} ^ 1$$, together with a set of variables $$\{e ^ {-1} \mid e \in \textit{E} ^ 1\}$$, satisfying the following relations for all $$v, w \in \textit{E} ^ 0$$ and $$e, f \in \textit{E} ^ 1$$:

(V)

$$vw = \delta_{v,w} \cdot v$$,

(E1)

$$s(e) \cdot e=e \cdot r(e)=e$$,

(E2)

$$r(e) \cdot e^{-1} = e^{-1} \cdot s(e) =e^{-1}$$,

(CK1)

$$e^{-1} \cdot f = \delta_{e,f} \cdot r(e)$$.

(Here $$\delta$$ is the Kronecker delta.) We define $$v^{-1}=v$$ for each $$v \in E^0$$, and for any path $$y=e_1\dots e_n$$ ($$e_1\dots e_n \in 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], ,
>                   [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
 ‣ Range( x ) ( attribute )
 ‣ Source( x ) ( attribute )

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([[], , ]);;
gap> S := GraphInverseSemigroup(gr);;
gap> e := S.1;
e_1
gap> Source(e);
v_2
gap> Range(e);
v_1


##### 11.1-3 IsVertex
 ‣ IsVertex( x ) ( operation )

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([[], , ]);;
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
 ‣ IsGraphInverseSemigroup( x ) ( filter )
 ‣ IsGraphInverseSemigroupElement( x ) ( filter )

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([[], , ]);;
gap> S := GraphInverseSemigroup(gr);
<infinite graph inverse semigroup with 3 vertices, 2 edges>
gap> IsGraphInverseSemigroup(S);
true
gap> x := GeneratorsOfSemigroup(S);
e_1
gap> IsGraphInverseSemigroupElement(x);
true


##### 11.1-5 GraphOfGraphInverseSemigroup
 ‣ GraphOfGraphInverseSemigroup( S ) ( attribute )

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([[], , ]);
<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
 ‣ IsGraphInverseSemigroupElementCollection ( category )

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

IsGraphInverseSubsemigroup is a synonym for IsSemigroup and IsInverseSemigroup and IsGraphInverseSemigroupElementCollection.

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

gap> gr := Digraph([[], , ]);
<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
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Bib Ind

generated by GAPDoc2HTML