Embeddability and Universal Theory of Partially Commutative Groups

作者：Casals Ruiz Montserrat^*

来源：International Mathematics Research Notices, 2015, 2015(24): 13575-13622.

DOI：10.1093/imrn/rnv122

The first part of the paper centers in the study of embeddability between partially commutative groups. In [10], for a finite simplicial graph Gamma, the authors introduce an infinite, locally infinite graph Gamma(e), called the extension graph of Gamma. They show that each finite-induced subgraph Delta of Gamma(e) gives rise to an embedding between the partially commutative groups G(Delta) and G(Gamma). Furthermore, it is proved that, in many instances, the converse also holds. Our first result is the decidability of the Extension Graph Embedding Problem: there is an algorithm that given two finite simplicial graphs Delta and Gamma decides whether or not. is an induced subgraph of Gamma(e). As a corollary, we obtain the decidability of the Embedding Problem for 2D partially commutative groups. In the second part of the paper, we relate the Embedding Problem between partially commutative groups to the model-theoretic question of classification up to universal equivalence. We use our characterization to transfer algebraic and algorithmic results on embeddability to model-theoretic ones and obtain some rigidity results on the elementary theory of atomic pc groups as well as to deduce the existence of an algorithm to decide if an arbitrary pc group is universally equivalent to a 2D one.

• 出版日期2015