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
Canonical name	SchutzenbergerGraph
Date of creation	2013-03-22 16:10:50
Last modified on	2013-03-22 16:10:50
Owner	Mazzu (14365)
Last modified by	Mazzu (14365)
Numerical id	34
Author	Mazzu (14365)
Entry type	Definition
Classification	msc 20M05
Classification	msc 20M18
Related topic	MunnTree
Defines	Schützenberger graph
Defines	left Schützenberger graph
Defines	right Schützenberger graph