The structure of a graph inverse semigroup

DOI10.1007/S00233-016-9793-XMaRDI QIDQ305770zbMATH OpenOpenAlexFDO

Publication date 30 August 2016

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.4380

directed graph graph inverse semigroup inverse semigroup semigroup congruence

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) General structure theory for semigroups (20M10) Inverse semigroups (20M18)

Abstract: Given any directed graph E one can construct a graph inverse semigroup G(E), where, roughly speaking, elements correspond to paths in the graph. In this paper we study the semigroup-theoretic structure of G(E). Specifically, we describe the non-Rees congruences on G(E), show that the quotient of G(E) by any Rees congruence is another graph inverse semigroup, and classify the G(E) that have only Rees congruences. We also find the minimum possible degree of a faithful representation by partial transformations of any countable G(E), and we show that a homomorphism of directed graphs can be extended to a homomorphism (that preserves zero) of the corresponding graph inverse semigroups if and only if it is injective.

Review text

Let \(E = ({E^0},{E^1},{\operatorname{r}},{\operatorname{s}})\) be a directed graph with the set of vertices \({E^0}\), the set of edges \({E^1}\) and the edge's source and range functions \({\operatorname{s}},{\operatorname{r}}:{E^1} \to {E^0}\). The graph inverse semigroup \(G(E)\) of \(E\) is the semigroup generated by the set \({E^0} \cup {E^1} \cup \{ {e^{ - 1}}\mid e \in {E^1}\} \) satisfying, for all \(v,w \in {E^0}\) and \(e,f \in {E^1}\), the identities (\(\delta \) is the Kronecker symbol): \(vw = {\delta _{v,w}}v\); \({\operatorname{s}}(e)e = e{\operatorname{r}}(e) = e\); \({\operatorname{r}}(e){e^{ - 1}} = {e^{ - 1}}{\operatorname{s}}(e) = {e^{ - 1}}\); \({e^{ - 1}}f = {\delta _{e,f}}{\operatorname{r}}(e)\). Here, congruences and corresponding images of graph inverse semigroups are investigated. The authors describe non-Rees congruences on \(G(E)\), show that quotient of a Rees congruence is another graph inverse semigroup and show that a homomorphism of directed graphs can be extended to a homomorphism of corresponding graph inverse semigroups preserving zero iff it is injective. From this, it follows that the automorphism group of a graph is isomorphic to the automorphism group of the graph's inverse semigroup and that every group is isomorphic to the automorphism group of some graph inversive semigroup.

Recommendations

Cites work

Cited in

(34)

Describes a project that uses

Uses Software

This page was built for publication: The structure of a graph inverse semigroup

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q305770)