# Schützenberger graph

Let $(X;T)$ be a presentation for the inverse monoid $\mathrm{Inv}^{1}\left\langle X|T\right\rangle$ [resp. inverse semigroup $\mathrm{Inv}\left\langle X|T\right\rangle$]. 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}\left\langle X|T\right\rangle$, let $[m]_{\mathcal{R}}$ be the equivalence class of $m$ with respect to the Right Green relation $\mathcal{R}$. The Right Schützenberger graph of $[m]_{\mathcal{R}}$ with respect to the presentation $(X;T)$ is defined as the $X$-inverse word graph $\mathcal{S}\Gamma(X;T;m)$ with vertex and edge set respectively

 $\mathrm{V}(\mathcal{S}\Gamma(X;T;m))=\left\{v\in\mathrm{Inv}^{1}\left\langle X% |T\right\rangle\,|\,[v]_{\mathcal{R}}=[m]_{\mathcal{R}}\right\},$
 $\mathrm{E}(\mathcal{S}\Gamma(X;T;m))=\left\{(v_{1},x,v_{2})\,|\,v_{1},v_{2}\in% \mathrm{V}(\mathcal{S}\Gamma(X;T;m)),\ x\in\left(X\amalg X^{-1}\right),\ v_{2}% =v_{1}\cdot[x]_{\tau}\right\},$

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\amalg 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}\left\langle X|T\right\rangle$ with $[m]_{\mathcal{R}}=[n]_{\mathcal{R}}$ we have $\mathcal{S}\Gamma(X;T;m)=\mathcal{S}\Gamma(X;T;n)$.

Analogously we can define the Left Schützenberger graph using the Left Green relation $\mathcal{L}$ instead of the Right Green relation $\mathcal{R}$, 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}\left\langle X|T\right\rangle$ happen to be a group (with identity $1_{G}$), then the Schützenberger graph $\mathcal{S}\Gamma{(X;T;1_{G})}$ of its unique $\mathcal{R}$-class is exactly the Cayley graph of the group $G$.

## References

• 1 N. Petrich, Inverse Semigroups, Wiley, New York, 1984.
• 2 J.B. Stephen, Presentation of inverse monoids, J. Pure Appl. Algebra 63 (1990) 81-112.
Title Schützenberger graph SchutzenbergerGraph 2013-03-22 16:10:50 2013-03-22 16:10:50 Mazzu (14365) Mazzu (14365) 34 Mazzu (14365) Definition msc 20M05 msc 20M18 MunnTree Schützenberger graph left Schützenberger graph right Schützenberger graph