This preprint was accepted March 31, 1998
Contact:
S.A. Evdokimov, I.N.Ponomarenko
ABSTRACT:
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.