Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1996 Copyright 1996 Universität Bonn, Institut für Informatik, Abt. V

Compact Cellular Algebras and Permutation Groups
Sergei Evdokimov, Marek Karpinski, Ilia Ponomarenko
[Download PostScript] [Download PDF]

Keeping in mind the generalization of Birkhoff's theorem on doubly stochastic matrices we define compact cellular algebras and compact permutation groups. Arising in this connection weakly compact graphs extend compact graphs introduced by G.~Tinhofer. It is proved that compact algebras are exactly the centralizer algebras of compact groups. A developed technique enables to get non-trivial examples of compact algebras and groups as well as completely identify compact Frobenius groups and the adjacency algebras of Johnson's and Hamming's schemes. In particular, Petersen's graph proves to be not compact, which answers the question by C.~Godsil. A simple polynomial-time isomorphism test for the class of compact cellular algebras (weakly compact graphs) is presented.

Last Change: 08/18/99 at 13:00:38
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope