Steklov Institute of Mathematics at St. Petersburg, Russia

inp@pdmi.ras.ru

The famous paper of Boris Weisfeiler and Andrei Leman was published in an ordinary Soviet Union information sciences bulletin fifty years ago, just nine years before the graph isomorphism problem was termed a "disease" [16]. The problem was posed to the authors by G.E. Vladuts, an expert in the creation of chemical databases, where each organic compound is described with the aid of a structural formula, in fact, a multigraph with color vertices. In this relatively small but very compressed text, the algorithmic ideas of Leman (who later became a brilliant programmer) and the algebraic technique of Weisfeiler (who later became a famous algebraic geometer) were combined to produce new concepts which are still actively used.

From an algorithmic point of view, the main idea of the paper was to replace a successive classification of vertices of a graph by the classification of its ordered arcs. In matrix language, the input of each iteration is a linear space with a basis of $\{0,1\}$ matrices; during the iteration, this linear space is extended by adding the pairwise products of basis matrices and then closed with respect to entrywise Selur-Hadamard product. This operation was denoted as $\text{Ы}$, the twenty ninth letter in the Russian alphabet. "Why $\text{Ы}$? So nobody would guess" – this is a dialogue from a popular film in the Soviet Union in the 60s.

The output of the Weisfeiler-Leman algorithm, a stable graph, is known today as a coherent configuration, or more exactly, the coherent closure, or WL-closure of the initial graph. The term "coherent configuration" was coined by D. Higman who came to coherent configurations independently in [11]. Later, Higman mentioned the Weisfeiler-Leman algorithm in [12] and Weisfeiler mentioned coherent configurations in [19]. In this connection, it should be noted that a general cellular algebra and the cellular algebra associated with a stable graph are now called, respectively, a coherent algebra and the adjacency algebra of the corresponding coherent con-figuration.

Conjectures 1 and 2 proposed in the paper and which stated, in fact, that the Weisfeiler-Leman algorithm
solves the graph isomorphism problem were incorrect. However, computations made by Leman in [14]
show that these conjectures are true for all graphs with at most $9$ vertices. A counterexample, a
strongly
regular non-rank 3 graph with 26 vertices, was found a year later [1]^{*}. In
fact, the
counterexample on 16 vertices, nowadays commonly called the Shrikhande graph, see [17], is
known
since 1959. Moreover, it turns out [5] that a deep stabilization algorithm described in a
subsequent collective monograph edited by Weisfeiler [19] and closely related with a
$k$-tuple coloring algorithm (the $k$-dim W-L in the sense of Babai [2]) cannot test
graph isomorphism for a fixed $k$ correctly; an algebraic explanation of this result in terms of
coherent
configuration was obtained in [6]. A modern presentation of this topic can be found in [Sec. 3.5, 10].

For fifty years since the paper was written, the theory of coherent configurations (cellular algebras) has been repeatedly used to obtain strong mathematical results. First of all, one should mention here a seminal theorem of L. Babai giving an upper bound for the order of a uniprimitive permutation group [3] and recent improvement of this theorem [18]. Together with the Weisfeiler-Leman algorithm, this theory played a key role in constructing polynomial-time testing isomorphism of circulant graphs [8, 15]. Finally, the same can be said of the quasipolynomial algorithm of L. Babai for testing isomorphism of general graphs [4].

In conclusion, we note that the Weisfeiler-Leman paper had a profound impact on the development of algebraic combinatorics in the Soviet Union and Russia; the details can be found in a comprehensive survey [9] and a more recent text [7].

^{*}The
smallest counterexample to Conjecture 1 had recently been constructed in [13].

- The original Russian version (scan)
- The translated paper by Weisfeiler and Leman
- The letter of Andrew Leman to Ilia Ponomarenko
- The paper + this Preface + the Letter

- G. M. Adeľson-Veľski, B. Ju. Weisfeiler, A. A. Leman, and I. A. Faradžev,
*An example of a graph which has no transitive group of automorphisms*, Dokl. Akad. Nauk SSSR**185**(1969), 975–976. - L. Babai and R. Mathon,
*Talk at the south-east conference on combinatorics and graph theory*, (1980). - L. Babai,
*On the order of uniprimitive permutation groups*, Ann. Math. (2)**113**(1981), 553–568. - L. Babai,
*Graph Isomorphism in Quasipolynomial Time*, ArXiv e-prints, 1512.03547 (2016), 1–89. - J.-Y. Cai, M. Furer, and N. Immerman,
*An optimal lower bound on the number of variables for graph identification*, Combinatorica**12**(1992), no. 4, 389–410. - S. Evdokimov and I. Ponomarenko,
*On highly closed cellular algebras and highly closed isomorphisms*, Electron. J. Comb.**6**(1999), no. 1, 31 p. (English). - S. Evdokimov and I. Ponomarenko,
*Permutation group approach to association schemes*, European Journal of Combinatorics**30**(2009), no. 6, 1456–1476. - S. Evdokimov and I. Ponomarenko,
*Circulant graphs: recognizing and isomorphism testing in polynomial time*, St. Petersbg. Math. J.**15**(2004), no. 6, 813–835. - I. A. Faradžev, M. H. Klin, and M. E. Muzychuk,
*Cellular rings and groups of automorphisms of graphs*, Faradžev, I. A. (ed.) et al., Investigations in algebraic theory of combinatorial objects. In part a rev. and updated transl. of the Russ. orig. Dordrecht: Kluwer Academic Publishers. Math. Appl., Sov. Ser. 84, Dordrecht: Kluwer Academic Publishers, 1994, pp. 1–152. - M. Grohe,
*Descriptive complexity, canonisation, and definable graph structure theory*(to appear)., Cambridge: Cambridge University Press; Ithaca, NY: Association of Symbolic Logic (ASL), 2017. - D. G. Higman,
*Coherent configurations. I*, Rend. Sem. Mat. Univ. Padova**44**(1971), 1–25. - D. G. Higman,
*Computations related to coherent configurations*, Numerical mathematics and computing, Proc. 19th Manitoba Conf., Winnipeg/ Can. 1989, Congr. Numerantium 75, 1990, pp. 9–20. - M. Klin and M. Ziv-Av,
*A non-Schurian coherent configuration on 14 points exists*, Des. Codes Cryptogr.**84**(2017), no. 1-2, 203–221. - A. A. Leman,
*Automorphisms of certain classes of graphs.*Autom. Remote Control**1970**(1970), 235–242. - M. Muzychuk,
*A solution of the isomorphism problem for circulant graphs*, Proceedings of the London Mathematical Society**88**(2004), no. 1, 1–41. - R. C. Read and D. G. Corneil,
*The graph isomorphism disease*, J. Graph Theory**1**(1977), 339–363 (English). - S. S. Shrikhande,
*The uniqueness of the $L_{2}$ association scheme*, Annals of Mathematical Statistics**30**(1959), 781–798. - X. Sun and J. Wilmes,
*Structure and automorphisms of primitive coherent configurations*, ArXiv e-prints, 1510.02195 (2015), 1–53. - B. Weisfeiler (ed.),
*On construction and identification of graphs*, Lecture Notes in Mathematics, Vol. 558, Springer-Verlag, Berlin-New York, 1976, With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler.