Petersburg Department of Steklov Institute of Mathematics

PREPRINT 12/1998

S.A. Evdokimov & I.N.Ponomarenko


This preprint was accepted March 31, 1998
Contact: S.A. Evdokimov, I.N.Ponomarenko

We study $m$-closed cellular algebras (coherent configuration) and
$m$-isomorphisms of cellular algebras which can be regarded as $m$th
approximations to
Schurian algebras (i.e. the centralizer algebras of permutation
groups) and to strong isomorphisms (i.e. bijections of the point sets
taking one algebra to the other) respectively. If $m=1$ we come to
arbitrary cellular
algebras and their weak isomorphisms (i.e. matrix algebra isomorphisms
preserving the Hadamard multiplication). On the other hand, the algebras which
are $m$-closed for all $m\ge 1$ are exactly Schurian ones whereas the weak
isomorphisms which are $m$-isomorphisms for all $m\ge 1$ are exactly ones induced
by strong isomorphisms.  We show that for any $m$ there exist $m$-closed
non-Schurian algebras on $O(m)$ points and $m$-isomorphisms of cellular
algebras on $O(m)$ points which are not induced by strong isomorphisms. One more
result establishes the equivalence of the Schurian polynomial
approximation schemes defined by the $m$-closure and
the $m$-dimensional Weisfeiler-Lehman methods.  As a
consequence, on one hand this enables us to find for any~$m$ an edge colored
graph with $O(m)$ vertices satisfying the $m$-vertex condition and having
non-Schurian adjacency algebra. On the other hand, we rediscover and
explain from the algebraic point of view the Cai-F{\"
u}rer-Immerman phenomenon that the $m$-dimensional Weisfeiler-Lehman method fails to
recognize in an efficient way the isomorphism of graphs.

Back to all preprints
Back to the Petersburg Department of Steklov Institute of Mathematics