Schützenberger graph
Let $(X;T)$ be a presentation^{} for the inverse^{} monoid ${\mathrm{Inv}}^{1}\u27e8X|T\u27e9$ [resp. inverse semigroup $\mathrm{Inv}\u27e8X|T\u27e9$]. 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}\u27e8X|T\u27e9$, 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}\mathrm{\Gamma}(X;T;m)$ with vertex and edge set respectively
$$\mathrm{V}(\mathcal{S}\mathrm{\Gamma}(X;T;m))=\{v\in {\mathrm{Inv}}^{1}\u27e8X|T\u27e9|{[v]}_{\mathcal{R}}={[m]}_{\mathcal{R}}\},$$ |
$$\mathrm{E}(\mathcal{S}\mathrm{\Gamma}(X;T;m))=\{({v}_{1},x,{v}_{2})|{v}_{1},{v}_{2}\in \mathrm{V}(\mathcal{S}\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}\u27e8X|T\u27e9$ with ${[m]}_{\mathcal{R}}={[n]}_{\mathcal{R}}$ we have $\mathcal{S}\mathrm{\Gamma}(X;T;m)=\mathcal{S}\mathrm{\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}\u27e8X|T\u27e9$ happen to be a group (with identity ${1}_{G}$), then the Schützenberger graph $\mathcal{S}\mathrm{\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 |