Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1996 Copyright 1996 University of Bonn, Department of Computer Science, Abt. V
85154

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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V