## The original paper by Weisfeiler and Leman: The preface

#### Ilia PonomarenkoSteklov Institute of Mathematics at St. Petersburg, Russiainp@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" . 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 . Later, Higman mentioned the Weisfeiler-Leman algorithm in  and Weisfeiler mentioned coherent configurations in . 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  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 *. In fact, the counterexample on 16 vertices, nowadays commonly called the Shrikhande graph, see , is known since 1959. Moreover, it turns out  that a deep stabilization algorithm described in a subsequent collective monograph edited by Weisfeiler  and closely related with a $k$-tuple coloring algorithm (the $k$-dim W-L in the sense of Babai ) cannot test graph isomorphism for a fixed $k$ correctly; an algebraic explanation of this result in terms of coherent configuration was obtained in . 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  and recent improvement of this theorem . 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 .

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  and a more recent text .

Acknowledgments. We thank Misha Klin and Andrei Vasilyiev for helpful inter-mediation, Grigory Ryabov for the translation of the text into English, as well as Katie Brodhead for assistance in the improvement of English in both preface and translation.

*The smallest counterexample to Conjecture 1 had recently been constructed in .

### References

1. 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.
2. L. Babai and R. Mathon, Talk at the south-east conference on combinatorics and graph theory, (1980).
3. L. Babai, On the order of uniprimitive permutation groups, Ann. Math. (2) 113 (1981), 553–568.
4. L. Babai, Graph Isomorphism in Quasipolynomial Time, ArXiv e-prints, 1512.03547 (2016), 1–89.
5. 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.
6. S. Evdokimov and I. Ponomarenko, On highly closed cellular algebras and highly closed isomorphisms, Electron. J. Comb. 6 (1999), no. 1, 31 p. (English).
7. S. Evdokimov and I. Ponomarenko, Permutation group approach to association schemes, European Journal of Combinatorics 30 (2009), no. 6, 1456–1476.
8. S. Evdokimov and I. Ponomarenko, Circulant graphs: recognizing and isomorphism testing in polynomial time, St. Petersbg. Math. J. 15 (2004), no. 6, 813–835.
9. 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.
10. M. Grohe, Descriptive complexity, canonisation, and definable graph structure theory (to appear)., Cambridge: Cambridge University Press; Ithaca, NY: Association of Symbolic Logic (ASL), 2017.
11. D. G. Higman, Coherent configurations. I, Rend. Sem. Mat. Univ. Padova 44 (1971), 1–25.
12. 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.
13. 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.
14. A. A. Leman, Automorphisms of certain classes of graphs. Autom. Remote Control 1970 (1970), 235–242.
15. M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proceedings of the London Mathematical Society 88 (2004), no. 1, 1–41.
16. R. C. Read and D. G. Corneil, The graph isomorphism disease, J. Graph Theory 1 (1977), 339–363 (English).
17. S. S. Shrikhande, The uniqueness of the $L_{2}$ association scheme, Annals of Mathematical Statistics 30 (1959), 781–798.
18. X. Sun and J. Wilmes, Structure and automorphisms of primitive coherent configurations, ArXiv e-prints, 1510.02195 (2015), 1–53.
19. 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.