Free inverse monoids and graph immersions. (English) Zbl 0798.20056

The aim of this paper is to study inverse monoids, in particular free inverse monoids, by means of analogues of the graphical techniques of combinatorial group theory. It is shown that there is a relationship between immersions of graphs and closed submonoids of free inverse monoids similar to that between coverings of graphs and subgroups of free groups. Before going into details some preparation is required. Graphs, in this context, [the context of J. P. Serre: ‘Trees’ (1980; Zbl 0369.20013)] come equipped with ‘inverse’ edges: for every edge \(e: a \to b\) there is an edge \(e^{-1}: b\to a\) distinct from \(e\), in such a way that \((e^{-1})^{-1} = e\). A morphism \(f: \Delta \to \Gamma\) of graphs is a covering if for each vertex \(v\) of \(\Delta\), when restricted to the set of edges emanating from \(v\), \(f\) is a bijection onto the set of edges emanating from \(vf\); it is an immersion if it is an injection when so restricted. When the graphs are connected, then for any vertex \(v\) of \(\Delta\), such a covering induces an embedding of the fundamental group of \(\Delta\) at \(v\) into that of \(\Gamma\) at \(vf\). Conversely, any subgroup of the latter group is determined in such a way. Moreover, equivalent covers correspond to conjugate subgroups. Specializing to the ‘bouquet of circles on \(X\)’, that is, the graph with one vertex and a loop for each element of the set \(X\), its connected coverings are classified by the subgroups of the free group on \(X\).
The first main theorem of this paper states that there is a natural equivalence between the category of connected immersions over the bouquet of circles on \(X\) and the category of transitive representations (by partial one-one mappings) of the free inverse monoid \(FIM(X)\) on \(X\). By Schein’s theorem, the latter are coded by the closed inverse submonoids of \(FIM(X)\) (those inverse submonoids \(U\) with the property that \(u \in U\) and \(v \geq u\) implies \(v \in U\)). The second main theorem is that the closed inverse submonoids of \(FIM(X)\) are themselves codes by the free actions of (free) groups on trees: for each such action of a group \(G\) on a tree \(T\), and designated vertex \(v\) of \(T\), an inverse monoid \(M(T,G,v)\) is constructed as a set of ordered pairs, the first co- ordinate being a finite subtree of \(T\), the second an element of \(G\). (In particular, when \(G\) is the free group on \(X\) and \(T\) is its Cayley graph, this monoid is essentially Munn’s construction of the free inverse monoid). The monoids so constructed are the closed inverse submonoids of \(FIM(X)\), up to isomorphism. A remarkable consequence is that for each such submonoid there is an idempotent-pure retraction onto \(FIM(Y)\), for some set \(Y\). The third major theorem draws tighter the connection between connected immersions over the bouquet of circles on \(X\) and the closed inverse submonoids of \(FIM(X)\), in terms of ‘conjugacy’, by considering the free inverse category over a connected graph. More generally, the same ideas are used to classify the connected immersions over any connected graph.
Yet another line of approach is to associate with each closed inverse submonoid \(N\) of \(FIM(X)\) an inverse automaton, whose states are the ‘cosets’ of \(N\). (This automaton arises naturally from the representation induced by \(N\).) A number of conditions are found equivalent to finiteness of the automaton; for instance, that \(N\) be finitely generated; or that \(N\) be a rational subset of \(FIM(X)\). In the final section this idea is applied to combinatorial group theory. With any subgroup \(H\) of the free group on \(X\) there are successively associated a closed inverse subsemigroup of \(FIM(X)\), whence an immersion, an automaton and, eventually, an inverse monoid \(\text{Synt}(H)\), the syntactic monoid of the automaton. This monoid is finite if and only if \(H\) is finitely generated. Further papers make more use of this association, but a sample application is that \(H\) has finite index if and only if \(\text{Synt}(H)\) is a group (and if and only if the corresponding closed inverse submonoid of \(FIM(X)\) is full).


20M18 Inverse semigroups
20E08 Groups acting on trees
20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.
20E05 Free nonabelian groups


Zbl 0369.20013
Full Text: DOI