Coherent algebras and the graph isomorphism problem

The concept of breaking up coherent algebras which embeds the given coherent algebra into a coherent algebra of a greater dimension and reduces the multiplicity of the algebra is introduced.

Abstract

In this paper we study the graph isomorphism problem via coherent algebras. We show that any nontrivial graph isomorphism problem reduces polynomially to the problem when an isomorphism of two coherent algebras ι: A→B is a strong isomorphism. By analysing the structure of coherent algebras with a simple spectrum we deduce that any isomorphism of two coherent algebras with a simple spectrum is a strong isomorphism. For the general case we introduce the concept of breaking up coherent algebras which embeds the given coherent algebra into a coherent algebra of a greater dimension and reduces the multiplicity of the algebra. This approach enables us to give a simple criterion when ι is a strong isomorphism for homogeneous algebras of multiplicity two.