2022/08/05 by K. Auinger, Auinger, K., J. Bitterlich +3 · 1 citation
Computer Science · Mathematics · #semigroups and automata theory #Geometric and Algebraic Topology #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2208.03273
For a finite connected graph E with set of edges E, a finite E-generated group G is constructed such that the set of relations p=1 satisfied by G (with p a word over E∪ E-1) is closed under deletion of generators (i.e.~edges). As a consequence, every element g∈ G admits a unique minimal set C(g) of edges (the content of g) needed to represent g as a word over C(g)\cupC(g)-1. The crucial property of the group G is that connectivity in the graph E is encoded in G in the following sense: if a word p forms a path u\longrightarrow v in E then there exists a G-equivalent word q which also forms a path u\longrightarrow v and uses only edges from their content; in particular, the content of the corresponding group element [p]G=[q]G spans a connected subgraph of E containing the vertices u and v. As the free group generated by E obviously has these properties, the construction provides another instance of how certain features of free groups can be ``approximated'' or ``simulated'' in finite groups. As an application it is shown that every finite inverse monoid admits a finite F-inverse cover. This solves a long-standing problem of Henckell and Rhodes.