Diagram Groups

V. Guba, M. Sapir

IBP-Litp 1995/22: Rapport de Recherche Litp / Litp research reports
119 pages - Mai/May 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Diagram Groups

Résumé : Un groupe de diagrammes consiste en un ensemble de diagrammes de semigroupes sphériques, c'est-à-dire de graphes étiquetés d'un type particulier. Les diagrammes de semigroupes sont des représentations géométriques de dérivations dans des systèmes de Thue. Nous caractérisons (par générateurs et relations) les groupes de diagrammes qui correspondent à des systèmes de Thue complets (confluents et noethériens). Ceci nous permet de répondre à certaines questions de Pride sur les présentations de monoïdes asphériques. Les groupes de diagrammes sont également intéressants en eux-mêmes. Il existe un algorithme très rapide pour multiplier des diagrammes, si bien que le problème du mot dans les groupes représentables par des diagrammes admet une solution agréable. La classe des groupes de diagrammes s'avère être vaste : elle comprend les groupes libres et les groupes dits de Thompson, et elle est fermée par produit direct, par produit libre, et par plusieurs autres constructions. En un sens, les groupes de diagrammes forment des analogues bidimensionnels des groupes libres. Nous développons une combinatoire des diagrammes qui ressemble à la combinatoire des mots, et qui nous permet d'établir de nombreuses propriétés des groupes de diagrammes.

Abstract : A diagram group consists of so called spherical semigroup diagrams, that is, labelled plain graphs of some special kind. Semigroup diagrams are geometric images of derivations under Thue systems. The diagram groups measure the number of ways to derive one word from another word in a given Thue system, that is they measure the non-asphericity of a Thue system. We describe (by generators and defining relations) diagram groups corresponding to complete (confluent and terminating) Thue systems. This allowed us to answer some questions of Pride about aspherical monoid presentations. Diagram groups are interesting in their own. There exists a very fast algorithm of multiplying diagrams, so groups representable by diagrams have nicely solvable word problems. The class of diagram groups turned out to be wide. It includes all free groups, the so called Thompson groups, is closed under direct and free products and under some other constructions. In some sense diagram groups are 2-dimensional analogues of free groups. We develop combinatorics on diagrams which resembles the combinatorics on words. This allowed us to establish many structure properties of diagram groups.

Publications internes Litp 1995 / Litp research reports 1995