Schützenberger graph

Let $(X;T)$ be a presentation for the inverse monoid ${\mathrm{Inv}}^1⟨X|T⟩$ [resp. inverse semigroup $\mathrm{Inv}⟨X|T⟩$]. In what follows, the argument for inverse semigroups and inverse monoids is exactly the same, so we concentrate on the last one.

Given $m\in {\mathrm{Inv}}^1⟨X|T⟩$, let ${[m]}_{ℛ}$ be the equivalence class of $m$ with respect to the Right Green relation $ℛ$. The Right Schützenberger graph of ${[m]}_{ℛ}$ with respect to the presentation $(X;T)$ is defined as the $X$-inverse word graph $𝒮\mathrm{\Gamma }(X;T;m)$ with vertex and edge set respectively

$$\mathrm{V}(𝒮\mathrm{\Gamma }(X;T;m))=\{v\in {\mathrm{Inv}}^1⟨X|T⟩|{[v]}_{ℛ}={[m]}_{ℛ}\},$$

$$\mathrm{E}(𝒮\mathrm{\Gamma }(X;T;m))=\{(v_1,x,v_2)|v_1,v_2\in \mathrm{V}(𝒮\mathrm{\Gamma }(X;T;m)),x\in \left(X\coprod X^{-1}\right),v_2=v_1\cdot {[x]}_{\tau }\},$$

where $\tau ={(T\cup {\rho }_X)}^{\mathrm{c}}$, i.e. $\tau$ is the congruence generated by $T$ and the Wagner congruence ${\rho }_X$, and ${[x]}_{\tau }$ is the congruence class of the letter $x\in \left(X\coprod X^{-1}\right)$ with respect to the congruence $\tau$.

This is a good definition, in fact it can be easily shown that given $m,n\in {\mathrm{Inv}}^1⟨X|T⟩$ with ${[m]}_{ℛ}={[n]}_{ℛ}$ we have $𝒮\mathrm{\Gamma }(X;T;m)=𝒮\mathrm{\Gamma }(X;T;n)$.

Analogously we can define the Left Schützenberger graph using the Left Green relation $ℒ$ instead of the Right Green relation $ℛ$, but this notion is not used in literature.

Schützenberger graphs play in combinatorial inverse semigroups theory the role that Cayley graphs play in combinatorial group theory. In fact, if $G={\mathrm{Inv}}^1⟨X|T⟩$ happen to be a group (with identity $1_G$), then the Schützenberger graph $𝒮\mathrm{\Gamma }(X;T;1_G)$ of its unique $ℛ$-class is exactly the Cayley graph of the group $G$.