Algebras and their related structures

Algebras and their related structures Algebras and Their Related Structures

OTKA T 037877

2002.02.01 – 2005.12.31

Principal Investigator: Agnes Szendrei

Research Team (including PI): 6 senior and 4 junior researchers

The purpose this research project is to obtain new results in three interrelated areas of abstract algebra -- universal algebra, lattice theory and semigroup theory -- in the following six topics:

1. The structure theory of finite algebras, clones on finite sets

2. The structure of the lattice of clones on a finite/infinite base set

3. Problems concerning varieties of algebras

4. Regular semigroups

5. Lattices as related structures

6. Combinatorial questions

These topics have essential connections to more classical branches of algebra as well as to computer science. For example:

We use the techniques of clone theory to study term equivalence of finite groups. This work is related to the long-standing conjecture, often attributed to Suzuki, that if for two finite groups, the subgroup lattices of their n-th powers are isomorphic for all n, then the groups themselves are isomorphic. We discovered that there exist non-isomorphic term equivalent groups, which refutes the `Suzuki conjecture’.

The following type of problem often occurs in practice, therefore the search for effective algorithms to solve it is in the focus of research in computer science:

Given two finite sets A and B (e.g. A is a set of tasks to be carried out and B is the set of workers who are available) find a way to assign an element of B to every element of A in such a way that some prescribed constraints are satisfied (e.g. not every available person can perform all the tasks, etc.).

A mathematical model is the following. We are given a relational structure A; the homomorphism problem for A is the question: algorithmically how easy/hard is it to decide for any relational structure B (of the same type as A) whether there exists a homomorphism from A to B. (In this model the relations are the constraints.) The dichotomy conjecture states that the algorithmic complexity of the homomorphism problem for every A is either in P or is NP-complete – there is no other alternative. The conjecture has been proved for special classes of relational structures A. A few years ago P. Jeavons discovered that the results of clone theory and the structure theory of finite algebras – in particular, some earlier pure algebraic results of the participants of this project – can be applied to handle the homomorphism problem. Since then we have joined in the study of this problem.