On a New High Dimensional Weisfeiler-Lehman Algorithm
Sergei Evdokimov
, Marek Karpinski
and Ilia Ponomarenko
DOI: 10.1023/A:1018672019177
Abstract
We investigate the following problem: how different can a cellular algebra be from its Schurian closure, i.e., the centralizer algebra of its automorphism group? For this purpose we introduce the notion of a Schurian polynomial approximation scheme measuring this difference. Some natural examples of such schemes arise from high dimensional generalizations of the Weisfeiler-Lehman algorithm which constructs the cellular closure of a set of matrices. We prove that all of these schemes are dominated by a new Schurian polynomial approximation scheme defined by the m-closure operators. A sufficient condition for the m-closure of a cellular algebra to coincide with its Schurian closure is given.
Pages: 29–45
Keywords: graph isomorphism problem; cellular algebra; permutation group
Full Text: PDF
References
G.M. Adelson-Vel”skii, B. Ju. Weisfeiler, A.A. Lehman, and I.A. Farad zev, On an example of a graph whose automorphism group is not transitive, Soviet Math. Dokl. 10 (1969), 440-441. L. Babai, On the order of uniprimitive permutation groups, Annals of Math. 113 (1981), 553-568. L. Babai, Automorphism groups, isomorphism, reconstruction, in Handbook of Combinatorics, R.L. Graham, M. Grötschel, and L. Lovász (Eds.), Elsevier Science, 1995, Vol. 2, pp. 1447-1541. L. Babel, Computing cellular algebras, (submitted to Combinatorica). J. Cai, M. Fürer, and N. Immerman, Optimal lower bound on the number of variables for graph identification, $Combinatorica 12$ (1992), 389-410. S. Evdokimov and I. Ponomarenko, Bases of primitive cellular algebras, Proc. International Algebraic Conference Dedicated to the Memory of D.K.Faddeev, 1997, pp. 45-46. S. Friedland, Coherent algebras and the graph isomorphism problem, Discrete Applied Math. 25 (1989), 73-98. M. Garey and D. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness, Freeman, San Francisco,
1979. D.G. Higman, Coherent algebras, Linear Algebra Appl. 93 (1987), 209-239. L.A. Kalu nin and M.H. Klin, On some numerical invariants of permutation groups, Latv. Mat. E egod. 18 (1976), 81-99 (in Russian). R.M. Karp and V. Ramachandran, Parallel algorithms for shared-memory machines, Algorithms and Complexity, 1990, Vol. A 871-942. R. Mathon, A note on the graph isomorphism counting problem, Inform. Process. Lett. 8 (1979), 131-132. I. Ponomarenko, On computation complexity problems concerning relation algebras, Zapiski Nauch. Semin. POMI 202 (1992), 116-134 (in Russian). B. Ju. Weisfeiler (ed.), On construction and identification of graphs, Springer Lecture Notes, 1976, p.
558. H. Wielandt, Finite Permutation Groups, Academic Press, New York-London, 1964.
1979. D.G. Higman, Coherent algebras, Linear Algebra Appl. 93 (1987), 209-239. L.A. Kalu nin and M.H. Klin, On some numerical invariants of permutation groups, Latv. Mat. E egod. 18 (1976), 81-99 (in Russian). R.M. Karp and V. Ramachandran, Parallel algorithms for shared-memory machines, Algorithms and Complexity, 1990, Vol. A 871-942. R. Mathon, A note on the graph isomorphism counting problem, Inform. Process. Lett. 8 (1979), 131-132. I. Ponomarenko, On computation complexity problems concerning relation algebras, Zapiski Nauch. Semin. POMI 202 (1992), 116-134 (in Russian). B. Ju. Weisfeiler (ed.), On construction and identification of graphs, Springer Lecture Notes, 1976, p.
558. H. Wielandt, Finite Permutation Groups, Academic Press, New York-London, 1964.