On highly closed cellular algebras and highly closed isomorphisms

Sergei Evdokimov ; Ilia Ponomarenko

The electronic journal of combinatorics, Tome 6 (1999)

Résumé

We define and study $m$-closed cellular algebras (coherent configurations) and $m$-isomorphisms of cellular algebras which can be regarded as $m$th approximations of Schurian algebras (i.e. the centralizer algebras of permutation groups) and of 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 algebras on $O(m)$ points which are not Schurian and $m$-isomorphisms of cellular algebras on $O(m)$ points which are not induced by strong isomorphisms. 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ürer-Immerman phenomenon that the $m$-dimensional Weisfeiler-Lehman method fails to recognize the isomorphism of graphs in an efficient way.

Détail

DOI : 10.37236/1450

Classification : 05E99, 05C60
Mots-clés : cellular algebras, coherent configurations, Schurian algebras, strong isomorphisms, weak isomorphisms, Cai-Fürer-Immerman phenomenon, Weisfeiler-Lehman method