Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: On highly closed cellular algebras and highly closed isomorphisms. | On highly closed cellular algebras and highly closed isomorphisms Dedicated to A. A. Lehman and B. Yu. Weisfeiler on the occasion of the 30th anniversary of their paper where the cellular algebra first appeared. Sapienti sat. Sergei Evdokimov St. Petersburg Institute for Informatics and Automation evdokim@ Ilia Ponomarenko Steklov Institute of Mathematics at St. Petersburg inp@ Submitted June 2 1998 Accepted November 6 1998 Abstract We define and study m-closed cellular algebras coherent configurations and m-isomorphisms of cellular algebras which can be regarded as mth approximations of Schurian algebras . the centralizer algebras of permutation groups and of strong isomorphisms . 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 . matrix algebra isomorphisms preserving the Hadamard multiplication . On the other hand the algebras which are m-closed for all m 1 are exactly Schurian ones whereas the weak isomorphisms which are m-isomorphisms for all m 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-Fiirer-Immerman phenomenon that the m-dimensional Weisfeiler-Lehman method fails to recognize the isomorphism of graphs in an efficient way. Research supported by RFFI grants 96-15-96060 and 96-01-00676. 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 6 1999 R18 2 1 Introduction The association scheme theory was called in 2 a group theory without groups . Indeed the axiomatics of association schemes reflects combinatorial .
