Schützenberger graph

Let (X;T) be a presentationMathworldPlanetmathPlanetmathPlanetmath for the inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath monoid Inv1X|T [resp. inverse semigroup InvX|T]. In what follows, the argument for inverse semigroups and inverse monoids is exactly the same, so we concentrate on the last one.

Given mInv1X|T, let [m] be the equivalence classMathworldPlanetmathPlanetmath 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 𝒮Γ(X;T;m) with vertex and edge set respectively


where τ=(TρX)c, i.e. τ is the congruence generated by T and the Wagner congruence ρX, and [x]τ is the congruence class of the letter x(XX-1) with respect to the congruencePlanetmathPlanetmathPlanetmath τ.

This is a good definition, in fact it can be easily shown that given m,nInv1X|T with [m]=[n] we have 𝒮Γ(X;T;m)=𝒮Γ(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 graphsMathworldPlanetmath play in combinatorial group theory. In fact, if G=Inv1X|T happen to be a group (with identity 1G), then the Schützenberger graph 𝒮Γ(X;T;1G) of its unique -class is exactly the Cayley graph of the group G.


  • 1 N. Petrich, Inverse Semigroups, Wiley, New York, 1984.
  • 2 J.B. Stephen, Presentation of inverse monoids, J. Pure Appl. AlgebraMathworldPlanetmathPlanetmathPlanetmath 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