# On the Weisfeiler algorithm of depth-$1$ stabilization

Gang Chen  School of Mathematics and Statistics, and Key Laboratory of
Nonlinear Analysis $\&$ Applications (Ministry of Education), Central China
Normal University, Wuhan 430079, China<EMAIL_ADDRESS>,  Qing
Ren  School of Mathematics and Statistics, and Key Laboratory of Nonlinear
Analysis $\&$ Applications (Ministry of Education), Central China Normal
University, Wuhan 430079, China<EMAIL_ADDRESS>and  Ilia
Ponomarenko  Steklov Institute of Mathematics at St. Petersburg, Russia;
School of Mathematics and Statistics, and Key Laboratory of Nonlinear Analysis
$\&$ Applications (Ministry of Education), Central China Normal University,
Wuhan 430079, China<EMAIL_ADDRESS>
###### Abstract.

An origin of the multidimensional Weisfeiler-Leman algorithm goes back to a
refinement procedure of deep stabilization, introduced by B. Weisfeiler in a
paper included in the collective monograph “On construction and identification
of graphs” (1976). This procedure is recursive and the recursion starts from
an algorithm of depth-$1$ stabilization, which has never been discussed in the
literature.

A goal of the present paper is to show that a simplified algorithm of the
depth-$1$ stabilization has the same power as the $3$-dimensional Weisfeiler-
Leman algorithm. It is proved that the class of coherent configurations
obtained at the output of this simplified algorithm coincides with the class
introduced earlier by the third author. As an application we also prove that
if there exist at least two nonisomorphic projective planes of order $q$, then
the Weisfeiler-Leman dimension of the incidence graph of any projective plane
of order $q$ is at least $4$.

##  1\. Introduction

In 1968, B. Weisfeiler and A. Leman proposed an algorithm $\operatorname{WL}$
for testing graph isomorphism [19]. The idea of the $\operatorname{WL}$ is as
follows: analyzing the triples of vertices of a graph ${\cal G}$ with vertex
set $\Omega$, construct a canonical partition $\operatorname{WL}({\cal G})$ of
the Cartesian square $\Omega^{2}$, such that pairs from different classes lie
in different orbits of the induced action of the group
$\operatorname{Aut}({\cal G})$ on $\Omega^{2}$. It should be noted that the
goal (as Weisfeiler later wrote) was to construct an automorphic partition of
${\cal G}$, i.e., a partition of $\Omega$ into the orbits of the group
$\operatorname{Aut}({\cal G})$. A year later, it became clear that the
constructed algorithm did not achieve this goal [1].

It can be seen from the 1968 paper that the authors understood the need to
include individualization of vertices in the “right” algorithm. Probably, this
was fully realized in the paper by Weisfeiler, included by him in the
collective monograph [18, Section O], where he introduced the concept of deep
stabilization. Again, the goal was to find the automorphic partition of ${\cal
G}$, but here the individualization of the vertices of ${\cal G}$ has already
explicitly been used. The number of individualized vertices is just the depth
of the algorithm $\operatorname{W}_{m}$ of _depth- $m$ stabilization_ proposed
by Weisfeiler. The algorithm starts with $\operatorname{WL}$ and calls the
algorithm $W_{m-1}$ ($m\geq 2$) recursively, followed by a depth-$1$
stabilization (the exact definitions can also be found in Section 4). It was
conjectured that if $m$ is at least $O(\log n)$, then the depth-$m$
stabilization determines the automorphic partition of any graph of order $n$.
Furthermore, it was proved that depth-$1$ stabilization determines this
partition in some nontrivial special cases [18, Section P].

The algorithm now known as the multidimensional Weisfeiler-Leman algorithm was
used by many researchers in the late 1970s and early 1980s, see [2]. The
$m$-dimensional version $\operatorname{WL}_{m}$ of this algorithm (the _$m$
-dim WL_) analyzes $(m+1)$-tuples of vertices, but the algorithm itself is
non-recursive and does not explicitly use individualization of the vertices of
input graph (note that $\operatorname{WL}_{2}=\operatorname{WL}$). This
algorithm has been extensively studied in the context of the graph isomorphism
problem and descriptive complexity theory (see [12]) and culminated in its use
in the Babai quasipolynomial algorithm [2]. At the same time, it became clear
that the $\operatorname{WL}_{m}$ cannot determine the automorphic partition of
some graphs ${\cal G}$ even if $m=cn$ for an absolute constant $c$ [4] (see
also [8]).

One of the main goals of the present paper is to compare the power of the
depth-$1$ stabilization $\operatorname{W}=\operatorname{W}_{1}$ and the
$m$-dim WL. It should be noted that these algorithms being applied to a graph
${\cal G}$ have different outputs (for $m\geq 3$). The algorithm
$\operatorname{W}$ constructs a partition $\operatorname{W}({\cal G})$ of the
set $\Omega^{2}$, that is a _coherent configuration_ in the sense of D. Higman
[14] (or stationary graph in terms of B. Weisfeiler and A. Leman), whereas the
second one constructs the partition $\operatorname{WL}_{m}({\cal G})$ of the
Cartesian power $\Omega^{m}$, which is an _$m$ -ary coherent
configuration_111For $m=2$, this is an ordinary coherent configuration. in
terms of L. Babai [2] (see also [13]). A natural way to compare the outputs is
to consider the projection $\operatorname{pr}_{2}\operatorname{WL}_{m}({\cal
G})$ of the $m$-ary coherent configuration $\operatorname{WL}_{m}({\cal G})$
to the first two coordinates, which is an ordinary coherent configuration. Our
first result states that in this sense the power of $\operatorname{W}$ is
between the powers of $\operatorname{WL}_{3}$ and $\operatorname{WL}_{4}$,
more exactly,

(1) $\operatorname{pr}_{2}\operatorname{WL}_{3}({\cal
G})\leq\operatorname{W}({\cal
G})\leq\operatorname{pr}_{2}\operatorname{WL}_{4}({\cal G})$

for every colored graph ${\cal G}$. The proof will be given in Section 7.

The exact definition of the depth-$1$ stabilization is quite cumbersome, see
Section 4. Therefore, we consider also a “light” version of the depth-$1$
stabilization, which was actually studied by B. Weisfeiler in more detail, and
the output of which is also a coherent configuration (in general, smaller than
that in the full version of the depth-$1$ stabilization), denoted below by
$\operatorname{W_{1/2}}({\cal G})$. Roughly speaking,
$\operatorname{W_{1/2}}({\cal G})$ can be thought as the output of the
Weisfeiler-Leman algorithm applied to the graph ${\cal G}$ in which any pair
of vertices is colored by a multiset of colors of this pair in each coherent
configuration $\operatorname{WL}({\cal G}_{\alpha})$, $\alpha\in\Omega$, where
${\cal G}_{\alpha}$ is a colored graph obtained by individualization of
$\alpha$ in ${\cal G}$.

######  Theorem 1.1.

For every colored graph ${\cal G}$, we have

(2) $\operatorname{WL}_{3}({\cal
G})=\operatorname{WL}_{3}(\operatorname{W_{1/2}}({\cal
G}))\quad\text{and}\quad\operatorname{pr}_{2}\operatorname{WL}_{3}({\cal
G})=\operatorname{W_{1/2}}({\cal G}).$

Although our informal definition of $\operatorname{W_{1/2}}({\cal G})$ is
given for colored graphs, the concept of coloring is not necessary. Indeed,
the coherent configurations which are stable with respect to
$\operatorname{W_{1/2}}$ are _sesquiclosed_ in the sense of [17], and,
moreover, $\operatorname{W_{1/2}}({\cal G})$ is just the intersection of all
coherent configurations on $\Omega$, containing the edge set of ${\cal G}$ as
one of the relations (Theorem 5.1). In fact, the two formulas in Theorem 1.1
express some relations between $3$-ary and $2$-ary coherent configurations.

On the other hand, the concept of coloring is essential if one is interested
in applying the depth-$m$ stabilization and the $m$-dim $\operatorname{WL}$ to
test isomorphism directly, without computing an automorphic partition. In this
case, it is said that (a) graphs ${\cal G}$ and ${\cal G}^{\prime}$ are
_$\operatorname{WL}_{m}$ -equivalent_ (or not distinguished by the algorithm
$\operatorname{WL}_{m}$) if the colorings of the partitions
$\operatorname{WL}_{m}({\cal G})$ and $\operatorname{WL}_{m}({\cal
G}^{\prime})$, constructed by the $\operatorname{WL}_{m}$ are the same, and
(b) the $\operatorname{WL}_{m}$ _identifies_ a graph ${\cal G}$ if every graph
$\operatorname{WL}_{m}$-equivalent to ${\cal G}$ is isomorphic to ${\cal G}$.
In a similar way, one can define the $\operatorname{W_{1/2}}$-equivalence and
$\operatorname{W_{1/2}}$-identification.

######  Theorem 1.2.

Two graphs are $\operatorname{WL}_{3}$-equivalent if and only if they are
$\operatorname{W_{1/2}}$-equivalent. Moreover, the $\operatorname{WL}_{3}$ and
$\operatorname{W_{1/2}}$ identify the same graphs.

The structure of the colorings used in the above definitions is quite
complicated, for example, the coloring constructed by the
$\operatorname{WL}_{m}$ contains full information about the intersection
numbers of the corresponding $m$-ary coherent configuration. From algebraic
point of view, the colorings of two $m$-ary coherent configurations are equal
if and only if the color preserving bijection between their color classes is
an algebraic isomorphism between these coherent configurations (for $m=2$, an
algebraic isomorphism is what was called a weak equivalence in [18]). The
proof of Theorem 1.2 is given just in terms of the algebraic isomorphisms. In
this language, the algorithm $\operatorname{WL}$ identifies a graph ${\cal G}$
if and only if the coherent configuration $\operatorname{WL}({\cal G})$ is
separable, i.e., every algebraic isomorphism from it is induced by a
(combinatorial) isomorphism [11, Theorem 2.5]. In particular, it gives a
method to prove that a given graph has the _Weisfeiler-Leman dimension_ at
most $2$, where the Weisfeiler-Leman dimension of a graph ${\cal G}$ is the
smallest $m$ for which the $\operatorname{WL}_{m}$ identifies ${\cal G}$.

In general, not every algebraic isomorphism of a coherent configuration
respects the property of being sesquiclosed. In this connection, it is quite
natural to consider sesquiclosed algebraic isomorphisms, i.e., those that can
be extended to algebraic isomorphisms of one-point extensions. The graphs
${\cal G}$ of the Weisfeiler-Leman dimension at most $3$ can be characterized
as those for which the coherent configuration $\operatorname{W_{1/2}}({\cal
G})$ is _sesquiseparable_ in the sense that every sesquiclosed algebraic
isomorphism from it is induced by an isomorphism. As an immediate consequence
of Theorem 1.2 we obtain the following statement.

######  Corollary 1.3.

The Weisfeiler-Leman dimension of a graph ${\cal G}$ is at most $3$ if and
only if the coherent configuration $\operatorname{W_{1/2}}({\cal G})$ is
sesquiseparable.

To illustrate the above concepts, we consider the incidence graphs of finite
projective planes. On the first glance, the results obtained in [10] make
impression that the $\operatorname{WL}_{3}$ cannot distinguish these graphs.
Actually, this is true but a direct deduction does not give a nontrivial lower
bound on the Weisfeiler-Leman dimension. On the other hand, the technique
developed in the present paper enables us to do this.

######  Theorem 1.4.

The incidence graphs of finite projective planes of the same order are
$\operatorname{W_{1/2}}$-equivalent.

Theorems 1.4 and 1.1 show that any two incidence graphs of finite projective
planes of the same order $q$ are $\operatorname{WL}_{3}$-equivalent. Thus the
Weisfeiler-Leman dimension of any such graph is at least $4$ if there are at
least two nonisomorphic projective planes of order $q$ (which is the case for
infinitely many prime powers $q$).

######  Corollary 1.5.

Let $q$ be a positive integer such that there are at least two nonisomorphic
projective planes of order $q$. Then the Weisfeiler-Leman dimension of the
incidence graph of every finite projective plane of order $q$ is at least $4$.

The paper is organized as follows. In Sections 2 and 3, we give a necessary
background on ordinary and $m$-ary coherent configurations, and the
$m$-dimensional Weisfeiler-Leman algorithm. A general description of the
depth-$m$ stabilization in the language of coherent configurations is given in
Section 4. Special attention is paid here to the case $m=1$. Then in Section
5, we introduce the $\operatorname{W_{1/2}}$-closure of a coherent
configuration and show that $\operatorname{W_{1/2}}$ is not stronger than
$\operatorname{WL}_{3}$. Formula (1) and Theorems 1.1 and 1.2 are proved in
Section 7. In Section 8, we prove Theorem 1.4.

##  2\. Coherent configurations

In order to make the paper as selfcontained as possible, we present a
necessary background from the theory of coherent configurations. Our notation
is compatible with those in the monograph [5]; proofs of the statements below
can be found there.

###  2.1. Notation

Throughout the paper, $\Omega$ denotes a finite set. The $i$th coordinate of
an $m$-tuple $x\in\Omega^{m}$ is denoted by $x_{i}$, $i=1,\ldots,m$. The
concatenation of $x$ and $y\in\Omega^{k}$ is defined to be the $(m+k)$-tuple
$x\cdot y=(x_{1},\ldots,x_{m},y_{1},\ldots,y_{k})$.

For $\Delta\subseteq\Omega$, the Cartesian product $\Delta\times\Delta$ and
its diagonal are denoted by ${\bf 1}_{\Delta}$ and $1_{\Delta}$, respectively;
for $\delta\in\Delta$, we abbreviate $1_{\delta}=1_{\\{\delta\\}}$. For a
relation $s\subseteq{\bf 1}_{\Omega}$, we set
$s^{*}=\\{(\alpha,\beta):(\beta,\alpha)\in s\\}$, $\alpha
s=\\{\beta\in\Omega:\ (\alpha,\beta)\in s\\}$ for all $\alpha\in\Omega$. For
relations $r,s\subseteq\Omega\times\Omega$, we put $r\cdot
s=\\{(\alpha,\beta)\\!:\ (\alpha,\gamma)\in r,\ (\gamma,\beta)\in s$ for some
$\gamma\in\Omega\\}$. For any set $S$ of relations, we denote by $S^{\cup}$
the set of all unions of elements of $S$. For any mapping
$f:\Omega\to\Omega^{\prime}$, we set $s^{f}=\\{(\alpha^{f},\beta^{f}):\
(\alpha,\beta)\in s\\}$.

The partitions of the same set are partially ordered in a standard way: $S\leq
T$ if each class of $S$ is a union of some classes of $T$, or equivalently,
$S^{\cup}\subseteq T^{\cup}$. The join of $S$ and $T$ is defined as a uniquely
determined partition $S\vee T$ such that $(S\vee T)^{\cup}=S^{\cup}\cap
T^{\cup}$. For any set ${\cal S}$ of partitions of the same set, that is
closed with respect to the join, one can define a mapping ${\mathfrak{c}}$
from the set of all partitions of this set to ${\cal S}$, that takes $S$ to
the join of all $T\in{\cal S}$ such that $T\geq S$. This mapping is a closure
operator in the sense that for each partition $S$, we have
${\mathfrak{c}}(S)\geq S$,
${\mathfrak{c}}({\mathfrak{c}}(S))={\mathfrak{c}}(S)$, and
${\mathfrak{c}}(S)\geq{\mathfrak{c}}(T)$ if $S\geq T$ [3].

###  2.2. Rainbows

Let $S$ be a partition of $\Omega^{2}$. A pair ${\cal X}=(\Omega,S)$ is called
a _rainbow_ on $\Omega$ if

  1. (C1)

$1_{\Omega}\in S^{\cup}$,

  2. (C2)

$s^{*}\in S$ for all $s\in S$.

The numbers $|\Omega|$ and $\operatorname{rk}({\cal X})=|S|$ are called the
degree and rank of ${\cal X}$, respectively. The elements of $S$ and of
$S^{\cup}$ are called basis relations and _relations_ of ${\cal X}$. A unique
basis relation containing the pair $(\alpha,\beta)$ is denoted by
$r(\alpha,\beta)=r_{\cal X}(\alpha,\beta)$. The set of all relations of ${\cal
X}$ is closed with respect to intersections and unions. Any
$\Delta\subseteq\Omega$ for which $1_{\Delta}\in S$ is called a fiber of
${\cal X}$; the set of all of them is denoted by $F=F({\cal X})$. In view of
condition (C1), the set $F$ forms a partition of $\Omega$. Any element of
$F^{\cup}$ is called a _homogeneity set_ of ${\cal X}$.

Let ${\cal X}^{\prime}=(\Omega^{\prime},S^{\prime})$ be a rainbow. A
combinatorial isomorphism or, briefly, _isomorphism_ from ${\cal X}$ to ${\cal
X}^{\prime}$ is defined to be a bijection $f:\Omega\rightarrow\Omega^{\prime}$
such that $s^{f}\in S^{\prime}$ for all $s\in S$. In this case, the rainbows
${\cal X}$ and ${\cal X}^{\prime}$ are said to be isomorphic. The group of all
isomorphisms of ${\cal X}$ to itself contains a normal subgroup

$\operatorname{Aut}({\cal X})=\\{f\in\operatorname{Sym}(\Omega):\
s^{f}=s\text{ for all }s\in S\\}$

called the automorphism group of ${\cal X}$.

The partial order of the partitions of $\Omega^{2}$ induces a partial order of
the rainbows on $\Omega$. Namely, given two such rainbows ${\cal X}$ and
${\cal Y}$, we set

${\cal X}\leq{\cal Y}\ \Leftrightarrow\ S({\cal X})^{\cup}\subseteq S({\cal
Y})^{\cup}$

and say that ${\cal X}$ is an _fusion_ of ${\cal Y}$ and ${\cal Y}$ is an
_extension_ of ${\cal X}$. The minimal and maximal elements with respect to
this order are the trivial and discrete rainbows, respectively; in the former
case, $S$ consists of $1_{\Omega}$ and its complement (unless $\Omega$ is a
singleton), and in the last case, $S$ consists of singletons. The
_intersection_ of rainbows ${\cal X}$ and ${\cal Y}$ is defined as a uniquely
determined rainbow ${\cal X}\cap{\cal Y}$ such that $S({\cal X}\cap{\cal
Y})=S({\cal X})\vee S({\cal Y})$, or equivalently,

$S({\cal X}\cap{\cal Y})^{\cup}=S({\cal X})^{\cup}\,\cap\,S({\cal Y})^{\cup}.$

A similarity from ${\cal X}$ to ${\cal X}^{\prime}$ is defined to be a
bijection $\varphi:S\rightarrow S^{\prime}$ such that for all $s\in S$ we have
$\varphi(s)\subseteq 1_{\Omega^{\prime}}\ \Leftrightarrow\ s\subseteq
1_{\Omega}$, and $\varphi(s^{*})=\varphi(s)^{*}$. In this case, ${\cal X}$ and
${\cal X}^{\prime}$ are said to be similar. Extending $\varphi$ in a natural
way to bijections $S^{\cup}\to{S^{\prime}}{\phantom{x}{}^{\cup}}$ and
$F^{\cup}\to{F^{\prime}}{\phantom{x}{}^{\cup}}$, denoted also by $\varphi$, we
have

$\varphi(1_{\Omega})=1_{\Omega^{\prime}}\quad\text{and}\quad\Omega^{\varphi}=\Omega^{\prime}.$

Every isomorphism $f:{\cal X}\to{\cal X}^{\prime}$ _induces_ the similarity
$\varphi_{f}:{\cal X}\to{\cal X}^{\prime},$ $s\mapsto s^{f}$. A similarity
$\varphi$ is induced by an isomorphism $f$ if it holds that
$\varphi=\varphi_{f}$. The identity similarity of ${\cal X}$ is denoted by
$\operatorname{id}_{\cal X}$. A similarity $\psi$ from a rainbow ${\cal
Y}\geq{\cal X}$ _extends_ a similarity $\varphi$ from ${\cal X}$ if
$\psi(s)=\varphi(s)$ for all $s\in S$.

###  2.3. Coherent configurations

A rainbow ${\cal X}$ is called a _coherent configuration_ if it satisfies the
additional condition

  1. (C3)

given $r,s,t\in S$, the _intersection number_ $c_{r,s}^{t}=|\alpha r\cap\beta
s^{*}|$ does not depend on the choice of $(\alpha,\beta)\in t$.

For any basis relation $t\in S$ such that $t\subseteq 1_{\Omega}$, the
intersection number $c_{s,s^{*}}^{t}$ is either zero or is equal to $|\alpha
s|$ for all $\alpha$ such that $\alpha s\neq\varnothing$; in the latter case,
the number $n_{s}=|\alpha s|$ is called the valency of $s$. Every basis
relation $s\in S$ is contained in the Cartesian product of two uniquely
determined fibers which are called the _left and right supports_ of $s$,
respectively.

For homogeneity sets $\Delta$ and $\Gamma$, we denote by $S_{\Delta,\Gamma}$
the set of all basis relations contained in $\Delta\times\Gamma$, and
abbreviate $S_{\Delta}=S_{\Delta,\Delta}$. The rainbow ${\cal
X}_{\Delta}=(\Delta,S_{\Delta})$ is a coherent configuration called the
_restriction_ of ${\cal X}$ to $\Delta$. The coherent configuration ${\cal X}$
is said to be homogeneous or a scheme if $|F|=1$, or equivalently,
$1_{\Omega}\in S$.

Let $G\leq\operatorname{Sym}(\Omega)$ be a permutation group. Denote by $S$
the set of all orbits $(\alpha,\beta)^{G}$ in the componentwise action of $G$
on $\Omega\times\Omega$, where $\alpha,\beta\in\Omega$. Then the pair

$\operatorname{Inv}(G)=\operatorname{Inv}(G,\Omega)=(\Omega,S)$

is a coherent configuration. Any coherent configuration ${\cal X}$ associated
with some permutation group $G$ in this way is said to be schurian. In this
case every fiber $\Delta$ of ${\cal X}$ is an orbit of $G$, and the points of
$\Delta$ can be identified with the right cosets of a point stabilizer
$G_{\delta}$ with $\delta\in\Delta$, so that the action of $G$ on $\Delta$ is
induced by right multiplications. Note that a coherent configuration ${\cal
X}$ is _schurian_ if and only if ${\cal
X}=\operatorname{Inv}(\operatorname{Aut}({\cal X}))$.

Let ${\cal X}$ and ${\cal X}^{\prime}$ be coherent configurations. A bijection
$\varphi:S\rightarrow S^{\prime}$, $r\mapsto r^{\prime}$ is called an
_algebraic isomorphism_ from ${\cal X}$ to ${\cal X}^{\prime}$ if

$c_{r^{\prime},s^{\prime}}^{t^{\prime}}=c_{r,s}^{t}\quad\text{for all}\
r,s,t\in S.$

Every algebraic isomorphism of coherent configurations is also a similarity of
the corresponding rainbows. Furthermore, $\varphi$ preserves the degree, rank,
and supports of basis relations, i.e., if $\Delta,\Gamma$ are fibers of ${\cal
X}$, then $r\in S_{\Delta,\Gamma}$ if and only if $r^{\prime}\in
S_{\Delta^{\prime},\Gamma^{\prime}}$.

Not every algebraic isomorphism is induced by an isomorphism. The coherent
configuration ${\cal X}$ is said to be _separable_ if every algebraic
isomorphism from ${\cal X}$ is induced by an isomorphism. Any trivial or
discrete coherent configuration is separable.

###  2.4. Coherent closure

The set of all coherent configurations on $\Omega$ is closed with respect to
intersection. The _coherent closure_ of a set $T\subseteq
2^{\Omega\times\Omega}$ is defined to be the intersection
$\operatorname{WL}(T)$ of all coherent configurations ${\cal X}$ on $\Omega$,
for which $T\subseteq S^{\cup}$. The notation reflects the fact that
$\operatorname{WL}(T)$ can be computed by the algorithm $\operatorname{WL}$,
see Section 1.

When $T$ is the union of the set $S({\cal X})$ for some rainbow ${\cal X}$ on
$\Omega$ and a set $T^{\prime}\subseteq 2^{\Omega\times\Omega}$, we put
$\operatorname{WL}({\cal X},T^{\prime}):=\operatorname{WL}(T)$ and abbreviate
$\operatorname{WL}({\cal X}):=\operatorname{WL}({\cal X},\varnothing)$ and
$\operatorname{WL}({\cal X},s):=\operatorname{WL}({\cal X},\\{s\\})$. In these
notation, the mapping $\operatorname{WL}:{\cal
X}\mapsto\operatorname{WL}({\cal X})$ becomes a closure operator on the
rainbows on $\Omega$.

Let ${\cal X}$ and ${\cal X}^{\prime}$ be rainbows and $\varphi:{\cal
X}\to{\cal X}^{\prime}$ a similarity. In general, there is no algebraic
isomorphism $\psi:\operatorname{WL}({\cal X})\to\operatorname{WL}({\cal
X}^{\prime})$ extending $\varphi$. However, if such $\psi$ does exist, then it
is uniquely determined (and can be computed by the algorithm
$\operatorname{WL}$). Moreover, if $\varphi$ is induced by an isomorphism $f$,
then $f$ induces $\psi$.

Let $m\geq 1$ and $y\in\Omega^{m}$. The $m$-point extension of a coherent
configuration ${\cal X}$ on $\Omega$ with respect to $y$ is defined to be the
coherent closure ${\cal X}_{y}=\operatorname{WL}({\cal X},T)$ with
$T=\\{1_{y_{i}}:\ 1\leq i\leq m\\}$. To simplify notation, we write $r_{y}$
instead of $r_{{\cal X}_{y}}$. When the points are irrelevant, we use the term
“point extension”, and if $m=1$, we abbreviate ${\cal X}_{y_{1}}:={\cal
X}_{y}$.

Let $\varphi:{\cal X}\to{\cal X}^{\prime}$ be an algebraic isomorphism, and
let $x\in\Omega^{m}$, $x^{\prime}\in\Omega^{\prime}{\phantom{x}{}^{m}}$. An
algebraic isomorphism $\psi:{\cal X}_{x}\to{\cal X}^{\prime}_{x^{\prime}}$ is
called an $xx^{\prime}$-extension  (or just a point extension) of $\varphi$ if
$\psi$ extends $\varphi$ and

$\psi(1_{x_{i}})=1_{x^{\prime}_{i}},\quad i=1,\ldots,m.$

The $xx^{\prime}$-extension is unique if it exists, and then we denote it by
$\varphi_{xx^{\prime}}$. Note that if the identity algebraic isomorphism
$\varphi=\operatorname{id}_{\cal X}$ has the extension $\varphi_{\tilde{x}x}$
for some $m$-tuple $\tilde{x}$, then the composition of $\varphi_{\tilde{x}x}$
with $\varphi_{xx^{\prime}}$ is obviously the $\tilde{x}x^{\prime}$-extension
of $\varphi$.

If $m=1$ and $y=(\alpha)$, $y^{\prime}=(\alpha^{\prime})$ are one-tuples, then
the algebraic isomorphism
$\varphi_{\alpha\alpha^{\prime}}:=\varphi_{yy^{\prime}}$ is called the
$\alpha\alpha^{\prime}$-extension of $\varphi$. Note that it exists only if
$\Delta^{\varphi}=\Delta^{\prime}$, where $\Delta$ (respectively,
$\Delta^{\prime}$) is the fiber of ${\cal X}$ (respectively, ${\cal
X}^{\prime}$), containing the point $\alpha$ (respectively,
$\alpha^{\prime}$).

When ${\cal X}={\cal X}^{\prime}$ and $\varphi=\operatorname{id}_{\cal X}$, we
introduce a binary relation $\sim$ on the concatenations $x\cdot
y\in\Omega^{m+2}$, where $x\in\Omega^{2}$, so that

(3) $x\cdot y\sim x^{\prime}\cdot
y^{\prime}\quad\Leftrightarrow\quad\varphi_{yy^{\prime}}(r_{y}(x))=r_{y^{\prime}}(x^{\prime});$

in accordance with the above, here it is implicitly assumed that the algebraic
automorphism $\varphi$ has the $yy^{\prime}$-extension.

###  2.5. $m$-ary coherent configurations

Let $m$ be a positive integer. For a tuple $x\in\Omega^{m}$, denote by
$\rho(x)$ the equivalence relation on $M=\\{1,\ldots,m\\}$ such that
$(i,j)\in\rho(x)$ if and only if $x_{i}=x_{j}$. The monoid of all maps from
$M$ to itself is denoted by $\operatorname{Mon}(M)$. Given
$\sigma\in\operatorname{Mon}(M)$, we set

$x^{\sigma}=(x_{1^{\sigma}},\ldots,x_{m^{\sigma}}).$

Let ${\mathfrak{X}}$ be a partition of $\Omega^{m}$ and $x\in\Omega^{m}$. The
class of ${\mathfrak{X}}$ containing $x$ is denoted by $[x]$. Given
$X_{1},\ldots,X_{m}\in{\mathfrak{X}}$, we denote by $n(x;X_{1},\ldots,X_{m})$
the number of all $\alpha\in\Omega$ such that $x_{i\leftarrow\alpha}\in X_{i}$
for all $i\in M$, where

(4)
$x_{i\leftarrow\alpha}=(x_{1},\ldots,x_{i-1},\alpha,x_{i+1},\ldots,x_{m}).$

A partition ${\mathfrak{X}}$ of $\Omega^{m}$ is called an _$m$ -ary coherent
configuration_ on $\Omega$ if the following conditions are satisfied for all
$X\in{\mathfrak{X}}$:

  1. (C1’)

$\rho(x)$ does not depend on $x\in X$,

  2. (C2’)

$X^{\sigma}\in{\mathfrak{X}}$ for all $\sigma\in\operatorname{Mon}(M)$,

  3. (C3’)

for any $X_{0},X_{1},\ldots,X_{m}\in{\mathfrak{X}}$, the number
$n_{X_{1},\ldots,X_{m}}^{X_{0}}=n(x_{0};X_{1},\ldots,X_{m})$ does not depend
on $x_{0}\in X_{0}$.

The $2$-ary coherent configurations are the coherent configurations in the
sense of Subsection 2.3, and the definitions below are compatible with that
introduced there.

The $m$-ary coherent configurations on $\Omega$ are partially ordered in
accordance with the partial order of the partitions of $\Omega^{m}$. The
intersection ${\mathfrak{X}}\cap{\mathfrak{Y}}$ of two $m$-ary coherent
configurations ${\mathfrak{X}}$ and ${\mathfrak{Y}}$ on $\Omega$ is defined as
the join of the corresponding partitions of $\Omega^{m}$. It is not hard to
verify that ${\mathfrak{X}}\cap{\mathfrak{Y}}$ is also an $m$-ary coherent
configuration. This enables us to define the $m$-ary coherent closure
$\operatorname{WL}_{m}({\mathfrak{X}})$ for any partition ${\mathfrak{X}}$ of
$\Omega^{m}$ as the intersection of all $m$-ary coherent configurations
${\mathfrak{Y}}\geq{\mathfrak{X}}$. In particular, the mapping
${\mathfrak{X}}\mapsto\operatorname{WL}_{m}({\mathfrak{X}})$ is a closure
operator, and if $m=2$, then
$\operatorname{WL}_{m}({\mathfrak{X}})=\operatorname{WL}({\mathfrak{X}})$.

Let $X\subseteq\Omega^{m}$, $k\in M$, and $y\in\Omega^{m-k}$. Denote by
$\operatorname{pr}_{k}X$ (respectively, $\operatorname{res}_{y}X$) the set of
all $x\in\Omega^{k}$ such that $x\cdot x^{\prime}\in X$ for some
$x^{\prime}\in\Omega^{m-k}$ (respectively, such that $x\cdot y\in X$). In
accordance with [13] (see also [17]), if ${\mathfrak{X}}$ is an $m$-ary
coherent configuration, then

(5) $\operatorname{pr}_{k}{\mathfrak{X}}=\\{\operatorname{pr}_{k}X:\
X\in{\mathfrak{X}}\\}\quad\text{and}\quad\operatorname{res}_{y}{\mathfrak{X}}=\\{\operatorname{res}_{y}X:\
X\in{\mathfrak{X}},\ \operatorname{res}_{y}X\neq\varnothing\\}$

are $k$-ary coherent configurations on $\Omega$, called the _$k$ -projection_
of ${\mathfrak{X}}$, and the _residue_ of ${\mathfrak{X}}$ with respect to
$y$, respectively. Obviously,

(6)
$\operatorname{res}_{y}{\mathfrak{X}}\geq\operatorname{pr}_{k}{\mathfrak{X}}.$

For a set $X\in{\mathfrak{X}}$, the number of all $y\in X$ such that
$\operatorname{pr}_{k}(x)=\operatorname{pr}_{k}(y)$ does not depend on $x\in
X$ [6, Lemma 3.5], and is denoted by $n_{k}(X)$. Next, let $y\in\Omega^{m-k}$,
$t\in\\{1,\ldots,m-k\\}^{k}$, and $y_{k,t}=(y_{t_{1}},\ldots,y_{t_{k}})$. Then
it is easily seen that

(7) $\\{y_{k,t}\\}\in\operatorname{res}_{y}{\mathfrak{X}}.$

Let ${\mathfrak{X}}^{\prime}$ be an $m$-ary coherent configuration on
$\Omega^{\prime}$. An _isomorphism_ from ${\mathfrak{X}}$ to
${\mathfrak{X}}^{\prime}$ is a bijection
$f:\Omega^{m}\rightarrow{\Omega^{\prime}}{\phantom{x}{}^{m}}$ such that
$X^{f}\in{\mathfrak{X}}^{\prime}$ and $(X^{\sigma})^{f}=(X^{f})^{\sigma}$ for
all $X\in{\mathfrak{X}}$ and all $\sigma\in\operatorname{Mon}(M)$. An
_algebraic isomorphism_ from ${\mathfrak{X}}$ to ${\mathfrak{X}}^{\prime}$ is
a bijection $\varphi:{\mathfrak{X}}\to{\mathfrak{X}}^{\prime}$ such that

(8) $\varphi(X^{\sigma})=\varphi(X)^{\sigma}\quad\text{and}\quad
n_{X_{1},\ldots,X_{m}}^{X_{0}}=n_{\varphi(X_{1}),\ldots,\varphi(X_{m})}^{\varphi(X_{0})}$

for all $X,X_{0},\ldots,X_{m}\in{\mathfrak{X}}$ and
$\sigma\in\operatorname{Mon}(M)$222The definition of algebraic isomorphisms
given here is equivalent to Definition 7 in [6]. Again, for $m=2$, this
definition is compatible with that given in Section 2. For any $k\in M$, the
algebraic isomorphism $\varphi$ induces the algebraic isomorphism between the
$k$-projections,

(9)
$\varphi_{k}:\operatorname{pr}_{k}{\mathfrak{X}}\to\operatorname{pr}_{k}{\mathfrak{X}}^{\prime},\
\operatorname{pr}_{k}X\mapsto\operatorname{pr}_{k}\varphi(X).$

In a similar way, one can also define the $K$-projections
$\operatorname{pr}_{K}{\mathfrak{X}}$ and $\varphi_{K}$ and the numbers
$n_{K}(X)$ for any subset $K\subseteq M$. Any two tuples $y\in\Omega^{k}$ and
$y^{\prime}\in{\Omega^{\prime}}{\phantom{x}{}^{k}}$ are said to be _$\varphi$
-similar_, where $k=|K|$, if the algebraic isomorphism $\varphi_{K}$ takes
$[y]$ to $[y^{\prime}]$.

######  Lemma 2.1.

Let $\varphi:{\mathfrak{X}}\to{\mathfrak{X}}^{\prime}$ be an algebraic
isomorphism of $m$-ary coherent configurations, $k\in M$, and let $y$ and
$y^{\prime}$ be $\varphi$-similar $(m-k)$-tuples. Then the mapping

(10)
$\varphi_{yy^{\prime}}:\operatorname{res}_{y}{\mathfrak{X}}\to\operatorname{res}_{y^{\prime}}{\mathfrak{X}}^{\prime},\
\operatorname{res}_{y}X\mapsto\operatorname{res}_{y^{\prime}}\varphi(X)$

is an algebraic isomorphism extending $\varphi_{k}$. Moreover,
$\varphi_{yy^{\prime}}$ takes $\\{y_{k,t}\\}$ to $\\{y^{\prime}_{k,t}\\}$ for
all $t\in\\{1,\ldots,m-k\\}^{k}$.

###### Proof.

The first part of the statement was proved in [17, Lemma 3.6]. To prove the
second statement, let $x=y_{k,t}\cdot y$ and $X=[x]$. Then
$\operatorname{res}_{y}X=\\{y_{k,t}\\}$, see formula (7). In accordance with
[17, formula (10)], we have $\rho(X)=\rho(\varphi(X))$. Therefore,

$\varphi(X)=\\{z^{\prime}_{k,t}\cdot z^{\prime}:\
z^{\prime}\in\operatorname{pr}_{K^{\prime}}\varphi(X)\\},$

where $K^{\prime}=\\{k+1,\ldots,m\\}$. Since $y$ and $y^{\prime}$ are
$\varphi$-similar, we have
$y^{\prime}\in\operatorname{pr}_{K^{\prime}}\varphi(X)$. Therefore the set
$\operatorname{res}_{y^{\prime}}\varphi(X)$ contains $y^{\prime}_{k,t}$ and
hence coincides with the singleton $\\{y^{\prime}_{k,t}\\}$. Thus,

$\varphi_{yy^{\prime}}(\\{y_{k,t}\\})=\varphi_{yy^{\prime}}(\operatorname{res}_{y}X)=\operatorname{res}_{y^{\prime}}\varphi(X)=\\{y^{\prime}_{k,t}\\},$

as required. ∎

##  3\. The $m$-dim Weifeiler-Leman algorithm

###  3.1. The Weisfeiler-Leman algorithm

Let ${\cal X}=(\Omega,S)$ be a rainbow and ${\mathfrak{C}}$ a linear ordered
set. Any injective mapping $c:S\to{\mathfrak{C}}$ is called a _coloring_ of
${\cal X}$. The element $c(\alpha,\beta):=c(r(\alpha,\beta))$ is called the
_color_ of the pair $(\alpha,\beta)$ as well of the relation
$r(\alpha,\beta)$. A rainbow equipped with a coloring is said to be _colored_.
An isomorphism $f:{\cal X}\to{\cal X}^{\prime}$ of colored rainbows with
colorings $c$ and $c^{\prime}$ is an ordinary isomorphism that preserves the
colorings, i.e., $c^{\prime}(s^{f})=c(s)$ for all $s\in S$.

Let $m\geq 2$. For a given colored rainbow ${\cal X}$, the $m$-dimensional
Weisfeiler-Leman algorithm $\operatorname{WL}_{m}$ constructs a certain
coloring $c(m,{\cal X})$ of the set $\Omega^{m}$. At the first stage, an
initial coloring $c_{0}=c_{0}(m,{\cal X})$ of $\Omega^{m}$ is constructed from
a coloring $c^{\prime}$ defined by the following condition: given
$x,y\in\Omega^{m}$, we have $c^{\prime}(x)=c^{\prime}(y)$ if and only if
$\rho(x)=\rho(y)$ and

(11) $c(x_{i},x_{j})=c(y_{i},y_{j})\quad\text{ for all }i,j\in M,$

where $c$ is the coloring of the rainbow ${\cal X}$. Namely, the color
$c_{0}(x)$ of every $x$ is set to be the tuple
$(c^{\prime}(x^{\sigma}))_{\sigma\in\operatorname{Mon}(M)}$.

Starting from the second stage, the initial coloring is refined step by step.
Namely, if $c_{i}$ is the coloring constructed at the $i$th step ($i\geq 0$),
then the color of an $m$-tuple $x$ in the coloring $c_{i+1}$ is defined to be

$c_{i+1}(x)=(c_{i}(x),\\{\\{(c_{i}(x_{1\leftarrow\alpha}),\ldots,c_{i}(x_{m\leftarrow\alpha})):\
\alpha\in\Omega\\}\\}),$

where $\\{\\{\cdot\\}\\}$ denotes a multiset. The algorithm stops when
$|\operatorname{im}(c_{i})|=|\operatorname{im}(c_{i+1})|$ and the final
coloring $c(m,{\cal X})$ is set to be $c_{i}$.

The color classes of the coloring $c(m,{\cal X})$ form an $m$-ary coherent
configuration denoted below by $\operatorname{WL}_{m}({\cal X})$. It is equal
to the $m$-ary coherent closure $\operatorname{WL}_{m}({\mathfrak{X}}_{0})$ of
the partition ${\mathfrak{X}}_{0}$ consisting of the color classes of the
coloring $c_{0}(m,{\cal X})$. It is important to note that this fact enables
us to define the $m$-ary coherent configuration $\operatorname{WL}_{m}({\cal
X})$ also for any uncolored rainbow ${\cal X}$. It was observed in [8] (see
also [7]) that the mapping

$\operatorname{pr}_{2}\operatorname{WL}_{m}:{\cal
X}\mapsto\operatorname{pr}_{2}\operatorname{WL}_{m}({\cal X})$

is a closure operator taking the rainbows on $\Omega$ to the coherent
configurations on $\Omega$, and, moreover, that for all $2\leq k\leq m$, we
have

(12)
$\operatorname{pr}_{2}\operatorname{WL}_{k}(\operatorname{pr}_{2}\operatorname{WL}_{m}({\cal
X}))=\operatorname{pr}_{2}\operatorname{WL}_{m}({\cal X}).$

In what follows we also need the lemma below.

######  Lemma 3.1.

Let ${\cal X}$ be a rainbow on $\Omega$, $m\geq 3$, and
${\mathfrak{X}}=\operatorname{WL}_{m}({\cal X})$. Then for any tuple
$y\in\Omega^{m-2}$,

$\operatorname{res}_{y}{\mathfrak{X}}\geq(\operatorname{pr}_{2}{\mathfrak{X}})_{y}.$

###### Proof.

Formula (6) for $k=2$ implies that
$\operatorname{res}_{y}{\mathfrak{X}}\geq\operatorname{pr}_{2}{\mathfrak{X}}\geq{\cal
X}$. Next, from formula (7), it follows that for all $i\in\\{1,\ldots,m-k\\}$,
the singleton $\\{1_{y_{i}}\\}=\\{y_{2,t_{i}}\\}$ with $t_{i}=(i,i)$ is a
class of the coherent configuration $\operatorname{res}_{y}{\mathfrak{X}}$.
Thus,

$\operatorname{res}_{y}{\mathfrak{X}}\geq\operatorname{WL}(\operatorname{pr}_{2}{\mathfrak{X}},T_{y})=(\operatorname{pr}_{2}{\mathfrak{X}})_{y},$

where $T_{y}=\\{1_{y_{1}},\ldots,1_{y_{m-2}}\\}$. ∎

The coherent configuration $\operatorname{pr}_{2}\operatorname{WL}_{m}({\cal
X})$ can naturally be treated as a colored rainbow in which the color of $s\in
S$ is defined to be the minimum of the colors $c(X)$, where $c=c(m,{\cal X})$
and $X$ is a class of $\operatorname{WL}_{m}({\cal X})$ such that
$\operatorname{pr}_{2}X=s$. This colored rainbow is canonical in the sense
that every color preserving isomorphism from ${\cal X}$ to ${\cal X}^{\prime}$
is also a color preserving isomorphism from
$\operatorname{pr}_{2}\operatorname{WL}_{m}({\cal X})$ to
$\operatorname{pr}_{2}\operatorname{WL}_{m}({\cal X}^{\prime})$ .

An uncolored rainbow ${\cal X}$ is said to be _$\operatorname{WL}_{m}$
-equivalent_ to an uncolored rainbow ${\cal X}^{\prime}$ with respect to a
similarity $\varphi:{\cal X}\to{\cal X}^{\prime}$ if there exists an algebraic
isomorphism $\hat{\varphi}:\operatorname{WL}_{m}({\cal
X})\to\operatorname{WL}_{m}({\cal X}^{\prime})$ such that the $2$-projection
$\hat{\varphi}_{2}$ of $\hat{\varphi}$ extends $\varphi$. We say that the
$m$-dim WL _identifies_ the rainbow ${\cal X}$ if for every rainbow ${\cal
X}^{\prime}$, every similarity $\varphi:{\cal X}\to{\cal X}^{\prime}$ such
that ${\cal X}$ and ${\cal X}^{\prime}$ are
$\operatorname{WL}_{m}$-equivalent, is induced by an isomorphism. The
_$\operatorname{WL}$ -dimension_
$\dim_{\scriptscriptstyle\operatorname{WL}}({\cal X})$ of the rainbow ${\cal
X}$ is defined to be the smallest positive integer $m$ such that the $m$-dim
WL identifies ${\cal X}$.

###  3.2. Rainbows and graphs

An undirected loopless graph ${\cal G}$ can be treated as a colored rainbow.
Indeed, let $\Omega$ and $E$ be the vertex and edge set of ${\cal G}$,
respectively. Denote by ${\cal X}({\cal G})$ the colored rainbow on $\Omega$,
that has exactly three basis relations, namely, $1_{\Omega}$, $E$, and the
edge set of the complement of ${\cal G}$, that are colored in the colors $0$,
$1$, and $2$, respectively. This can easily be extended to vertex colored
graphs ${\cal G}$ if one replaces $1_{\Omega}$ by relations $1_{\Delta}$,
where $\Delta$ runs over the color classes of ${\cal G}$.

In accordance with above definitions, two vertex colored graphs ${\cal G}$ and
${\cal G}^{\prime}$ are isomorphic if and only if so are the colored rainbows
${\cal X}={\cal X}({\cal G})$ and ${\cal X}^{\prime}={\cal X}({\cal
G}^{\prime})$. Moreover, if ${\cal G}$ and ${\cal G}^{\prime}$ are of the same
order, then there is a unique color preserving mapping $\varphi:S({\cal X})\to
S({\cal X}^{\prime})$, and $\varphi$ is a similarity from ${\cal X}$ to ${\cal
X}^{\prime}$, called a _standard_ one.

In this terminology, the $m$-dim WL does not distinguish the graphs ${\cal G}$
and ${\cal G}^{\prime}$ in the sense of [12] if and only if the (uncolored)
rainbows ${\cal X}$ and ${\cal X}^{\prime}$ are
$\operatorname{WL}_{m}$-equivalent with respect to the standard similarity
$\varphi$. Indeed, the “only if” part is an immediate consequence of the fact
that the mapping

(13) $\hat{\varphi}:\operatorname{WL}_{m}({\cal
X})\to\operatorname{WL}_{m}({\cal X}^{\prime}),\
X\mapsto{c^{\prime}}{\phantom{x}{}^{-1}}(c(X))$

is an algebraic isomorphism such that the $2$-projection $\hat{\varphi}_{2}$
of $\widehat{\varphi}$ extends the algebraic isomorphism $\varphi$, where
$c=c(m,{\cal X})$ and $c^{\prime}=c(m,{\cal X}^{\prime})$. Conversely, assume
that the rainbows ${\cal X}$ and ${\cal X}^{\prime}$ are
$\operatorname{WL}_{m}$-equivalent with respect to $\varphi$. Then there is an
algebraic isomorphism $\hat{\varphi}:\operatorname{WL}_{m}({\cal
X})\to\operatorname{WL}_{m}({\cal X}^{\prime})$ such that $\hat{\varphi}_{2}$
extends $\varphi$. The last condition implies that
$\hat{\varphi}({\mathfrak{X}}_{0})={\mathfrak{X}}^{\prime}_{0}$ and the
equality

$c_{i}(X)=c^{\prime}_{i}(\hat{\varphi}(X))$

holds for $i=0$ and all $X\in{\mathfrak{X}}_{0}$. By induction on $i$, this
equality holds for all $i\geq 0$. Therefore the $m$-dim WL does not
distinguish the graphs ${\cal G}$ and ${\cal G}^{\prime}$.

Let ${\cal G}$ be a vertex colored graph. It is not difficult to verify that
the $m$-dim WL _identifies_ ${\cal G}$ in the sense of [12] if and only if the
$m$-dim WL identifies the uncolored rainbow ${\cal X}({\cal G})$, and the
$\operatorname{WL}$-dimension of ${\cal G}$ equals
$\dim_{\scriptscriptstyle\operatorname{WL}}({\cal X})$.

###  3.3. The Cai-Fürer-Immerman theorem

Let us recall (very briefly) the definition of the
${\mathscr{C}}_{m}$-pebbling game [4]. We describe it as a pebbling game
${\mathscr{C}}_{m}(\varphi)$ for two rainbows ${\cal X}$ and ${\cal
X}^{\prime}$ and a similarity $\varphi:{\cal X}\to{\cal X}^{\prime}$.

There are two players, called Spoiler and Duplicator, and $m$ pairwise
distinct pebbles, each given in duplicate. The game consists of rounds and
each round consists of two parts. At the first part, Spoiler chooses a set
$A^{\prime}$ of points in ${\cal X}$ or in ${\cal X}^{\prime}$. Duplicator
responds with a set $A$ in the other rainbow, such that $|A|=|A^{\prime}|$ (if
this is impossible, then Duplicator loses). At the second part, Spoiler places
one of the pebbles333It is allowed to move previously placed pebbles to other
vertices and place more than one pebble on the same vertex. on a point in $A$.
Duplicator responds by placing the copy of the pebble on some point of
$A^{\prime}$.

The configuration after a round is determined by a bijection
$f:\Delta\to\Delta^{\prime}$, where $\Delta\subseteq\Omega$ (respectively,
$\Delta^{\prime}\subseteq\Omega^{\prime}$) is the set of points in ${\cal X}$
(respectively, in ${\cal X}^{\prime}$), covered by pebbles, and any two points
$\alpha\in\Delta$ and $f(\alpha)\in\Delta^{\prime}$ are covered by the copies
of the same pebble. Duplicator wins the round if

$(s_{\Delta})^{f}=\varphi(s)_{\Delta^{\prime}}$

for all $s\in S$ such that $s_{\Delta}\neq\varnothing$; in the other words,
the bijection $f$ induces the isomorphism between the rainbows ${\cal
X}_{\Delta}$ and ${\cal X}^{\prime}_{\Delta^{\prime}}$, that respects the
similarity $\varphi$. Spoiler wins if Duplicator does not win.

The game starts from an initial configuration (which is considered as the
configuration after zero rounds), i.e., a pair
$(x,x^{\prime})\in\Omega^{k}\times{\Omega^{\prime}}{\phantom{x}{}^{k}}$ for
which $k\leq m$ and the points $x_{i}$ and $x^{\prime}_{i}$ are covered with
copies of the same pebble, $i=1,\ldots,k$. We say that Duplicator has a
winning strategy for the game ${\mathscr{C}}_{m}(\varphi)$ on ${\cal X}$ and
${\cal X}^{\prime}$ with initial configuration $(x,x^{\prime})$ if, regardless
of Spoiler’s actions, Duplicator wins after any number of rounds (for
appropriate selections of the sets $A^{\prime}$ and points in $A$).

Notation. $T^{m}_{\varphi}({\cal X},{\cal X}^{\prime})$ is the set of all
pairs $(x,x^{\prime})\in\Omega^{m}\times{\Omega^{\prime}}{\phantom{x}{}^{m}}$
such that Duplicator has a winning strategy in the pebble game
${\mathscr{C}}_{m+1}(\varphi)$ on ${\cal X}$ and ${\cal X}^{\prime}$ with
initial configuration $(x,x^{\prime})$.

One of the main results proved in [4] is the equivalence
$(1)\Leftrightarrow(3)$ in Theorem 5.2 there; it gives a characterization of
the set $T^{m}_{\varphi}({\cal X},{\cal X}^{\prime})$ in terms of the final
colors of the $m$-ary coherent configurations
${\mathfrak{X}}=\operatorname{WL}_{m}({\cal X})$ and
${\mathfrak{X}}^{\prime}=\operatorname{WL}_{m}({\cal X}^{\prime})$. In our
notation, it can be stated as follows:

(14) $(x,x^{\prime})\in T^{m}_{\varphi}({\cal X},{\cal
X}^{\prime})\quad\Leftrightarrow\quad c(m,{\cal X})(x)=c(m,{\cal
X}^{\prime})(x^{\prime})$

for all
$(x,x^{\prime})\in\Omega^{m}\times{\Omega^{\prime}}{\phantom{x}{}^{m}}$. The
lemma below is an easy consequence of this relation.

######  Lemma 3.2.

Let ${\cal X}$ and ${\cal X}^{\prime}$ be rainbows and
$\hat{\varphi}:\operatorname{WL}_{m}({\cal X})\to\operatorname{WL}_{m}({\cal
X}^{\prime})$ a bijection such that
$\varphi:=\operatorname{pr}_{2}(\hat{\varphi})$ takes $S$ to $S^{\prime}$.
Then

  1. (1)

if $\hat{\varphi}$ is an algebraic isomorphism, then
$\hat{\varphi}([x])=[x^{\prime}]$ for all $x\in\Omega^{m}$ and all
$x^{\prime}\in{\Omega^{\prime}}{\phantom{x}{}^{m}}$ such that
$(x,x^{\prime})\in T^{m}_{\varphi}({\cal X},{\cal X}^{\prime})$,

  2. (2)

if $[x]\times\hat{\varphi}([x])\subseteq T^{m}_{\varphi}({\cal X},{\cal
X}^{\prime})$ for all $x\in\Omega^{m}$, then $\hat{\varphi}$ is an algebraic
isomorphism.

###### Proof.

Assume that $\hat{\varphi}$ is an algebraic isomorphism. Then it is uniquely
determined from the condition on its $2$-projection, and hence coincides with
algebraic isomorphism (13). Thus the first statement follows from formula
(14). To prove the second statement, it suffices to note that the assumption
and formula (14) imply that the final colors of the classes $[x]$ and
$\hat{\varphi}([x])$ are the same for all $x\in\Omega^{m}$. Consequently, the
mapping $\hat{\varphi}$ coincides with algebraic isomorphism (13). ∎

##  4\. Deep stabilization in the sense of Weisfeiler

###  4.1. A general scheme

In this subsection, we discuss the concept of the deep stabilization proposed
by B. Weisfeiler in [18, Section O]. In accordance with the remark made by him
at page VII, all definitions, constructions and algorithms of that section
should be attributed to Weisfeiler himself. It should be noted that the terms
“graph” and “stationary graph” used there correspond in our terminology to the
structures satisfying condition (C1) and coherent configurations,
respectively. In both cases the set $S$ of basis relations is assumed to be
linear ordered and the corresponding order can naturally be interpreted as a
coloring of $\Omega^{2}$.

One of primary goals for Weisfeiler was to find an efficicent algorithm that
given a coherent configuration ${\cal X}$ constructs either a certificate for
the equality ${\cal X}=\operatorname{Inv}(\operatorname{Aut}({\cal X}))$ or a
canonical coherent configuration ${\cal X}^{\prime}>{\cal X}$ such that

$F({\cal X}^{\prime})=\operatorname{Orb}(\operatorname{Aut}({\cal X}));$

if the algorithm was polynomial-time, then one would obviously solve the graph
isomorphism problem. To this end, he proposed an algorithm
$\operatorname{W}_{m}$ of deep stabilization that, given an integer $m\geq 1$,
called the depth, recursively constructs a canonical coherent configuration
$\operatorname{W}_{m}({\cal X})\geq{\cal X}$ the automorphism group of which
coincides with $\operatorname{Aut}({\cal X})$. Though it was not written
explicitly, it is not hard to see that

${\cal X}\leq\operatorname{W}_{1}({\cal
X})\leq\ldots\leq\operatorname{W}_{m}({\cal X})=\operatorname{W}_{m+1}({\cal
X})=\ldots=\operatorname{Inv}(\operatorname{Aut}({\cal X}))$

for some $m\leq n$. It follows that the stabilization of sufficiently large
depth is sufficient to identify a given graph up to isomorphism.

The exact definition444It appears in Subsection 6.1 of [18, Chapter O], the
two other possible definitions (in Subsections 6.2 and 6.3) are not given in
detail. of the _depth- $m$ stabilization_ $\operatorname{W}_{m}$ is recursive
and requires an auxiliary algorithm $\sigma$ that given a coherent
configuration ${\cal X}$ on $\Omega$, and a family

${\mathfrak{F}}=\\{{\cal Y}^{\alpha}:\ \alpha\in\Omega\\}$

of the coherent configurations ${\cal Y}^{\alpha}$ on $\Omega$, constructs a
new coherent configuration $\sigma({\cal X},{\mathfrak{F}})\geq{\cal X}$. The
coherent configurations ${\cal Y}^{\alpha}$ should be “invariant” in some
natural sense to provide the equality $\operatorname{Aut}(\sigma({\cal
X},{\mathfrak{F}}))=\operatorname{Aut}({\cal X})$. In the case of the
depth-$m$ stabilization, one takes ${\cal Y}^{\alpha}={\cal X}_{\alpha}$ at
the first step of the recursion and defines the coherent configuration
$\operatorname{W}_{m}({\cal X})$ as follows:

$\operatorname{W}_{m}({\cal X})=\begin{cases}\sigma({\cal X},\\{{\cal
X}_{\alpha}:\ \alpha\in\Omega\\})&\text{if $m=1$,}\\\ \sigma({\cal
X},\\{\operatorname{W}_{m-1}({\cal X}_{\alpha}):\ \alpha\in\Omega\\})&\text{if
$m>1$,}\\\ \end{cases}$

where ${\cal X}_{\alpha}$ is the $\alpha$-extension of ${\cal X}$ with
canonically ordered basis relations. Thus the algorithm
$\operatorname{W}=\operatorname{W}_{1}$ of the _depth- $1$ stabilization_
consists in refining the coherent configuration ${\cal X}$ with the help of
the algorithm $\sigma$ applied for the family ${\mathfrak{F}}$ of the coherent
configurations ${\cal Y}^{\alpha}={\cal X}_{\alpha}$.

###  4.2. The depth-$1$ stabilization

We begin with a notation. Given two pairs $x,y\in\Omega^{2}$, denote by
$n_{y}(x)$ the number of all pairs $y^{\prime}$ for which $x\cdot y\sim x\cdot
y^{\prime}$, see formula (3). Clearly, $n_{y}(x)\geq 1$. When
$y=(\alpha,\alpha)$, we abbreviate $n_{\alpha}(x):=n_{y}(x)$.

Let $I=\\{1,\ldots,4\\}$ and $i\in I$. Based on the above notation, we define
a binary relation
$\stackrel{{\scriptstyle\scriptscriptstyle{{}_{i}}}}{{\sim}}$ on the points
(if $i=1$) or on the pairs of points (if $i\neq 1$) of the coherent
configuration ${\cal X}$:

(1)
$\alpha\stackrel{{\scriptstyle\scriptscriptstyle{{}_{1}}}}{{\sim}}\alpha^{\prime}\
\Leftrightarrow\ \operatorname{id}_{\cal X}$ has the
$\alpha\alpha^{\prime}$-extension,
(2) $x\stackrel{{\scriptstyle\scriptscriptstyle{{}_{2}}}}{{\sim}}x^{\prime}\
\Leftrightarrow\ r(x)=r(x^{\prime})$ and for each $\alpha$ there is
$\alpha^{\prime}$ such that $n_{\alpha}(x)=n_{\alpha^{\prime}}(x^{\prime})$,
(3) $x\stackrel{{\scriptstyle\scriptscriptstyle{{}_{3}}}}{{\sim}}x^{\prime}\
\Leftrightarrow\ \operatorname{id}_{\cal X}$ has the $xx^{\prime}$-extension,
(4) $x\stackrel{{\scriptstyle\scriptscriptstyle{{}_{4}}}}{{\sim}}x^{\prime}\
\Leftrightarrow\
x\stackrel{{\scriptstyle\scriptscriptstyle{{}_{3}}}}{{\sim}}x^{\prime}$ and
for each $y$ there is $y^{\prime}$ such that
$n_{y}(x)=n_{y^{\prime}}(x^{\prime})$.

It should be noted that the equivalence relations
$\stackrel{{\scriptstyle\scriptscriptstyle{{}_{3}}}}{{\sim}}$ and
$\stackrel{{\scriptstyle\scriptscriptstyle{{}_{4}}}}{{\sim}}$ are finer than,
respectively, $\stackrel{{\scriptstyle\scriptscriptstyle{{}_{1}}}}{{\sim}}$
and $\stackrel{{\scriptstyle\scriptscriptstyle{{}_{2}}}}{{\sim}}$ (take
$x=(\alpha,\alpha)$ and $x^{\prime}=(\alpha^{\prime},\alpha^{\prime})$). The
reason we consider four equivalence relations instead of two is to bring our
interpretation of the Weisfeiler algorithm closer to the original algorithm.

It is easily seen that (a)
$\stackrel{{\scriptstyle\scriptscriptstyle{{}_{1}}}}{{\sim}}$ is an
equivalence relation on $\Omega$, each class of which is contained in some
fiber of ${\cal X}$, and (b) if $i\neq 1$, then
$\stackrel{{\scriptstyle\scriptscriptstyle{{}_{i}}}}{{\sim}}$ is an
equivalence relation on $\Omega^{2}$, each class of which is contained in some
basis relation of ${\cal X}$. The set of classes of each equivalence relation
$\stackrel{{\scriptstyle\scriptscriptstyle{{}_{i}}}}{{\sim}}$ can naturally be
treated as a (canonically) linear ordered family of binary relations (for
$i=1$, one can take the corresponding reflexive relations). Denote this family
by $T_{i}$ and put

(15) $\sigma_{i}({\cal X})=\operatorname{WL}({\cal X},T_{i}),\qquad i\in I.$

It is not hard to see (and this was also done in [18, Section O]) that
$\sigma_{i}({\cal X})\geq{\cal X}$ and $\operatorname{Aut}({\cal
X})=\operatorname{Aut}(\sigma_{i}({\cal X}))$ for each $i$.

Now we are ready to describe the depth-$1$ stabilization. Namely, the
algorithm $\operatorname{W}$ consists in successive stabilization of the input
coherent configuration ${\cal X}$ with the help of auxiliary subroutines
$\sigma_{i}$, $i\in I$, computing the coherent closure (15) by using ordinary
Weisfeiler-Leman algorithm. More precisely, the coherent configuration
$\operatorname{W}({\cal X})$ is the output of the following procedure

(16) $\text{{\bf while }}{\cal X}<\sigma_{i}({\cal X})\text{ for some }i\in
I\text{ {\bf do} }{\cal X}:=\sigma_{i}({\cal X})\text{ {\bf od}}$

It should be noted that our description differs somewhat from Weisfeiler’s,
since he represented coherent configurations as matrices whose elements are
(pairwise non-commuting) variables; in particular, the relation
$\stackrel{{\scriptstyle\scriptscriptstyle{{}_{i}}}}{{\sim}}$ was not
calculated explicitly, but was presented implicitly, in the form of equalities
of the coefficients of some polynomials in these variables.

Some properties of the coherent configurations closed with respect to the
depth-$1$ stabilization are proved in [18, Chapters O and P]. It was
emphasized by Weisfeiler that all of them are already fulfilled for those
${\cal X}$ for which $\sigma_{1}({\cal X})=\sigma_{2}({\cal X})={\cal X}$. A
characterization of the coherent configurations satisfying the latter
condition follows from Lemma 7.1 and Theorem 1.2 to be proved in the
subsequent sections.

Summarizing the above, we note a difference between the Weisfeiler deep
stabilization algorithm and the modern multidimensional Weisfeiler-Leman
algorithm. Namely, the first one does not construct an explicit coloring of
the Cartesian power of the underlying set (although such a coloring can easily
be defined, see Section 6). The increase in depth is achieved by using a
recursion followed by the application of the ordinary ($2$-dimensional)
Weisfeiler-Leman algorithm.

##  5\. Sesquiclosed coherent configurations and sesquiclosure

In accordance with [17], a coherent configuration ${\cal X}=(\Omega,S)$ is
said to be _sesquiclosed_ if the following two conditions are satisfied for
all $\alpha,\alpha^{\prime}\in\Omega$:

  1. (S1)

$F({\cal X}_{\alpha})=\\{\alpha s:\ s\in S,\ \alpha s\neq\varnothing\\}$,

  2. (S2)

if $\alpha$ and $\alpha^{\prime}$ belong to the same fiber of ${\cal X}$, then
$\alpha\stackrel{{\scriptstyle\scriptscriptstyle{{}_{1}}}}{{\sim}}\alpha^{\prime}$.

The conditions (S1) and (S2) are independent. Indeed, if ${\cal G}$ and ${\cal
G}^{\prime}$ are the Payley and Piesert graphs (see [15]) of the same
sufficiently large order, then the coherent configuration of their disjoint
union ${\cal G}\cup{\cal G}^{\prime}$ is homogeneous. It satisfies condition
(S1), because both ${\cal G}$ and ${\cal G}^{\prime}$ are rank $3$ graphs, and
it does not satisfy condition (S2), because any one-point extension of
$\operatorname{WL}({\cal G})$ is separable (see the proof of [16, Theorem
1.1]) and hence the identity algebraic isomorphism $\operatorname{id}_{\cal
X}$ has no the $\alpha\alpha^{\prime}$-extension, where $\alpha$ is a vertex
of ${\cal G}$ and $\alpha^{\prime}$ is a vertex of ${\cal G}^{\prime}$.

Now, let ${\cal X}$ be the scheme of the Shrikhande graph, see e.g. [5,
Example 2.6.17]. This scheme has transitive automorphism group and hence
satisfies condition (S2). On the other hand, ${\cal X}$ is a scheme of rank
$3$, and a straightforward computation shows that any one-point extension of
${\cal X}$ has exactly $4$ fibers. Thus, ${\cal X}$ cannot satisfy condition
(S1).

######  Theorem 5.1.

The intersection of any two sesquiclosed coherent configurations is
sesquiclosed.

###### Proof.

Let ${\cal Y}$ be the intersection of sesquiclosed coherent configurations
${\cal X}$ and ${\cal X}^{\prime}$. To prove that ${\cal Y}$ satisfies
condition (S2), let $\Delta\in F({\cal Y})$. Note that $\Delta$ is a union of
some classes of the equivalence relation
$\stackrel{{\scriptstyle\scriptscriptstyle{{}_{1}}}}{{\sim}}$ defined for the
coherent configuration ${\cal Y}$. Take any such class $\Delta^{\prime}$. Then
condition (S2) is satisfied for all
$\alpha,\alpha^{\prime}\in\Delta^{\prime}$, and we are done if
$\Delta^{\prime}=\Delta$. Suppose that $\Delta^{\prime}\subsetneq\Delta$. Then
$\Delta^{\prime}$ is not a homogeneity set of either ${\cal X}$ or ${\cal
X}^{\prime}$. By symmetry, we may assume that the former holds. Since
$\Delta\in F({\cal Y})\subseteq F({\cal X})^{\cup}$, there are a fiber
$\Gamma\in F({\cal X}_{\Delta})$ and points

$\alpha\in\Gamma\setminus\Delta^{\prime}\quad\text{and}\quad\alpha^{\prime}\in\Gamma\cap\Delta^{\prime}.$

In view of condition (S2), the algebraic automorphism $\operatorname{id}_{\cal
X}$ has the $\alpha\alpha^{\prime}$-extension. Its restriction to ${\cal
Y}_{\alpha}\leq{\cal X}_{\alpha}$ yields the $\alpha\alpha^{\prime}$-extension
of the algebraic automorphism $\operatorname{id}_{\cal Y}$. It follows that
$\alpha\stackrel{{\scriptstyle\scriptscriptstyle{{}_{1}}}}{{\sim}}\alpha^{\prime}$
and hence $\alpha\in\Delta^{\prime}$, a contradiction.

Let $\alpha\in\Omega$ and $s\in S({\cal Y})$ be such that $\alpha
s\neq\varnothing$. Then there are $\Delta,\Gamma\in F({\cal Y})$ such that
$\alpha\in\Delta$ and $s\subseteq\Delta\times\Gamma$. Since $\alpha s$ is a
homogeneity set of the coherent configuration ${\cal Y}_{\alpha}$, there is
$\Gamma_{\alpha}\in F({\cal Y}_{\alpha})$ such that

(17) $\Gamma_{\alpha}\subseteq\alpha s\subseteq\Gamma.$

By the above paragraph, ${\cal Y}$ satisfies condition (S2). Hence the
algebraic automorphism $\operatorname{id}_{\cal Y}$ has the
$\alpha\beta$-extension $\varphi_{\beta}$ for each $\beta\in\Delta$ (this
extension is identity if $\beta=\alpha$). Then
$\Gamma_{\beta}:=(\Gamma_{\alpha})^{\varphi_{\beta}}$ is a fiber of ${\cal
Y}_{\beta}$. In view of (17), we have

(18) $\Gamma_{\beta}=(\Gamma_{\alpha})^{\varphi_{\beta}}\subseteq(\alpha
s)^{\varphi_{\beta}}=\beta s^{\varphi_{\beta}}=\beta s\subseteq\Gamma.$

We claim that the union $r$ of all relations $\\{\beta\\}\times\Gamma_{\beta}$
with $\beta\in\Delta$, belongs to the set
$S^{\cup}\,\cap\,{S^{\prime}}{\phantom{x}{}^{\cup}}=S({\cal Y})^{\cup}$. Let
us verify that $r\in S^{\cup}$; similarly, one can verify that
$r\in{S^{\prime}}{\phantom{x}{}^{\cup}}$. Since ${\cal X}_{\alpha}\geq{\cal
Y}_{\alpha}$, there is $r_{\alpha}\in S^{\cup}$ such that
$\Gamma_{\alpha}=\alpha r_{\alpha}$. By condition (S2), the algebraic
automorphism $\operatorname{id}_{\cal X}$ has the $\alpha\beta$-extension
$\varphi_{\alpha\beta}$ for each $\beta\in\Delta$. Since it extends
$\varphi_{\beta}$, we have

$\Gamma_{\beta}=(\Gamma_{\alpha})^{\varphi_{\beta}}=(\Gamma_{\alpha})^{\varphi_{\alpha\beta}}=(\alpha
r_{\alpha})^{\varphi_{\alpha\beta}}=\beta r_{\alpha}.$

Thus $r$ is equal to the union of all relations $\\{\beta\\}\times\beta
r_{\alpha}$, $\beta\in\Delta$, which is in its turn is equal to
$1_{\Delta}\cdot r_{\alpha}\in S^{\cup}$.

From the claim, it follows that $r$ is a relation of ${\cal Y}$. Moreover,
$r\subseteq\Delta\times\Gamma$ by formula (18). Since $\alpha s\supseteq\alpha
r$, we obtain $s=r$. Thus,

$\alpha s=\alpha r=\Gamma_{\alpha}\in F({\cal Y}_{\alpha}),$

as required. ∎

Let ${\cal X}$ be a rainbow on $\Omega$. At least one coherent configuration
larger than or equal to ${\cal X}$ is sesquiclosed, e.g., the discrete one.
Denote by $\operatorname{W_{1/2}}({\cal X})$ the intersection of all
sesquiclosed coherent configurations larger than or equal to ${\cal X}$.555It
will be clear from Lemma 7.1 that the coherent configuration
$\operatorname{W_{1/2}}({\cal X})$ is obtained after applying “half” of the
depth-$1$ stabilization algorithm $\operatorname{W}$. By Theorem 5.1, the
coherent configuration $\operatorname{W_{1/2}}({\cal X})$ is sesquiclosed and
we call it the _sesquiclosure_ of ${\cal X}$. The mapping ${\cal
X}\mapsto\operatorname{W_{1/2}}({\cal X})$ defines a closure operator on the
set of all rainbows on the same set. The following lemma shows that the
sesquiclosure is not more powerful than the closure defined by the $3$-dim WL.

######  Lemma 5.2.

For every rainbow ${\cal X}$, the coherent configuration
$\operatorname{pr}_{2}\operatorname{WL}_{3}({\cal X})$ is sesquiclosed. In
particular, $\operatorname{W_{1/2}}({\cal
X})\leq\operatorname{pr}_{2}\operatorname{WL}_{3}({\cal X})$.

###### Proof.

Put ${\mathfrak{X}}=\operatorname{WL}_{3}({\cal X})$; in particular,
$\operatorname{pr}_{2}\operatorname{WL}_{3}({\cal
X})=\operatorname{pr}_{2}{\mathfrak{X}}$. Let $\alpha\in\Omega$ and
$y=(\alpha)$ a $1$-tuple. The residue $\operatorname{res}_{y}{\mathfrak{X}}$
of the $3$-ary coherent configuration ${\mathfrak{X}}$ with respect to $y$ is
a coherent configuration on $\Omega$, and by Lemma 3.1 (for $m=3$),

(19)
$\operatorname{res}_{y}{\mathfrak{X}}\geq(\operatorname{pr}_{2}{\mathfrak{X}})_{\alpha}.$

Let $s$ be a basis relation of the coherent configuration
$\operatorname{pr}_{2}{\mathfrak{X}}$. Then there is a class
$X\in{\mathfrak{X}}$ such that $\operatorname{pr}_{2}X=s$. Without loss of
generality, we may assume that $X$ consists of the triples
$(\beta,\gamma,\beta)$ with $(\beta,\gamma)\in s$. Now if $\alpha
s\neq\varnothing$, then

$\\{\alpha\\}\times\alpha
s=\operatorname{pr}_{2}X\,\cap\,\operatorname{res}_{y}X=\operatorname{res}_{y}X.$

Consequently, $\\{\alpha\\}\times\alpha s$ is a basis relation of the coherent
configuration $\operatorname{res}_{y}{\mathfrak{X}}$. It follows that $\alpha
s$ is a fiber of it. Since $\alpha s$ is a homogeneity set of
$(\operatorname{pr}_{2}{\mathfrak{X}})_{\alpha}$, condition (S1) follows from
(19). This proves that the coherent configuration
$\operatorname{pr}_{2}{\mathfrak{X}}$ satisfies condition (S1).

Let $\alpha,\alpha^{\prime}\in\Omega$ belong to the same fiber of the coherent
configuration $\operatorname{pr}_{2}{\mathfrak{X}}$. Then the $1$-tuples
$y=(\alpha)$ and $y^{\prime}=(\alpha^{\prime})$ lie in the same class of the
partition $\operatorname{pr}_{1}{\mathfrak{X}}$. By Lemma 2.1 for $m=3$,
$k=2$, and $\varphi=\operatorname{id}_{\mathfrak{X}}$, the algebraic
automorphism (10) extends the identity algebraic automorphism of
$\operatorname{pr}_{2}{\mathfrak{X}}$ and takes the singleton
$\\{1_{\alpha}\\}\in\operatorname{res}_{y}{\mathfrak{X}}$ to the singleton
$\\{1_{\alpha^{\prime}}\\}\in\operatorname{res}_{y^{\prime}}{\mathfrak{X}}$.
Consequently, this algebraic automorphism has the
$\alpha\alpha^{\prime}$-extension. Thus the coherent configuration
$\operatorname{pr}_{2}{\mathfrak{X}}$ satisfies condition (S2). This implies
that it is sesquiclosed, and $\operatorname{W_{1/2}}({\cal
X})\leq\operatorname{pr}_{2}{\mathfrak{X}}$ by the minimality of the
sesquiclosure. ∎

In general, not every algebraic isomorphism of two coherent configurations can
be extended to an algebraic isomorphism between their sesquiclosures. An
obvious reason for this is that algebraic isomorphisms do not preserve the
property to be sesquiclosed. To exclude this reason, one can define
sesquiclosed algebraic isomorphisms as follows [17]: an algebraic isomorphism
$\varphi:{\cal X}\to{\cal X}^{\prime}$ is said to be _sesquiclosed_ if
$\varphi$ has the $\alpha\alpha^{\prime}$-extension for all
$\alpha\in\Delta\in F({\cal X})$ and $\alpha^{\prime}\in\Delta^{\prime}\in
F({\cal X}^{\prime})$ such that $\Delta^{\varphi}=\Delta^{\prime}$.

We extend the concept of sesquiclosed algebraic isomorphism to rainbows by
saying that a similarity $\varphi:{\cal X}\to{\cal X}^{\prime}$ is
sesquiclosed if there exists (and hence unique) a sesquiclosed algebraic
isomorphism $\psi:\operatorname{W_{1/2}}({\cal
X})\to\operatorname{W_{1/2}}({\cal X}^{\prime})$ that extends $\varphi$. In
this case we also say that the rainbows ${\cal X}$ and ${\cal X}^{\prime}$ are
_$\operatorname{W_{1/2}}$ -equivalent_ with respect to $\varphi$. The
algorithm $\operatorname{W_{1/2}}$ _identifies_ a rainbow ${\cal X}$ if every
sesquiclosed similarity from ${\cal X}$ is induced by an isomorphism. Saying
that graphs ${\cal G}$ and ${\cal G}^{\prime}$ are
$\operatorname{W_{1/2}}$-equivalent (respectively, the algorithm
$\operatorname{W_{1/2}}$ identifies ${\cal G}$), we mean that the the rainbows
${\cal X}({\cal G})$ and ${\cal X}({\cal G}^{\prime})$ are
$\operatorname{W_{1/2}}$-equivalent with respect to the standard similarity
(respectively, the algorithm $\operatorname{W_{1/2}}$ identifies the rainbow
${\cal X}({\cal G})$).

##  6\. Sesquiclosed coherent configurations and the $3$-dim WL

Let ${\cal X}$ be a sesquiclosed coherent configuration. We say that two point
triples $x$ and $x^{\prime}$ are _similar_ (with respect to ${\cal X}$) if
$(x_{1},x_{2})\cdot x_{3}\sim(x^{\prime}_{1},x^{\prime}_{2})\cdot
x^{\prime}_{3}$, i.e., if there exists the $x_{3}x^{\prime}_{3}$-extension
$\varphi_{x_{3}x^{\prime}_{3}}$ of the algebraic automorphism
$\operatorname{id}_{\cal X}$ and also

(20)
$\varphi_{x_{3}x^{\prime}_{3}}(r_{x_{3}}(x_{1},x_{2}))=r_{x^{\prime}_{3}}(x^{\prime}_{1},x^{\prime}_{2}).$

It is not hard to see that the relation “to be similar” is an equivalence
relation on the triples.

######  Theorem 6.1.

Let ${\cal X}$ be a sesquiclosed coherent configuration on $\Omega$. Then two
triples of $\Omega^{3}$ are similar if and only if they belong to the same
class of $\operatorname{WL}_{3}({\cal X})$.

###### Proof.

Let ${\cal P}$ be the partition of $\Omega^{3}$ into the classes of similar
triples, and let ${\mathfrak{X}}=\operatorname{WL}_{3}({\cal X})$. We need to
verify that ${\cal P}={\mathfrak{X}}$. To prove that ${\cal
P}\leq{\mathfrak{X}}$, we assume that $x$ and $x^{\prime}$ belong to the same
class $X\in{\mathfrak{X}}$. Then the $(1)$-tuples $y=(x_{3})$ and
$y^{\prime}=(x_{3}^{\prime})$ are $\psi$-similar, where
$\psi=\operatorname{id}_{\mathfrak{X}}$, and

(21)
$(x_{1},x_{2})\in\operatorname{res}_{y}X\quad\text{and}\quad(x^{\prime}_{1},x^{\prime}_{2})\in\operatorname{res}_{y^{\prime}}X.$

Let
$\psi_{yy^{\prime}}:\operatorname{res}_{y}{\mathfrak{X}}\to\operatorname{res}_{y^{\prime}}{\mathfrak{X}}$
be the algebraic isomorphism from Lemma 2.1 for $m=3$ and $k=2$. It extends
the algebraic automorphism
$\psi_{2}=\operatorname{id}_{\operatorname{pr}_{2}{\mathfrak{X}}}$ and hence
the algebraic automorphism $\operatorname{id}_{\cal X}$ (recall that
$\operatorname{pr}_{2}{\mathfrak{X}}\geq{\cal X}$). Furthermore,

$\psi_{yy^{\prime}}(1_{x_{3}})=1_{x_{3}^{\prime}}\quad\text{and}\quad\psi_{yy^{\prime}}(\operatorname{res}_{y}X)=\operatorname{res}_{y^{\prime}}(\psi(X))=\operatorname{res}_{y^{\prime}}X.$

Thus the restriction of $\psi_{yy^{\prime}}$ to the coherent configuration
${\cal X}_{x_{3}}\leq\operatorname{res}_{y}{\mathfrak{X}}$ is the
$x_{3}x^{\prime}_{3}$-extension $\varphi_{yy^{\prime}}$ of the algebraic
automorphism $\operatorname{id}_{\cal X}$. By formula (21), we obtain

$\varphi_{yy^{\prime}}(r_{y}(x_{1},x_{2}))=\psi_{yy^{\prime}}(r_{y}(x_{1},x_{2}))\supseteq\psi_{yy^{\prime}}(\operatorname{res}_{y}X)=$
$\operatorname{res}_{y^{\prime}}(\psi(X))=\operatorname{res}_{y^{\prime}}X\ni(x^{\prime}_{1},x^{\prime}_{2}).$

It follows that
$\varphi_{yy^{\prime}}(r_{y}(x_{1},x_{2}))=r_{y^{\prime}}(x^{\prime}_{1},x^{\prime}_{2})$,
i.e., the triples $x$ and $x^{\prime}$ are similar. Thus,
${\mathfrak{X}}\geq{\cal P}$. To prove the converse inclusion, we need an
auxiliary lemma.

######  Lemma 6.2.

Let $\varphi:{\cal X}\to{\cal X}^{\prime}$ be an algebraic isomorphism of
sesquiclosed coherent configurations. Assume that
$(x,x^{\prime})\in\Omega^{3}\times{\Omega^{\prime}}^{3}$ is such that
$\varphi$ has the $yy^{\prime}$-extension $\varphi_{yy^{\prime}}$ with
$y=x_{3}$ and $y^{\prime}=x_{3}^{\prime}$, and also

(22)
$\varphi(r(y,y))=r^{\prime}(y^{\prime},y^{\prime})\quad\text{and}\quad\varphi_{yy^{\prime}}(r_{y}(x_{1},x_{2}))=r^{\prime}_{y^{\prime}}(x^{\prime}_{1},x^{\prime}_{2}).$

Then $(x,x^{\prime})\in T^{3}_{\varphi}({\cal X},{\cal X}^{\prime})$.

###### Proof.

Given an arbitrary pair $(r,s)$ of basis relations of ${\cal X}_{y}$, put

$\Delta(r,s)=x_{1}r\cap x_{2}s^{*}.$

If this set is not empty, then the sets $x_{1}r$ and $x_{2}s^{*}$ are
contained in the same fiber of the coherent configuration ${\cal X}_{y}$, that
coincides with the right support of both $r$ and $s^{*}$; denote this fiber by
$\Gamma(r,s)$. When $\Delta(r,s)=\varnothing$, we put
$\Gamma(r,s)=\varnothing$. Similarly, we define the sets
$\Delta(r^{\prime},s^{\prime})$ and $\Gamma(r^{\prime},s^{\prime})$ for any
pair $(r^{\prime},s^{\prime})$ of basis relations of the coherent
configuration ${\cal X}^{\prime}_{y^{\prime}}$.

In what follows, the image of a relation $r$ with respect to
$\varphi_{yy^{\prime}}$ is denoted by $r^{\prime}$. In these notation, the
right-hand side of (22) implies that if $t=r_{y}(x_{1},x_{2})$, then
$t^{\prime}=\varphi_{yy^{\prime}}(t)=r^{\prime}_{y^{\prime}}(x^{\prime}_{1},x^{\prime}_{2})$,
and hence

(23)
$|\Delta(r,s)|=c_{r,s}^{t}=c_{r^{\prime},s^{\prime}}^{t^{\prime}}=|\Delta(r^{\prime},s^{\prime})|.$

Moreover, if $\Delta(r,s)\neq\varnothing$, then the algebraic isomorphism
$\varphi_{yy^{\prime}}$ takes the right support $\Gamma(r,s)$ of $r$ to the
right support $\Gamma(r^{\prime},s^{\prime})$ of $r^{\prime}$. It follows that

(24) $\Gamma(r,s)^{\prime}=\Gamma(r^{\prime},s^{\prime}).$

To prove that $(x,x^{\prime})\in T^{3}_{\varphi}({\cal X},{\cal X}^{\prime})$,
we consider the pebble game ${\mathscr{C}}_{4}(\varphi)$ with initial
configuration $(x,x^{\prime})$, see Subsection 3.3. Let Spoiler choose a set
$A^{\prime}\subseteq\Omega^{\prime}$ (the case $A^{\prime}\subseteq\Omega$ is
similar). Denote by $S(A^{\prime})$ the set of all pairs
$(r^{\prime},s^{\prime})$ of basis relations of ${\cal
X}^{\prime}_{y^{\prime}}$, such that the set
$A^{\prime}\cap\Delta(r^{\prime},s^{\prime})=:A^{\prime}(r^{\prime},s^{\prime})$
is not empty. Then

$|A^{\prime}|=\sum_{(r^{\prime},s^{\prime})\in
S(A^{\prime})}|A^{\prime}(r^{\prime},s^{\prime})|.$

Next, for every pair $(r^{\prime},s^{\prime})\in S(A^{\prime})$, denote by
$A(r,s)$ an arbitrary subset of $\Delta(r,s)$, the cardinality of which is
equal to the number
$|A^{\prime}(r^{\prime},s^{\prime})|\leq|\Delta(r^{\prime},s^{\prime})|=|\Delta(r,s)|$,
see (23).

Now, Duplicator responds with the union $A\subseteq\Omega$ of all the sets
$A(r,s)$ for which $(r^{\prime},s^{\prime})\in S(A^{\prime})$. This is
correct, because

$|A|=\sum_{(r^{\prime},s^{\prime})\in
S(A^{\prime})}|A(r,s)|=\sum_{(r^{\prime},s^{\prime})\in
S(A^{\prime})}|A^{\prime}(r^{\prime},s^{\prime})|=|A^{\prime}|.$

Next, Spoiler picks up some $a\in A$, and Duplicator responds with arbitrary
$a^{\prime}\in A^{\prime}(r^{\prime},s^{\prime})\subseteq A^{\prime}$, where
the pair $(r^{\prime},s^{\prime})\in S(A^{\prime})$ is defined so that $a\in
A(r,s)$.

To complete the proof, it remains to verify that
$r(x_{i},a)^{\prime}=r^{\prime}(x^{\prime}_{i},a^{\prime})$, $i=1,2,3$. Note
that

$a\in A(r,s)\subseteq\Delta(r,s)\subseteq\Gamma(r,s)\quad\text{and}\quad
a^{\prime}\in
A^{\prime}(r^{\prime},s^{\prime})\subseteq\Delta(r^{\prime},s^{\prime})\subseteq\Gamma(r^{\prime},s^{\prime}),$

see (24). By condition (S1), we have $\Gamma(r,s)=yu$ for some $u\in S$. In
view of the first equality in (22), condition (S2) implies that
$\Gamma(r^{\prime},s^{\prime})=y^{\prime}u^{\prime}$. Thus,
$r(x_{3},a)^{\prime}=r(y,a)^{\prime}=u^{\prime}=r^{\prime}(y^{\prime},a^{\prime})=r^{\prime}(x^{\prime}_{3},a^{\prime})$.
Next,

$r(x_{1},a)\supseteq r_{y}(x_{1},a)=r\quad\text{and}\quad
r^{\prime}(x^{\prime}_{1},a^{\prime})\supseteq
r^{\prime}_{y^{\prime}}(x^{\prime}_{1},a^{\prime})=r^{\prime}.$

Since the algebraic isomorphism $\varphi_{yy^{\prime}}$ coincides with
$\varphi$ on ${\cal X}$ and takes $r$ to $r^{\prime}$, this shows that
$r(x_{1},a)^{\prime}\supseteq r^{\prime}\ni(x^{\prime}_{1},a^{\prime})$.
Consequently, $r(x_{1},a)^{\prime}=r^{\prime}(x^{\prime}_{1},a^{\prime})$. The
same argument for $x_{1}$ and $r$ replaced by, respectively, $x_{2}$ and $s$,
shows that $r(x_{2},a)=r^{\prime}(x^{\prime}_{2},a^{\prime})$. ∎

Let us complete the proof of Theorem 6.1, let $x$ and $x^{\prime}$ be similar
triples. In view of condition (S2), the assumption of Lemma 6.2 is satisfied
for ${\cal X}^{\prime}={\cal X}$ and $\varphi=\operatorname{id}_{\cal X}$, and
therefore $(x,x^{\prime})\in T^{3}_{\varphi}({\cal X},{\cal X}^{\prime})$. By
Lemma 3.2(1) for $m=3$, ${\cal X}={\cal X}^{\prime}$, and
$\hat{\varphi}=\operatorname{id}_{\mathfrak{X}}$, this implies that
$[x]=[x^{\prime}]$. Thus, ${\cal P}\geq{\mathfrak{X}}$. ∎

##  7\. Proofs of the main results

In this section we first prove Theorem 1.1, and then deduce formula (1),
Theorem 1.2, and Corollary 1.3. Without loss of generality, we will prove all
these statements for a graph ${\cal G}$ replaced by its coherent configuration
${\cal X}=\operatorname{WL}({\cal G})$. In what follows, we put
${\mathfrak{X}}=\operatorname{WL}_{3}({\cal X})$.

Proof of Theorem 1.1. Denote by ${\mathfrak{Y}}_{0}$ the partition of
$\Omega^{3}$ into the color classes of the coloring
$c_{0}(3,\operatorname{pr}_{2}{\mathfrak{X}})$. It is not hard to see that
${\mathfrak{Y}}_{0}\leq{\mathfrak{X}}$. Taking the $3$-ary coherent closure of
both sides yields

$\operatorname{WL}_{3}(\operatorname{pr}_{2}{\mathfrak{X}})=\operatorname{WL}_{3}({\mathfrak{Y}}_{0})\leq\operatorname{WL}_{3}({\mathfrak{X}})={\mathfrak{X}}.$

Using this inclusion and applying the operator $\operatorname{WL}_{3}$ to each
coherent configuration in the series ${\cal X}\leq\operatorname{W_{1/2}}({\cal
X})\leq\operatorname{pr}_{2}{\mathfrak{X}}$ (see Lemma 5.2), we obtain

(25) ${\mathfrak{X}}=\operatorname{WL}_{3}({\cal
X})\leq\operatorname{WL}_{3}(\operatorname{W_{1/2}}({\cal
X}))\leq\operatorname{WL}_{3}(\operatorname{pr}_{2}{\mathfrak{X}})\leq{\mathfrak{X}},$

whence $\operatorname{WL}_{3}({\cal
X})=\operatorname{WL}_{3}(\operatorname{W_{1/2}}({\cal X}))$ .

To prove the second equality, set ${\cal Y}=\operatorname{W_{1/2}}({\cal X})$.
By Lemma 5.2, the coherent configuration ${\cal
Y}^{\prime}=\operatorname{pr}_{2}{\mathfrak{X}}$ is sesquiclosed and hence
${\cal Y}\leq{\cal Y}^{\prime}$. Assume on the contrary that ${\cal Y}<{\cal
Y}^{\prime}$. Then there are relations $s\in S({\cal Y})$ and $s^{\prime}\in
S({\cal Y}^{\prime})$, and a point $\alpha\in\Omega$ such that $\alpha
s^{\prime}$ is a proper subset of $\alpha s$. Take arbitrary points
$\beta\in\alpha s^{\prime}$ and $\beta^{\prime}\in\alpha s\setminus\alpha
s^{\prime}$ and put

$x=(\beta,\beta,\alpha)\quad\text{and}\quad
x^{\prime}=(\beta^{\prime},\beta^{\prime},\alpha).$

The triples $x$ and $x^{\prime}$ are similar with respect to ${\cal Y}$.
Indeed, $\varphi_{\alpha\alpha}=\operatorname{id}_{{\cal Y}_{\alpha}}$ is the
$\alpha\alpha$-extension of the algebraic automorphism
$\operatorname{id}_{\cal Y}$. Moreover, since the coherent configuration
${\cal Y}$ is sesquiclosed, $1_{\alpha s}$ is a basis relation of its point
extension ${\cal Y}_{\alpha}$. Therefore, $r_{\alpha}(\beta,\beta)=1_{\alpha
s}=r_{\alpha}(\beta^{\prime},\beta^{\prime})$ and hence

$\varphi_{\alpha\alpha}(r_{\alpha}(\beta,\beta))=\varphi_{\alpha\alpha}(1_{\alpha
s})=1_{\alpha s}=r_{\alpha}(\beta^{\prime},\beta^{\prime}).$

By Theorem 6.1, this implies that $x$ and $x^{\prime}$ lie in the same class
of the $3$-ary coherent configuration $\operatorname{WL}_{3}({\cal Y})$.
However, by the first part of the proof, $\operatorname{WL}_{3}({\cal
Y})=\operatorname{WL}_{3}({\cal Y}^{\prime})$, see formula (25). Thus, $x$ and
$x^{\prime}$ lie in the same class of $\operatorname{WL}_{3}({\cal
Y}^{\prime})$.

On the other hand, $r_{{\cal Y}^{\prime}}(\alpha,\beta)\neq r_{{\cal
Y}^{\prime}}(\alpha,\beta^{\prime})$. Therefore, the triples $x$ and
$x^{\prime}$ are not similar with respect to ${\cal Y}^{\prime}$. Since the
coherent configuration ${\cal Y}^{\prime}$ is sesquiclosed, this implies by
Theorem 6.1 that $x$ and $x^{\prime}$ do not lie in the same class of
$\operatorname{WL}_{3}({\cal Y}^{\prime})$, a contradiction. $\square$

Proof of formula (1). Denote by $\sigma_{1,2}$ the algorithm defined in (16)
for the set $I=\\{1,2\\}$. Obviously, $\sigma_{1,2}({\cal X})\leq W({\cal
X})$.

######  Lemma 7.1.

$\operatorname{W_{1/2}}({\cal X})=\sigma_{1,2}({\cal X})$.

###### Proof.

The coherent configuration $\sigma_{1,2}({\cal X})$ is sesquiclosed. Indeed,
taking into account that $\sigma_{1}(\sigma_{1,2}({\cal
X}))=\sigma_{1,2}({\cal X})=\sigma_{2}(\sigma_{1,2}({\cal X}))$, we see that
it satisfies condition (S1) by [18, Chapter O, Theorem 4.7(b)], and satisfies
condition (S2) by the definition of $\sigma_{1}$. Thus, $\sigma_{1,2}({\cal
X})\geq\operatorname{W_{1/2}}({\cal X}).$

Conversely, it suffices to verify that for any two pairs $x$ and $x^{\prime}$
of points of the coherent configuration ${\cal Y}=\operatorname{W_{1/2}}({\cal
X})$, we have

(26) $r_{\cal Y}(x)=r_{\cal Y}(x^{\prime})\quad\Rightarrow\
x\stackrel{{\scriptstyle\scriptscriptstyle{{}_{2}}}}{{\sim}}x^{\prime}.$

Indeed, assume that this is true. Then $\sigma_{2}({\cal Y})={\cal Y}$.
Furthermore, $\sigma_{1}({\cal Y})={\cal Y}$ because ${\cal Y}$ is
sesquiclosed (see condition (S1). Thus,

$\sigma_{1,2}((\operatorname{W_{1/2}}({\cal X}))=\sigma_{1,2}({\cal Y})={\cal
Y}=\operatorname{W_{1/2}}({\cal X})$

and $\operatorname{W_{1/2}}({\cal
X})=\sigma_{1,2}(\operatorname{W_{1/2}}({\cal X}))\geq\sigma_{1,2}({\cal X})$,
which completes the proof.

To prove (26), we assume that $r_{\cal Y}(x)=r_{\cal Y}(x^{\prime})$. Then
obviously $r(x)=r(x^{\prime})$. Next, let $\alpha\in\Omega$, and let $X$ be
the class of $\operatorname{WL}_{3}({\cal Y})$ containing the triple
$x\cdot\alpha$. Since $r_{\cal Y}(x)=r_{\cal Y}(x^{\prime})$ and
$\operatorname{pr}_{2}\operatorname{WL}_{3}({\cal Y})={\cal Y}$ (see above),
we have $x^{\prime}\in\operatorname{pr}_{2}X$. Consequently, there exists
$\alpha^{\prime}\in\Omega$ such that $x^{\prime}\cdot\alpha^{\prime}\in X$. It
follows (see Subsection 2.5) that

$n_{\alpha}(x)=n_{2}(X)=n_{\alpha^{\prime}}(x^{\prime}).$

Thus,
$x\stackrel{{\scriptstyle\scriptscriptstyle{{}_{2}}}}{{\sim}}x^{\prime}$, as
required. ∎

Let us prove the left-hand side inclusion in formula (1). By the second
inclusion in (2), we have $\operatorname{pr}_{2}\operatorname{WL}_{3}({\cal
X})=\operatorname{W_{1/2}}({\cal X})$. Thus by Lemma 7.1, we have

$\operatorname{pr}_{2}\operatorname{WL}_{3}({\cal
X})=\operatorname{W_{1/2}}({\cal X})=\sigma_{1,2}({\cal X})\leq W({\cal X}),$

as required.

Let us prove the right-hand side inclusion in formula (1). Let ${\cal
Y}^{\prime}=\operatorname{pr}_{2}\operatorname{WL}_{4}({\cal X})$. Since
$W({\cal X})$ is the minimal coherent configuration such that
$\sigma_{i}({\cal X})={\cal X}$ for all $i$, it suffices to verify that
$\sigma_{i}({\cal Y}^{\prime})={\cal Y}^{\prime}$ also for all $i$. By formula
(12), we have $\operatorname{pr}_{2}\operatorname{WL}_{3}({\cal
Y}^{\prime})={\cal Y}^{\prime}$. Consequently, by Theorem 1.1,

$\operatorname{W_{1/2}}({\cal
Y}^{\prime})=\operatorname{pr}_{2}\operatorname{WL}_{3}({\cal
Y}^{\prime})={\cal Y}^{\prime},$

i.e., ${\cal Y}^{\prime}$ is sesquiclosed. Thus it suffices to verify that
$\sigma_{3}({\cal Y}^{\prime})=\sigma_{4}({\cal Y}^{\prime})={\cal
Y}^{\prime}$. Note that this is obviously true if for any two pairs $x$ and
$x^{\prime}$ of points of the coherent configuration ${\cal Y}^{\prime}$, we
have

(27) $r_{{\cal Y}^{\prime}}(x)=r_{{\cal
Y}^{\prime}}(x^{\prime})\quad\Rightarrow\
x\stackrel{{\scriptstyle\scriptscriptstyle{{}_{3}}}}{{\sim}}x^{\prime}\quad\text{and}\quad
x\stackrel{{\scriptstyle\scriptscriptstyle{{}_{4}}}}{{\sim}}x^{\prime}.$

To verify this implication, assume that $r_{{\cal Y}^{\prime}}(x)=r_{{\cal
Y}^{\prime}}(x^{\prime})$. Then there are pairs $y$ and $y^{\prime}$ such that
in the $4$-ary coherent configuration
${\mathfrak{X}}:=\operatorname{WL}_{4}({\cal X})$ we have

(28) $[y\cdot x]=[y^{\prime}\cdot x^{\prime}].$

It follows that the pairs $x$ and $x^{\prime}$ are
$\operatorname{id}_{\mathfrak{X}}$-similar. By Lemma 2.1, this implies that
$(\operatorname{id}_{\mathfrak{X}})_{xx^{\prime}}$ induces the
$xx^{\prime}$-extension of the algebraic isomorphism
$\operatorname{pr}_{2}\operatorname{id}_{\mathfrak{X}}=\operatorname{id}_{{\cal
Y}^{\prime}}$. Thus,
$x\stackrel{{\scriptstyle\scriptscriptstyle{{}_{3}}}}{{\sim}}x^{\prime}$.

To verify that
$x\stackrel{{\scriptstyle\scriptscriptstyle{{}_{4}}}}{{\sim}}x^{\prime}$,
denote by $X_{1}$, $X_{2},\ldots,X_{k}$ all pairwise distinct classes
$[\tilde{y}\cdot x]\in{\mathfrak{X}}$ such that $x\cdot y\sim
x\cdot\tilde{y}$. Then it is easily seen that

$n_{y}(x)=\sum_{i=1}^{k}|\operatorname{res}_{x}X_{i}|=\sum_{i=1}^{k}n_{2}(X_{i}).$

Thus to verify that $n_{y}(x)=n_{y^{\prime}}(x^{\prime})$ (and hence
$x\stackrel{{\scriptstyle\scriptscriptstyle{{}_{4}}}}{{\sim}}x^{\prime}$), it
suffices to check that given a pair $\tilde{y}$ such that $x\cdot y\sim
x\cdot\tilde{y}$, there exists a pair $\tilde{y}^{\prime}$ such that
$x^{\prime}\cdot y^{\prime}\sim x^{\prime}\cdot\tilde{y}^{\prime}$ and the
class $\tilde{X}:=[\tilde{y}\cdot x]$ coincides with the class
$[\tilde{y}^{\prime}\cdot y^{\prime}]$.

We have
$x\in\operatorname{pr}_{\\{3,4\\}}X\cap\operatorname{pr}_{\\{3,4\\}}\tilde{X}$.
It follows that
$x^{\prime}\in\operatorname{pr}_{\\{3,4\\}}X=\operatorname{pr}_{\\{3,4\\}}\tilde{X}$.
This implies that there exists a pair $\tilde{y}^{\prime}$ such that
$[\tilde{y}^{\prime}\cdot y^{\prime}]=\tilde{X}$. Consequently,

$(\operatorname{id}_{\mathfrak{X}})_{y^{\prime}y}(\operatorname{res}_{y^{\prime}}X)=\operatorname{res}_{y}X\quad\text{and}\quad(\operatorname{id}_{\mathfrak{X}})_{\tilde{y}\tilde{y}^{\prime}}(\operatorname{res}_{\tilde{y}}\tilde{X})=\operatorname{res}_{\tilde{y}^{\prime}}\tilde{X}.$

Furthermore, by Lemma 3.1, we have $\operatorname{res}_{y^{\prime}}X\subseteq
r_{y^{\prime}}(x^{\prime})$, $\operatorname{res}_{y}X\subseteq r_{y}(x)$ and
$\operatorname{res}_{\tilde{y}}\tilde{X}\subseteq r_{\tilde{y}}(x)$,
$\operatorname{res}_{\tilde{y}^{\prime}}\tilde{X}\subseteq
r_{\tilde{y}^{\prime}}(x^{\prime})$. By Lemma 2.1, this yields

(29) $(\operatorname{id}_{\cal
X})_{y^{\prime}y}(r_{y^{\prime}}(x^{\prime}))=r_{y}(x)\quad\text{and}\quad(\operatorname{id}_{\cal
X})_{\tilde{y}\tilde{y}^{\prime}}(r_{\tilde{y}}(x))=r_{\tilde{y}^{\prime}}(x^{\prime}).$

Finally, since $x\cdot y\sim x\cdot\tilde{y}$, we also have

(30) $(\operatorname{id}_{\cal X})_{y\tilde{y}}(r_{y}(x))=r_{\tilde{y}}(x).$

By (29) and (30), the composition mapping $(\operatorname{id}_{\cal
X})_{y^{\prime}\tilde{y}^{\prime}}=(\operatorname{id}_{\cal
X})_{y^{\prime}y}\,(\operatorname{id}_{\cal
X})_{y\tilde{y}}(\operatorname{id}_{\cal X})_{\tilde{y}\tilde{y}^{\prime}}$
takes the relation $r_{y^{\prime}}(x^{\prime})$ to the relation
$r_{\tilde{y}^{\prime}}(x^{\prime})$. Thus, $x^{\prime}\cdot y^{\prime}\sim
x^{\prime}\cdot\tilde{y}^{\prime}$, and we are done. $\square$

Proof of Theorem 1.2. The first part of the statement follows from Theorem 7.2
below if the similarity $\varphi$ is taken to be the standard one.

######  Theorem 7.2.

Rainbows ${\cal X}$ and ${\cal X}^{\prime}$ are
$\operatorname{WL}_{3}$-equivalent with respect to a similarity $\varphi:{\cal
X}\to{\cal X}^{\prime}$ if and only if ${\cal X}$ and ${\cal X}^{\prime}$ are
$\operatorname{W_{1/2}}$-equivalent with respect to $\varphi$.

###### Proof.

To prove the “only if” part, assume that ${\cal X}$ and ${\cal X}^{\prime}$
are $\operatorname{WL}_{3}$-equivalent with respect to $\varphi$, i.e., there
is an algebraic isomorphism $\hat{\varphi}:\operatorname{WL}_{3}({\cal
X})\to\operatorname{WL}_{3}({\cal X}^{\prime})$ such that
$\psi:=\hat{\varphi}_{2}$ defined in (9) for $k=2$, extends the similarity
$\varphi$. By the second equality in formula (2), the algebraic isomorphism
$\psi$ takes ${\cal Y}:=\operatorname{W_{1/2}}({\cal X})$ to ${\cal
Y}^{\prime}:=\operatorname{W_{1/2}}({\cal X}^{\prime})$. It remains to verify
that $\psi$ is sesquiclosed. To this end, let

$\alpha\in\Delta\in F({\cal
Y})\quad\text{and}\quad\alpha^{\prime}\in\Delta^{\prime}\in F({\cal
Y}^{\prime})$

so that $\Delta^{\psi}=\Delta^{\prime}$. Denote by $y$ and $y^{\prime}$ the
$1$-tuples $(\alpha)$ and $(\alpha^{\prime})$, respectively. By Lemma 2.1 for
$m=3$ and $k=2$, the algebraic isomorphism $\hat{\varphi}$ induces an
algebraic isomorphism

$\hat{\varphi}_{yy^{\prime}}:\operatorname{res}_{y}\operatorname{WL}_{3}({\cal
X})\to\operatorname{res}_{y^{\prime}}\operatorname{WL}_{3}({\cal
X}^{\prime}),$

that extends $\psi$. Since the restriction of $\hat{\varphi}_{yy^{\prime}}$ to
the point extension ${\cal Y}_{\alpha}$, takes this extension to ${\cal
Y}^{\prime}_{\alpha^{\prime}}$, we are done.

Let us prove the “if” part. Without loss of generality, we may assume that
${\cal X}=\operatorname{W_{1/2}}({\cal X})$ and ${\cal
X}^{\prime}=\operatorname{W_{1/2}}({\cal X}^{\prime})$. Let $\varphi:{\cal
X}\to{\cal X}^{\prime}$ be a sesquiclosed algebraic isomorphism. Then given
$x\in\Omega^{3}$, there exists
$x^{\prime}\in{\Omega^{\prime}}{\phantom{x}{}^{3}}$ such that condition (22)
is satisfied; note that this guarantees the existence of the
$yy^{\prime}$-extension $\varphi_{yy^{\prime}}$ of the algebraic isomorphism
$\varphi$, where $y=(x_{3})$ and $y^{\prime}=(x_{3}^{\prime})$.

We claim that the mapping

$\hat{\varphi}:\operatorname{WL}_{3}({\cal X})\to\operatorname{WL}_{3}({\cal
X}^{\prime}),\ [x]\mapsto[x^{\prime}],$

is a correctly defined bijection. Indeed, the uniqueness of the point
extension of algebraic isomorphism implies that if condition (22) is satisfied
for $x$ and $x^{\prime}$ replaced by $\tilde{x}\in\Omega^{3}$ and
$\tilde{x}^{\prime}\in{\Omega^{\prime}}{\phantom{x}{}^{3}}$, respectively,
then the diagram

$\begin{CD}{\cal X}_{y}@>{\varphi_{yy^{\prime}}}>{}>{\cal
X}^{\prime}_{y^{\prime}}\\\ @V{{(\operatorname{id}_{\cal
X})_{y\tilde{y}}}}V{}V@V{}V{(\operatorname{id}^{\prime}_{{\cal
X}^{\prime}})_{y^{\prime}\tilde{y}^{\prime}}}V\\\ {\cal
X}_{\tilde{y}}@>{}>{\varphi_{\tilde{y}\tilde{y}^{\prime}}}>{\cal
X}^{\prime}_{\tilde{y}^{\prime}}\\\ \end{CD}\ $

is commutative, where $\tilde{y}=(\tilde{x}_{3})$ and
$\tilde{y}^{\prime}=(\tilde{x}^{\prime}_{3})$. Here we also use the fact that
${\cal X}$ and ${\cal X}^{\prime}$ are sesquiclosed. It follows that if
$\tilde{x}$ is $\hat{\varphi}$-similar to $x$, then $\tilde{x}^{\prime}$ is
$\hat{\varphi}$-similar to $x^{\prime}$. By Theorem 6.1, this implies that
$[\tilde{x}]=[x]$ and $[x^{\prime}]=[\tilde{x}^{\prime}]$, which proves the
claim.

Let us complete the proof of Theorem 7.2. By the first equality in (2), we
have $\hat{\varphi}_{2}=\varphi$. Furthermore, from Lemma 6.2, it follows that
if $\hat{\varphi}([x])=[x^{\prime}]$ for some $x$ and $x^{\prime}$, then
$(x,x^{\prime})\in T^{3}_{\varphi}({\cal X},{\cal X}^{\prime})$. By Lemma
3.2(2), this shows that $\hat{\varphi}$ is an algebraic isomorphism. Thus,
${\cal X}$ and ${\cal X}^{\prime}$ are $\operatorname{WL}_{3}$-equivalent with
respect to $\varphi$. ∎

The second part of Theorem 1.2 follows from the first one. Indeed, the
coherent configuration ${\cal X}$ is identified by $\operatorname{WL}_{3}$ if
and only if every algebraic isomorphism with respect to which ${\cal X}$ and
${\cal X}^{\prime}$ are $\operatorname{WL}_{3}$-equivalent is induced by an
isomorphism. By Theorem 7.2, this is true if and only if every algebraic
isomorphism with respect to which ${\cal X}$ and ${\cal X}^{\prime}$ are
$\operatorname{W_{1/2}}$-equivalent, is induced by an isomorphism, i.e.,
${\cal X}$ is identified by $\operatorname{W_{1/2}}$. $\square$

##  8\. Applications to projective planes

###  8.1. Preliminaries

Let ${\cal X}$ be a coherent configuration on $\Omega$. Denote by ${\cal
X}\otimes{\cal X}$ the tensor square of ${\cal X}$, which is a coherent
configuration on $\Omega^{2}$ with basis relations $r\otimes s=\\{(x,y):\
(x_{1},y_{1})\in r,\ (x_{2},y_{2})\in s\\}$, where $r$ and $s$ run over $S$.

Following [10], the _$2$ -extension_ and _$2$ -closure_ of ${\cal X}$ are
defined to be the coherent configurations

$\hat{\cal X}=\operatorname{WL}({\cal X}\otimes{\cal
X},1_{\Delta})\quad\text{and}\quad\bar{\cal X}=(\hat{\cal X}_{\Delta})^{f},$

respectively, where $\Delta=\operatorname{Diag}(\Omega^{2})$ and $f$ is the
bijection $\Delta\to\Omega$, $(\alpha,\alpha)\mapsto\alpha$. The $2$-extension
accumulates information about all one point extensions of ${\cal X}$. More
precisely, let $e$ be the equivalence relation with classes
$\Gamma=\Omega\times\\{\alpha\\}$, $\alpha\in\Omega$. Then $e$ is a parabolic
of $\hat{\cal X}$, i.e., an equivalence relation on $\Omega^{2}$ that is also
a relation of the coherent configuration $\hat{\cal X}$. Furthermore,

(31) $(\hat{\cal X}_{\Gamma})^{f_{\alpha}}\geq{\cal X}_{\alpha},$

where $f_{\alpha}$ is the bijection $\Gamma\to\Omega$,
$(\beta,\alpha)\mapsto\beta$.

The $2$-closure defines a closure operator which is more powerful than the
operator $\operatorname{W_{1/2}}$. Indeed, from [5, Lemma 3.5.25], it follows
that the coherent configuration $\bar{\cal X}$ satisfies conditions (S1) and
(S2), and hence is sesquiclosed. This proves the proposition below (which
strengthens the left-hand side inclusion in [8, Theorem 1.4] for $m=2$).

######  Proposition 8.1.

$\operatorname{W_{1/2}}({\cal X}))\leq\bar{\cal X}$.

Let ${\cal X}^{\prime}$ be a coherent configuration on $\Omega^{\prime}$. An
algebraic isomorphism $\hat{\varphi}:\widehat{\cal X}\to\widehat{{\cal
X}^{\prime}}$ is called a _$2$ -extension_ of an algebraic isomorphism
$\varphi:{\cal X}\to{\cal X}^{\prime}$ if

$\hat{\varphi}(1_{\Delta})=1_{\Delta^{\prime}}\quad\text{and}\quad\hat{\varphi}(r\otimes
s)=\varphi(r)\otimes\varphi(s)$

for all $r,s\in S$, where
$\Delta^{\prime}=\operatorname{Diag}({\Omega^{\prime}}{\phantom{x}{}^{2}})$.
Not every $\varphi$ has the $2$-extension, but if it has, then
$\widehat{\varphi}$ is uniquely determined. The following lemma is a special
case of [9, Lemma 8.3(2)] for $m=2$.

######  Lemma 8.2.

If ${\cal X}=\bar{\cal X}$ and $\varphi$ has the $2$-extension, then $\varphi$
is sesquiclosed.

###  8.2. The scheme of a projective plane

Let ${\cal P}$ be a finite projective plane of order $q$. Denote by $\Omega$
the union of the point and line sets of ${\cal P}$, $|\Omega|=2(q^{2}+q+1)$.
Then the set $\Omega^{2}\setminus 1_{\Omega}$ is partitioned into three
symmetric relations $s_{1}$, $s_{2}$, and $s_{3}$ consisting of all pairs of
distinct points or lines, of a point and a line that are incident, and of a
point and a line that are not incident, respectively. Together with
$s_{0}=1_{\Omega}$ they form a symmetric scheme ${\cal X}({\cal P})$ of rank
$4$ and the valencies

(32) $n_{s_{0}}=1,\quad n_{s_{1}}=q^{2}+q,\quad n_{s_{2}}=q+1,\quad
n_{s_{3}}=q^{2}.$

Every scheme algebraically isomorphic to ${\cal X}({\cal P})$ is of the form
${\cal X}({\cal P}^{\prime})$ for some projective plane ${\cal P}^{\prime}$ of
the same order $q$. Conversely, the schemes of any two projective planes of
the same order are algebraically isomorphic, and, in view of (32), the
corresponding algebraic isomorphism is unique.

The $2$-extension of the scheme of a projective plane of arbitrary order $q$
was explicitly calculated in [10, Theorem 1.4]. It turned out that its rank
does not depend on $q\geq 3$ and is equal to $208$. Statements (2) and (3) of
the cited theorem yield the following result to be used in Subsection 8.3.

######  Theorem 8.3.

Let ${\cal P}$ be a projective plane and ${\cal X}={\cal X}({\cal P})$. Then
$\bar{\cal X}={\cal X}$ and every algebraic isomorphism from ${\cal X}$ has
the $2$-extension.

In fact, Theorem 8.3 follows from a parametrization of the basis relations of
$\hat{\cal X}$ by certain configurations of points and lines of ${\cal P}$.
Using this parametrization (see [10, Appendix]), the basis relations contained
in the parabolic $e$ can completely be described as in Table 1: each of them
consists of only the pairs $((\beta,\alpha),(\gamma,\alpha))$,
$\alpha,\beta,\gamma\in\Omega$, and the third column contains the number of
basis relations satisfying the conditions in the first two columns.

$\\{\alpha,\beta,\gamma\\}=$ | type | $N$
---|---|---
$\\{x\\}$ | $r(x,x)=s_{0}$ | $1$
$\\{x,y\\}$ | $r(x,y)\in\\{s_{1},s_{2},s_{3}\\}$ | $9$
$\\{x,y,z\\}$ | $r(x,y)=r(y,z)=r(x,z)=s_{1}$ | $2$
$\\{x,y,z\\}$ |  $r(x,y)=s_{1}$, $r(y,z),r(x,z)\in\\{s_{2},s_{3}\\}$ | $2$
Table 1. $s\in S(\hat{\cal X})$ such that $s\subseteq e$.

###  8.3. Proof of Theorem 1.4

Let ${\cal G}=X({\cal P})$ be the incidence graph of a projective plane ${\cal
P}$ of order $q$, i.e., the vertex and edge sets of ${\cal G}$ are $\Omega$
and $s_{2}$, respectively. Thus ${\cal G}$ is a regular bipartite graph of
degree $q+1$ and with $q^{2}+q+1$ vertices in each part, and also
$\operatorname{WL}({\cal G})={\cal X}({\cal P})$.

Let ${\cal P}^{\prime}$ be a projective plane of order $q$, and let $\varphi$
be the algebraic isomorphism from ${\cal X}={\cal X}({\cal P})$ to ${\cal
X}^{\prime}={\cal X}({\cal P}^{\prime})$. By Theorem 8.3, we have $\bar{\cal
X}={\cal X}$, $\bar{{\cal X}^{\prime}}={\cal X}^{\prime}$, and $\varphi$ has
the $2$-extension. By Proposition 8.1, this shows that ${\cal X}\leq\bar{\cal
X}={\cal X}$. Hence, ${\cal X}=\operatorname{W_{1/2}}({\cal X})$, and
similarly, ${\cal X}^{\prime}=\operatorname{W_{1/2}}({\cal X}^{\prime})$. By
Lemma 8.2, this implies that $\varphi$ is sesquiclosed and hence the graphs
${\cal G}$ and ${\cal G}^{\prime}$ are $\operatorname{W_{1/2}}$-equivalent.

###  8.4. A one point extension

We complete the section by calculating a one-point extension of the scheme
${\cal X}={\cal X}({\cal P})$. Let $\alpha\in\Omega$. We claim that

(33) ${\cal X}_{\alpha}=(\hat{\cal X}_{\Gamma})^{f_{\alpha}},$

where $\Gamma$ and $f_{\alpha}$ are as in formula (31). By that formula, it
suffices to verify that every basis relation $r$ of the coherent configuration
on the right-hand side of (33) is a relation of the coherent configuration
${\cal X}_{\alpha}$. Every such $r$ is of the form $(s_{\Gamma})^{f_{\alpha}}$
for some $s\in S(\hat{\cal X})$ contained in the parabolic $e$. Assume first
that $s$ is not one of the two relations in the third row of Table 1. Then

$r=(s_{\Gamma})^{f_{\alpha}}=(\alpha s_{i}\times\alpha s_{j})\cap
s_{k}:=s_{ijk}$

for appropriate $i,j,k\in\\{1,\ldots,4\\}$, and $r$ is a relation of ${\cal
X}_{\alpha}$, see [5, Lemma 3.3.5(2)].

One of the two remaining basis relations $s$ consists of pairs
$((\beta,\alpha),(\gamma,\alpha))$ for which $\alpha$, $\beta$, and $\gamma$
are collinear elements of ${\cal P}$ (three distinct points on the same line
or three distinct lines having a common point), and if $s^{\prime}$ is the
another one, then

$(s_{\Gamma})^{f_{\alpha}}\cup(s^{\prime}_{\Gamma})^{f_{\alpha}}=s_{111}.$

Thus it suffices to verify that only $r=(s_{\Gamma})^{f_{\alpha}}$ is a
relation of ${\cal X}_{\alpha}$. But this immediately follows from the
straightforward equality

$r=(s_{122}\cdot s_{221})\setminus 1_{\alpha s_{1}}.$

Formula (33) is completely proved. It implies that $F({\cal
X}_{\alpha})=\\{\alpha s_{i}:\ i=0,1,2,3\\}$ and the structure of the coherent
configuration ${\cal X}_{\alpha}$ is described by the table

|  $\alpha$ $\alpha s_{0}$ | $\alpha s_{1}$ | $\alpha s_{2}$ | $\alpha s_{3}$
---|---|---|---|---
$\alpha s_{0}$ |  $\alpha$1$\alpha$ |  $\alpha$1$\alpha$ |  $\alpha$1$\alpha$ |  $\alpha$1$\alpha$
---|---|---|---|---
$\alpha s_{1}$ | $1$ | $3$ | $2$ | $2$
$\alpha s_{2}$ | $1$ | $2$ | $2$ | $1$
$\alpha s_{3}$ | $1$ | $2$ | $1$ | $2$

where the element in the row $\alpha s_{i}$ and column $\alpha s_{j}$ is equal
to the cardinality of the set $S({\cal X}_{\alpha})_{\alpha s_{i},\alpha
s_{j}}$.

######  Proposition 8.4.

Any one point extension of the scheme of projective plane of order $q\geq 3$
is a coherent configuration of rank $24$.

One can also verify that the intersection numbers of the one point extension
in Proposition 8.4 do not depend on $q\geq 3$.

## Acknowledgment

The first two authors are supported by Natural Science Foundation of China
(No. 12371019, No. 12161035)

## References

  * [1] G. M. Adel’son-Vel’skii, B. Yu. Weisfeiler, A. A. Lehman, and I. A. Faradžev, _Example of a graph without transitive automorphism group_ , Soviet Math. Dokl. 10 (1969), 440–441.
  * [2] L. Babai, _Graph isomorphism in quasipolynomial time_ , 2016, arXiv:1512.03547 [cs.DS], pp. 1–89.
  * [3] S. Burris and H. P. Sankappanavar, _A course in universal algebra_ , Springer New York, NY, 1984, 2012 update.
  * [4] J. Y. Cai, M. Fürer, and N. Immerman, _An optimal lower bound on the number of variables for graph identification_ , Combinatorica 12 (1992), 389–410.
  * [5] G. Chen and I. Ponomarenko, _Coherent configurations_ , Central China Normal University Press, 2019, the updated version is available at http://www.pdmi.ras.ru/ inp/ccNOTES.pdf.
  * [6] G. Chen, Q. Ren, and I. Ponomarenko, _On multidimensional Schur rings of finite groups_ , 2023, https://doi.org/10.1515/jgth-2023-0032.
  * [7] A. Dawar and D. Vagnozzi, _Generalizations of $k$-dimensional Weisfeiler-Leman stabilization_, Mosc. J. Comb. Number Theory 9 (2020), no. 3, 229–252.
  * [8] S. Evdokimov and I. Ponomarenko, _On highly closed cellular algebras and highly closed isomorphisms_ , Electronic J. Combin. 6 (1999), no. #R18, 1–31.
  * [9] S. Evdokimov and I. Ponomarenko, _Separability number and schurity number of coherent configurations_ , Electronic J. Combin. 7 (2000), no. #R31, 1–33.
  * [10] S. Evdokimov and I. Ponomarenko, _Schemes of a finite projective plane and their extensions_ , St. Petersburg Math. J. 21 (2010), no. 1, 65—93.
  * [11] F. Fuhlbrück, J. Köbler, and O. Verbitsky, _Identifiability of Graphs with Small Color Classes by the Weisfeiler–Leman Algorithm_ , SIAM J. Discrete Math. 35 (2021), no. 3, 1792–1853.
  * [12] M. Grohe, _Descriptive complexity, canonisation, and definable graph structure theory_ , Cambridge University Press, 2017.
  * [13] H. Helfgott, J. Bajpai, and D. Dona, _Graph isomorphisms in quasi-polynomial time_ , 2017, arXiv:1710.04574, pp. 1–67.
  * [14] D. Higman, _Coherent configurations. Part 1: Ordinary representation theory_ , Geom. Dedicata 4 (1975), 1–32.
  * [15] W. Peisert, _All self-complementary symmetric graphs_ , J. Algebra 240 (2001), no. 1, 209–229.
  * [16] I. Ponomarenko, _On the separability of cyclotomic schemes over finite field_ , Algebra Analiz 32 (2020), no. 6, 124–146.
  * [17] I. Ponomarenko, _On the WL-dimension of circulant graphs of prime power order_ , 2022, arXiv:2206.15028 [math.CO]; to appear in Algebraic Combinatorics (2023).
  * [18] B. Weisfeiler, _On construction and identification of graphs_ , Lecture Notes Math., vol. 558, Springer, 1976.
  * [19] B. Yu. Weisfeiler and A. A. Leman, _The reduction of a graph to canonical form and the algebra which appears therein_ , NTI, Ser. 2 9 (1968), 12–16, English translation is available at https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf.