Montreal Geometric & Combinatorial Group Theory Seminar

 

 

Speaker: Stuart Margolis (Bar Ilan University)

Title: "Some Surprising Undecidable Problems for

Finite Groups, Graphs and Other Finite Structures"

Date: 3:30pm Wednesday, March 19th.

Room: 920 Burnside

 

Abstract:   The discovery of undecidable problems by Godel, Turing, Church and others in the 1930's had a profound effect on mathematics and later on computer science. Yet, many mathematicians consider undecidable problems as unnatural and oddities. The purpose of this talk is to give a number of very easy to describe and natural problems on finite groups, graphs and related structures that are provably undecidable. The main technique is to reduce known undecidable problems to the problems in question. The necessary background in the theory of computation will be given during the talk. As an "advertisement" we include two of the undecidable problems here.

 

1) The Cayley Graph Embeddability Problem - The Cayley graph of a finite group relative to a generating set is a well known and well studied object that arises in many different ways. It is quite easy to check algorithmically if a finite labelled graph is indeed the Cayley graph of a finite group. We show on the other hand that the problem of checking if a given labelled graph is a subgraph of a finite Cayley graph is algorithmically undecidable. On the other hand it is decidable if such a graph is embeddable in the Cayley graph of a finite Abelian group, a finite nilpotent group of a fixed class, but not in the Cayley graph of some nilpotent group.

 

2) Subcategories of Finite Groupoids- One of the first theorems we learn in Abstract Algebra is that a subsemigroup of a finite group is in fact a group. Thus, given the multiplication table of a finite semigroup, we can algorithmically check if it is a subsemigroup of a finite group. A groupoid is a category in which every morphism is an isomorphism. Groupoids arise naturally in many geometric and topological problems. Thus a groupoid with one object is a group and the structure of groupoids can be easily determined in terms of sets and groups. However we show that the problem of determining the subcategories of finite groupoids is undecidable. That is, there is no algorithm to determine if given the multiplication table of a finite category, if it is embeddable into some finite groupoid.