# On the WL-dimension of circulant graphs of prime power order

Ilia Ponomarenko  Steklov Institute of Mathematics at St. Petersburg, Russia
<EMAIL_ADDRESS>
###### Abstract.

The $\operatorname{WL}$-dimension of a graph $X$ is the smallest positive
integer $m$ such that the $m$-dimensional Weisfeiler-Leman algorithm correctly
tests the isomorphism between $X$ and any other graph. It is proved that the
$\operatorname{WL}$-dimension of any circulant graph of prime power order is
at most $3$, and this bound cannot be reduced. The proof is based on using
theories of coherent configurations and Cayley schemes over a cyclic group.

##  1\. Introduction

A (not necessarily undirected) graph is said to be _circulant_ if it is a
Cayley graph over a cyclic group. A main motivation of the present paper is
the following computational problem: given a circulant graph ${\cal G}$ and a
graph ${\cal G}^{\prime}$ test whether ${\cal G}$ is isomorphic to ${\cal
G}^{\prime}$. To the best of the author’s knowledge, there are two polynomial-
time algorithms related to this problem, namely, [6] and [14]. The first
solves the problem for all ${\cal G}^{\prime}$, but largely based on
computational group theory, whereas the second solves the problem only for
circulant ${\cal G}^{\prime}$ but is more or less combinatorial. It is natural
to ask if the problem can be solved in a purely combinatorial way for all
${\cal G}^{\prime}$?

One of the most famous pure combinatorial methods for testing graph
isomorphism was introduced in [18]. This method first uses the classical
Weisfeiler-Leman algorithm, which, for a given graph ${\cal G}$, constructs a
(in a sense) canonical coloring of all pairs of vertices. Then the resulting
coloring is compared with similar coloring constructed for a graph ${\cal
G}^{\prime}$; the graphs ${\cal G}$ and ${\cal G}^{\prime}$ are declared
isomorphic if and only if the colorings have the same sets of colors (this can
be checked quite easily). This method tests isomorphism of ${\cal G}$ and
${\cal G}^{\prime}$ correctly in many (but not all) cases [16].

A generalization of the above method is obtained if the classical Weisfeiler-
Leman algorithm is replaced by its $m$-dimensional ($m\geq 3$) analog, in
which the $m$-tuples of vertices are canonically colored. In this case, for
every graph ${\cal G}$ there is a minimal $m$ with the following property: any
graph ${\cal G}^{\prime}$ such that the set of colors in the canonical
coloring of the $m$-tuples of the vertices of ${\cal G}^{\prime}$ is equal to
that for ${\cal G}$, is isomorphic to ${\cal G}$. This minimal $m$ is called
the _Weisfeiler-Leman dimension_ (the _$\operatorname{WL}$ -dimension_) of
${\cal G}$ and is denoted by $\dim_{\scriptscriptstyle\operatorname{WL}}({\cal
G})$. Now we can refine the question posed in the first paragraph as follows.

Question: is it true that there exists $m\in{\mathbb{N}}$ such that
$\dim_{\scriptscriptstyle\operatorname{WL}}({\cal G})\leq m$ for every
circulant graph ${\cal G}$.

Although we cannot answer this question in full, our main result, presented by
the theorem below, says that for circulant graphs of prime power order (i.e.,
those with the number of vertices equal to the power of a prime), as such a
constant one can take $3$.

######  Theorem 1.1.

The WL-dimension of every circulant graph of prime power order is at most $3$.

Every Paley graph ${\cal G}$ of prime order $p$ is circulant. It is also known
(see, e.g., [2, Subsec. 4.5]) that for some $p$, one can find a graph ${\cal
G}^{\prime}$ of order $p$ such that ${\cal G}$ and ${\cal G}^{\prime}$ are
nonisomorphic but have the same sets of colors in the colorings constructed by
the classical Weisfeiler-Leman algorithm. It follows that
$\dim_{\scriptscriptstyle\operatorname{WL}}({\cal G})>2$, which shows that the
estimate in Theorem 1.1 is sharp. An infinite family of such examples is
obtained if one replaces ${\cal G}$ and ${\cal G}^{\prime}$ by their
lexicographic powers.

Let us discuss some ideas underlying the proof of Theorem 1.1. The classical
Weisfeiler-Leman algorithm can be considered as an (efficiently computable)
functor which given a graph ${\cal G}$ defines a coherent configuration ${\cal
X}=\operatorname{WL}({\cal G})$ (the exact definitions are in Sections 2 and
3). It was proved in [9] that
$\dim_{\scriptscriptstyle\operatorname{WL}}({\cal G})\leq 2$ if and only if
the coherent configuration ${\cal X}$ is separable, i.e., every algebraic
isomorphism from ${\cal X}$ to another coherent configuration is induced by
isomorphism.

A weakening of the property of a coherent configuration to be separable is to
consider not all algebraic isomorphisms, but only those that have one-point
extensions. In this way, we arrive at a concept of sesquiseparable coherent
configuration, which is introduced and studied in Section 4. In fact, if
${\cal G}$ is a vertex-transitive graph and the coherent configuration ${\cal
X}$ is sesquiseparable, then $\dim_{\scriptscriptstyle\operatorname{WL}}({\cal
G})\leq 3$. We show that ${\cal X}$ is sesquiseparable if ${\cal G}$ is a
circulant graph of prime power order.

Now let ${\cal G}$ be a circulant graph. Then the coherent configuration
${\cal X}=\operatorname{WL}({\cal G})$ is a circulant scheme (a Cayley scheme
over a cyclic group; for details, see Section 6) and its structure is fairly
well controlled by the Leung-Man theory (see, for example, [5]). In
particular, ${\cal X}$ can be constructed from trivial and normal circulant
schemes by using tensor and wedge products. The normal circulant schemes and
the operation of wedge (or generalized wreath) product of (association)
schemes have been introduced and studied in [5] and [15], respectively. It
seems that a recent article [13] opens up a way to formulate the Leung-Man
theory directly in terms of graph theory, bypassing association schemes.

When ${\cal G}$ is of prime power order, the tensor product is irrelevant and
we prove that ${\cal X}$ is sesquiseparable by induction on the length of a
decomposition of ${\cal X}$ into a series of the wedge products (Lemma 6.8).
The central part of the proof is focused on studying algebraic and
combinatorial isomorphisms of the wedge product and establishing a sufficient
condition for the wedge product to be sesquiseparable (see Section 5 and
Remark 5.1).

We conclude the introduction with a brief remark about Theorem 6.4 obtained in
the course of the proof and which is of independent interest. In fact, this
theorem says that Theorem 1.1 holds for much wider class of circulant graphs.
Among these graphs are those ${\cal G}$ for which the scheme ${\cal X}$ is the
wedge product of normal circulant schemes (such schemes cover the half of
counterexamples constructed in [4]).

##  2\. Preliminaries

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

###  2.1. Notation

Throughout the paper, $\Omega$ denotes a finite set. For
$\Delta\subseteq\Omega$, the Cartesian product $\Delta\times\Delta$ and its
diagonal are denoted by ${\bf 1}_{\Delta}$ and $1_{\Delta}$, respectively. 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$, and
define $\langle{s}\rangle$ as the minimal (with respect to inclusion)
equivalence relation on $\Omega$, containing $s$. For any collection $S$ of
relations, we denote by $S^{\cup}$ the set of all unions of elements of $S$,
and consider $S^{\cup}$ as a poset with respect to inclusion.

The set of classes of an equivalence relation $e$ on $\Omega$ is denoted by
$\Omega/e$. For $\Delta\subseteq\Omega$, we set $\Delta/e=\Delta/e_{\Delta}$
where $e_{\Delta}={\bf 1}_{\Delta}\cap e$. If the classes of $e_{\Delta}$ are
singletons, $\Delta/e$ is identified with $\Delta$. Given a relation
$s\subseteq{\bf 1}_{\Omega}$, we put

(1) $s_{\Delta/e}=\\{(\Gamma,\Gamma^{\prime})\in{\bf
1}_{\Delta/E}:s_{\Gamma,\Gamma^{\prime}}\neq\varnothing\\},$

where $s_{\Gamma,\Gamma^{\prime}}=s\cap(\Gamma\times\Gamma^{\prime})$. We also
abbreviate $s_{\Gamma}=s_{\Gamma,\Gamma}$. Among all equivalence relations $e$
on $\Omega$, such that

(2) $s=\bigcup_{(\Delta,\Delta^{\prime})\in
s_{\Delta/e}}\Delta\times\Delta^{\prime},$

there is the largest (with respect to inclusion) one, which is denoted by
$\operatorname{Rad}(s)$ and called the radical of $s$. Obviously,
$\operatorname{Rad}(s)\subseteq\langle{s}\rangle$.

For a set $B$ of bijections $f:\Omega\to\Omega^{\prime}$, subsets
$\Delta\subseteq\Omega$ and $\Delta^{\prime}\subseteq\Omega^{\prime}$,
equivalence relations $e$ and $e^{\prime}$ on $\Omega$ and $\Omega^{\prime}$,
respectively, we put

$B^{\Delta/e,\Delta^{\prime}/e^{\prime}}=\\{f^{\Delta/e}:\ f\in B,\
\Delta^{f}=\Delta^{\prime},\ e^{f}=e^{\prime}\\},$

where $f^{\Delta/e}$ is the bijection from $\Delta/e$ onto
$\Delta^{\prime}/e^{\prime}$ induced by $f$; we also abbreviate
$B^{\Delta/e}=B^{\Delta/e,\Delta^{\prime}/e}$ if $\Delta^{\prime}$ is clear
from context.

###  2.2. Coherent configurations

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

  1. (C1)

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

  2. (C2)

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

  3. (C3)

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

The number $|\Omega|$ is called the degree of ${\cal X}$. We say that ${\cal
X}$ is trivial if $S$ consists of $1_{\Omega}$ and its complement (unless
$\Omega$ is not a singleton), homogeneous or a scheme if $1_{\Omega}\in S$,
and commutative if $c_{rs}^{t}=c_{sr}^{t}$ for all $r,s,t\in S$.

###  2.3. Isomorphisms and schurity

A combinatorial isomorphism or, briefly, _isomorphism_ from ${\cal X}$ to a
coherent configuration ${\cal X}^{\prime}=(\Omega^{\prime},S^{\prime})$ is
defined to be a bijection $f:\Omega\rightarrow\Omega^{\prime}$ such that
$s^{f}=\\{(\alpha^{f},\beta^{f}):(\alpha,\beta)\in s\\}$ belongs to
$S^{\prime}$ for all $s\in S$. In this case, ${\cal X}$ and ${\cal
X}^{\prime}$ are said to be isomorphic; the set of all isomorphisms from
${\cal X}$ to ${\cal X}^{\prime}$ is denoted by $\operatorname{Iso}({\cal
X},{\cal X}^{\prime})$. 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}$.

Let $G\leq\operatorname{Sym}(\Omega)$. Denote by $S$ the set of all orbits
$(\alpha,\beta)^{G}$ in the induced action of $G$ on $\Omega\times\Omega$,
where $\alpha,\beta\in\Omega$. Then the pair
$\operatorname{Inv}(G)=(\Omega,S)$ is a coherent configuration. Any coherent
configuration associated with a permutation group in this way is said to be
schurian. Note that ${\cal X}$ is schurian if and only if ${\cal
X}=\operatorname{Inv}(\operatorname{Aut}({\cal X})$.

###  2.4. Extensions

There is a natural partial order $\leq$ on the set of all coherent
configurations on $\Omega$. Namely, given two such coherent configurations
${\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 Y}$ is the _extension_ of ${\cal X}$. The minimal and
maximal elements with respect to this order are the trivial and discrete
coherent configurations, respectively; in the last case, $S$ consists of
singletons. Note that the functor ${\cal X}\to\operatorname{Aut}({\cal X})$
reverse the inclusion, namely,

(3) ${\cal X}\leq{\cal Y}\Rightarrow\operatorname{Aut}({\cal
X})\geq\operatorname{Aut}({\cal Y}).$

###  2.5. Algebraic isomorphisms and separability

A bijection $\varphi:S\rightarrow S^{\prime}$ is called an _algebraic
isomorphism_ from ${\cal X}$ to ${\cal X}^{\prime}$ if for all $r,s,t\in S$,
we have

$c_{r^{\varphi}s^{\varphi}}^{t^{\varphi}}=c_{rs}^{t}.$

In this case, $|\Omega^{\prime}|=|\Omega|$,
$1_{\Omega^{\prime}}=\varphi(1_{\Omega})$, and ${\cal X}^{\prime}$ is
commutative if and only if so is ${\cal X}$. Every
$f\in\operatorname{Iso}({\cal X},{\cal X}^{\prime})$ induces the algebraic
isomorphism $\varphi_{f}:{\cal X}\to{\cal X}^{\prime},$ $s\mapsto s^{f}$; we
put

$\operatorname{Iso}({\cal X},{\cal
X}^{\prime},\varphi)=\\{f\in\operatorname{Iso}({\cal X},{\cal X}^{\prime}):\
\varphi_{f}=\varphi\\}.$

Note that $\operatorname{Aut}({\cal X})=\operatorname{Iso}({\cal X},{\cal
X},\operatorname{id})$, where $\operatorname{id}$ is the trivial (identical)
algebraic automorphism of ${\cal X}$. Finally, for any $\alpha\in\Omega$ and
$\alpha^{\prime}\in\Omega^{\prime}$, we put

$\operatorname{Iso}_{\alpha,\alpha^{\prime}}({\cal X},{\cal
X}^{\prime},\varphi)=\\{f\in\operatorname{Iso}({\cal X}_{,}{\cal
X}^{\prime},\varphi):\ \alpha^{f}=\alpha^{\prime}\\}.$

A coherent configuration ${\cal X}$ is said to be _separable_ if every
algebraic isomorphism from ${\cal X}$ is induced by isomorphism, equivalently,
$\operatorname{Iso}({\cal X},{\cal X}^{\prime},\varphi)\neq\varnothing$ for
all ${\cal X}^{\prime}$ and $\varphi$. Any trivial coherent configuration is
separable.

###  2.6. Relations

The elements of $S$ and of $S^{\cup}$ are called basis relations and
_relations_ of the coherent configuration ${\cal X}$. A unique basis relation
containing the pair $(\alpha,\beta)$ is denoted by $r(\alpha,\beta)$. The set
of all relations is closed with respect to intersections and unions.

Any $\Delta\subseteq\Omega$ such that $1_{\Delta}\in S$ is called a fiber of
${\cal X}$. In view of condition (C1), the set $F=F({\cal X})$ of all fibers
forms a partition of $\Omega$. Every basis relation is contained in the
Cartesian product of two uniquely determined fibers. When ${\cal X}$ is a
scheme, $F=\\{\Omega\\}$, whereas when ${\cal X}$ is schurian, $F$ is just the
set of orbits of the group $\operatorname{Aut}({\cal X})$.

Every algebraic isomorphism $\varphi:{\cal X}\to{\cal X}^{\prime}$ is extended
in a natural way to a poset isomorphism $S^{\cup}\to(S^{\prime})^{\cup}$,
denoted also by $\varphi$. Then $\varphi$ induces a poset isomorphism
$F^{\cup}\to(F^{\prime})^{\cup}$, $\Delta\mapsto\Delta^{\varphi}$, where the
set $\Delta^{\varphi}$ is defined by the equality
$\varphi(1_{\Delta})=1_{\Delta^{\varphi}}$.

Let ${\cal X}\leq{\cal Y}$ and ${\cal X}^{\prime}\leq{\cal Y}^{\prime}$. We
say that the algebraic isomorphism $\varphi$ is extended to an algebraic
isomorphism $\psi:{\cal Y}\to{\cal Y}^{\prime}$ if $\psi(s)=\varphi(s)$ for
all $s\in S$. Note that such an extension is uniquely defined if it exists.

###  2.7. Parabolics and quotients

A relation of ${\cal X}$ that is an equivalence relation on $\Omega$ is called
a _parabolic_ of ${\cal X}$; the set of all parabolics is denoted by
$E=E({\cal X})$. It contains the equivalence relations $\langle{s}\rangle$ and
$\operatorname{Rad}(s)$ for $s\in S^{\cup}$. Given a parabolic $e\in E$, we
define $S_{\Omega/e}=\\{s_{\Omega/e}:\ s\in S\\}$, and
$S_{\Delta}=\\{s_{\Delta}:\ s\in S,\ s_{\Delta}\neq\varnothing\\}$ for any
$\Delta\in\Omega/e$. Then

${\cal X}_{\Omega/e}=(\Omega/e,S_{\Omega/e})\quad\text{and}\quad{\cal
X}_{\Delta}=(\Delta,S_{\Delta})$

are coherent configurations, called a _quotient_ of ${\cal X}$ modulo $e$ and
a _restriction_ of ${\cal X}$ to $\Delta$, respectively. Their fibers are
obtained from fibers $\Gamma\in F$ as follows: $\Gamma_{\Omega/e}$ in the
first case, and $\Gamma\cap\Delta$ in the second. In particular, ${\cal
X}_{\Omega/e}$ and ${\cal X}_{\Delta}$ are schemes if so is ${\cal X}$.

Let $\varphi:{\cal X}\to{\cal X}^{\prime}$ be an algebraic isomorphism and
$e\in E$. Then $\varphi(e)$ is a parabolic of ${\cal X}^{\prime}$ with the
same number of classes. Moreover,

(4)
$\varphi(\langle{s}\rangle)=\langle{\varphi(s)}\rangle\quad\text{and}\quad\varphi(\operatorname{Rad}(s))=\operatorname{Rad}(\varphi(s)).$

The algebraic isomorphism $\varphi$ induces the algebraic isomorphism

$\varphi_{\Omega/e}:{\cal X}_{\Omega/e}\to{\cal
X}^{\prime}_{\Omega^{\prime}/e^{\prime}},\ s_{\Omega/e}\mapsto
s^{\prime}_{\Omega^{\prime}/e^{\prime}},$

where $e^{\prime}=\varphi(e)$ and $s^{\prime}=\varphi(s)$. Now let
$\Delta\in\Omega/e$ and $\Delta^{\prime}\in\Omega/e^{\prime}$. Assume that
there is $\Gamma\in F$ such that
$\Delta\cap\Gamma\neq\varnothing\neq\Delta^{\prime}\cap\Gamma^{\prime}$, where
$\Gamma^{\prime}=\Gamma^{\varphi}$. Then $\varphi$ induces an algebraic
isomorphism

(5) $\varphi_{\Delta,\Delta^{\prime}}:{\cal X}_{\Delta}\to{\cal
X}^{\prime}_{\Delta^{\prime}},\ s_{\Delta}\mapsto
s^{\prime}_{\Delta^{\prime}}.$

This algebraic isomorphisms always exists for all $\Delta$ and
$\Delta^{\prime}$ if ${\cal X}$ (and hence ${\cal X}^{\prime}$) is a scheme.

###  2.8. Sections

Let ${\cal X}$ be a coherent configuration, $e\in E$, and $\Delta$ a class of
a parabolic containing $e$. The quotient set ${\mathfrak{S}}=\Delta/e$ is
called a section of ${\cal X}$. Any element of ${\mathfrak{S}}$ is of the form
$\alpha_{\mathfrak{S}}=\alpha e$ for some $\alpha\in\Delta$; when $\Delta$ is
implicit, we write $\alpha_{\mathfrak{S}}=\varnothing$ for all
$\alpha\not\in\Delta$. For any $s\in S$, we define the relation
$s_{\mathfrak{S}}$ on ${\mathfrak{S}}$ by formula (1). The set of all sections
of ${\cal X}$ is denoted by ${\mathfrak{S}}({\cal X})$. This set is partially
ordered: $\Delta/e\leq\Delta^{\prime}/e^{\prime}$, whenever
$\Delta\subseteq\Delta^{\prime}$ and $e^{\prime}\subseteq e$.

######  Lemma 2.1.

Let ${\cal X}$ be a commutative scheme, ${\mathfrak{S}}\in{\mathfrak{S}}({\cal
X})$, and $s\in S$. Then $\alpha_{\mathfrak{S}}s_{\mathfrak{S}}=(\alpha
s)_{{\mathfrak{S}}}$ for all $\alpha\in\Omega$ such that
$\alpha_{\mathfrak{S}}\neq\varnothing$.

###### Proof.

Obviously, $\alpha_{\mathfrak{S}}s_{\mathfrak{S}}\supseteq(\alpha
s)_{{\mathfrak{S}}}$. Conversely, without loss of generality, we assume that
$s_{\mathfrak{S}}\neq\varnothing$. Let ${\mathfrak{S}}=\Delta/e$ and
$\alpha\in\Delta$. Assume that
$\beta_{\mathfrak{S}}\in\alpha_{\mathfrak{S}}s_{\mathfrak{S}}$ for some
$\beta\in\Delta$. Then there are $\alpha^{\prime}\in\alpha e$ and
$\beta^{\prime}\in\beta e$ such that $(\alpha^{\prime},\beta^{\prime})\in s$.
Then $c_{rs}^{t}\neq 0$ where $r=r(\alpha,\alpha^{\prime})$ and
$t=r(\alpha,\beta^{\prime})$. By the commutativity, $c_{sr}^{t}\neq 0$. It
follows that there exists $\beta^{\prime\prime}\in\beta e$ such that
$(\alpha,\beta^{\prime\prime})\in s$. Thus, $\beta_{\mathfrak{S}}=\beta
e=\beta^{\prime\prime}e\subseteq(\alpha s)_{{\mathfrak{S}}}$.∎

For a section ${\mathfrak{S}}=\Delta/e\in{\mathfrak{S}}({\cal X})$, we put
${\cal X}_{\mathfrak{S}}=({\cal X}_{\Delta})_{\Delta/e}$. Then ${\cal
X}_{\mathfrak{S}}$ is schurian if so is ${\cal X}$. Now let $\varphi:{\cal
X}\to{\cal X}^{\prime}$ be an algebraic isomorphism, $e^{\prime}=\varphi(e)$,
and $\Delta^{\prime}$ a class of the $\varphi$-image of the parabolic of
${\cal X}$, containing the class $\Delta$. The algebraic isomorphism (5) (if
it is defined) induces the algebraic isomorphism

$\varphi_{{\mathfrak{S}},{\mathfrak{S}}^{\prime}}=(\varphi_{\Delta,\Delta^{\prime}})_{\Delta/e,\Delta^{\prime}/e^{\prime}}$

between the coherent configurations ${\cal X}_{\mathfrak{S}}$ and ${\cal
X}^{\prime}_{{\mathfrak{S}}^{\prime}}$.

###  2.9. Point extensions

The point extension ${\cal X}_{\alpha,\beta,\ldots}$ of the coherent
configuration ${\cal X}$ with respect to the points
$\alpha,\beta,\ldots\in\Omega$ is defined to be the smallest coherent
configuration ${\cal Y}=(\Omega,T)$ such that ${\cal Y}\geq{\cal X}$ and
$1_{\alpha},1_{\beta},\ldots\in T$. When the points are irrelevant, we use the
term “point extension” and “one-point extension” if $\alpha=\beta=\ldots$.

Let $\varphi:{\cal X}\to{\cal X}^{\prime}$ be an algebraic isomorphism, and
let $\alpha\in\Omega^{m}$, $\alpha^{\prime}\in{\Omega^{\prime}}^{m}$. We say
that algebraic isomorphism $\psi:{\cal X}_{\alpha}\to{\cal
X}^{\prime}_{\alpha^{\prime}}$ extending $\varphi$ is an
$(\alpha,\alpha^{\prime})$-extension  of $\varphi$ if

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

Note that the $(\alpha,\alpha^{\prime})$-extension is unique if it exists.

When $m=1$, the $(\alpha,\alpha^{\prime})$-extension $\psi$ exists only if
$\psi(r(\alpha,\alpha))=r(\alpha^{\prime},\alpha^{\prime})$, or, equivalently,
$\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}$).

###  2.10. Partly regular coherent configurations.

A coherent configuration ${\cal X}$ is said to be partly regular if there
exists a point $\alpha\in\Omega$ such that $|\alpha s|\leq 1$ for all $s\in
S$; the point $\alpha$ is said to be regular. In this case, the set
$\alpha^{\operatorname{Aut}({\cal X})}$ is a faithful regular orbit of
$\operatorname{Aut}({\cal X})$. Note that every extension of partly regular
coherent configuration is partly regular.

######  Lemma 2.2.

[2, Theorem 3.3.19] Every partly regular coherent configuration is schurian
and separable.

######  Corollary 2.3.

Let ${\cal X}$ be a partly regular coherent configuration and ${\cal
X}^{\prime}\geq{\cal X}$. Then ${\cal X}^{\prime}={\cal X}$ if and only if
$F({\cal X}^{\prime})=F({\cal X})$.

###### Proof.

It suffices to verify the “if” part only. Assume that $F({\cal
X}^{\prime})=F({\cal X})$. We take $\Delta\in F({\cal X})$ that contains a
regular point of ${\cal X}$. Since ${\cal X}$ is schurian (Lemma 2.2),
$\Delta$ is a faithful regular orbit of the group $G=\operatorname{Aut}({\cal
X})$ and hence $|G|=|\Delta|$. The same argument applied to partly regular
coherent configuration ${\cal X}^{\prime}\geq{\cal X}$ and $\Delta\in F({\cal
X}^{\prime})$, shows that $|G^{\prime}|=|\Delta|$, where
$G^{\prime}=\operatorname{Aut}({\cal X}^{\prime})$. Thus,

$|G|=|\Delta|=|G^{\prime}|.$

Since $G^{\prime}\leq G$ (see (3), this yields $G=G^{\prime}$, and ${\cal
X}=\operatorname{Inv}(G)=\operatorname{Inv}(G^{\prime})={\cal X}^{\prime}$. ∎

##  3\. Multidimensional coherent configurations and WL-dimension

The concept of the $\operatorname{WL}$-dimension of a graph was introduced in
[11] in terms of the multidimensional Weisfeiler-Leman algorithm. A goal of
this section is to analyze this definition in terms of coherent
configurations. Our approach is based on the multidimensional coherent
configurations defined in [1]; all the necessary information and results about
them are taken from [12].

Throughout this section, we fix an integer $m\geq 2$, and put
$M=\\{1,\ldots,m\\}$. The monoid of all mappings $\sigma:M\to M$ is denoted by
$\operatorname{Mon}(M)$. Elements of the Cartesian $m$-power $\Omega^{m}$ are
$m$-tuples $x=(x_{1},\ldots,x_{m})$ with $x_{i}\in\Omega$ for all $i\in M$.
For $\alpha\in\Omega$, we put

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

For $X\subseteq\Omega^{m}$ and $\sigma\in M$, we put
$X^{\sigma}=\\{x^{\sigma}:\ x\in X\\}$, where
$x^{\sigma}=(x_{1^{\sigma}},\ldots,x_{m^{\sigma}})$.

###  3.1. The multidimensional Weisfeiler-Leman algorithm

The $m$-dimensional Weisfeiler-Leman algorithm constructs for a given graph
${\cal G}=(\Omega,D)$ a certain coloring $c(m,{\cal G})$ of the set
$\Omega^{m}$; a _coloring_ is meant as a function from $\Omega^{m}$ to a
linear ordered set the elements of which are called _colors_. At the first
stage, an initial coloring $c_{0}=c_{0}(m,{\cal G})$ of $\Omega^{m}$ is
defined by the following condition: given $x,y\in\Omega^{m}$,

(7) $c_{0}(x)=c_{0}(y)\quad\Leftrightarrow\quad\\{(i,j):\ (x_{i},x_{j})\in
D\\}=\\{(i,j):\ (y_{i},y_{j})\in D\\},$

where the pair $(i,j)$ runs over the set $M\times M$. At the second stage,
this 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 G})$ is set to be $c_{i}$.

The coloring $c_{\cal G}=c(m,{\cal G})$ defines a partition
$\operatorname{WL}_{m}({\cal G})$ of $\Omega^{m}$ into the color classes
$X=c_{\cal G}^{-1}(i)$, where $i$ runs over the colors of $c_{\cal G}$. In
particular, the color $c_{\cal G}(X)=c_{\cal G}(x)$ does not depend on $x\in
X$. Since the final coloring is a refinement of the initial one, we have the
following statement.

######  Lemma 3.1.

Let $X\in\operatorname{WL}_{m}({\cal G})$ and $i,j\in M$. Then
$(x_{i},x_{j})\in D$ either for all or for no $x\in X$.

Another important property of the coloring $c_{\cal G}$ is that it defines a
monoid homomorphism
$\tau:\operatorname{Mon}(M)\to\operatorname{Mon}(\operatorname{im}(c_{\cal
G}))$ such that for all $X\in\operatorname{WL}_{m}({\cal G})$ and all
$\sigma\in\operatorname{Mon}(M)$, we have

(8) $c_{\cal G}(X)^{\tau(\sigma)}=c_{\cal G}(X^{\sigma}).$

According with interpretation given in [12], this equality means that the
color of $X$ “knows” the color of $X^{\sigma}$.

Two graphs ${\cal G}$ and ${\cal G}^{\prime}$ are said to be
$\operatorname{WL}_{m}$-equivalent111In terms of [11], this means that the
$m$-dimensional Weisfeiler-Leman algorithm does not distinguish ${\cal G}$ and
${\cal G}^{\prime}$. if $\operatorname{im}(c_{{\cal
G}})=\operatorname{im}(c_{{\cal G}^{\prime}})$. The _Weisfeiler-Leman
dimension_ $\dim_{\scriptscriptstyle\operatorname{WL}}({\cal G})$ of a graph
${\cal G}$ is defined to be the smallest natural $m$ such that every graph
$\operatorname{WL}_{m}$-equivalent to ${\cal G}$ is isomorphic to ${\cal G}$.
It should be noted that these definitions can be extended to the case $m=1$.

For $m=2$, the partition $\operatorname{WL}({\cal
G})=\operatorname{WL}_{2}({\cal G})$ coincides with $S({\cal X})$ for some
coherent configuration on $\Omega$, called the coherent configuration of the
graph ${\cal G}$; in fact, ${\cal X}$ is the smallest coherent configuration
for which $D\in S^{\cup}$. The graphs ${\cal G}$ and ${\cal G}^{\prime}$ are
$\operatorname{WL}_{2}$-equivalent (briefly, $\operatorname{WL}$-equivalent)
if and only if the mapping $X\to c_{{\cal G}^{\prime}}^{-1}(c_{{\cal G}}(X))$
is an algebraic isomorphism from $\operatorname{WL}({\cal G})$ to
$\operatorname{WL}({\cal G}^{\prime})$ (see [9]), where $c_{{\cal
G}}=c(2,{\cal G})$ and $c_{{\cal G}^{\prime}}=c(2,{\cal G}^{\prime})$. A goal
of this section is to prove an analog of the “only if” part of this statement
for $m\geq 3$.

###  3.2. Multidimensional coherent configurations

For a tuple $x\in\Omega^{m}$, denote by $\rho(x)$ the equivalence relation on
$M$ such that $(i,j)\in\rho(x)$ if and only if $x_{i}=x_{j}$. For any
$X_{1},\ldots,X_{m}\subseteq\Omega^{m}$, 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$.

######  Definition 3.2.

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):=\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}$.

For $m=2$, conditions (C1’), (C2’), and (C3’) imply conditions (C1), (C2), and
(C3), respectively. In fact, the coherent configurations are just the $2$-ary
coherent configurations. An example of $m$-ary coherent configuration is a
partition of $\Omega^{m}$ into the orbits of a permutation group on $\Omega$,
acting on $\Omega^{m}$ coordinatewise.

The set of all $m$-ary configurations on $\Omega$ is partially ordered.
Namely, ${\mathfrak{X}}\leq{\mathfrak{Y}}$ if every class of ${\mathfrak{X}}$
is a union of some classes of ${\mathfrak{Y}}$, or equivalently, if
${\mathfrak{X}}^{\cup}\subseteq{\mathfrak{Y}}^{\cup}$, where
${\mathfrak{X}}^{\cup}$ (respectively, ${\mathfrak{Y}}^{\cup}$) is the set of
all unions of classes of ${\mathfrak{X}}$ (respectively, ${\mathfrak{Y}}$).
The largest $m$-ary coherent configuration is the discrete one in which every
class is a singleton; the smallest $m$-ary coherent configuration consists of
the orbits of the symmetric group $\operatorname{Sym}(\Omega)$ in its
componentwise action on $\Omega^{m}$ (this easily follows from (C2) and the
fact that the orbits are in one-to-one correspondence with the equivalence
relations on $M$).

An _algebraic isomorphism_ of $m$-ary coherent configurations ${\mathfrak{X}}$
and ${\mathfrak{X}}^{\prime}$ is a bijection
$\varphi:{\mathfrak{X}}\to{\mathfrak{X}}^{\prime}$ such that for all
$X,X_{0},\ldots,X_{m}\in{\mathfrak{X}}$ and $\sigma\in\operatorname{Mon}(M)$,

(9) $\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 $m=2$, one can easily verify that our definition is agreed with that in
Subsection 2.5.

Note that if $X\in{\mathfrak{X}}$ and $i,j\in M$, then $(i,j)\in\rho(X)$ if
and only if $X^{\sigma}=X$, where $\sigma\in\operatorname{Mon}(M)$ is
identical on $M\setminus\\{i\\}$ and takes $j$ to $i$. It follows that

(10) $\rho(\varphi(X))=\rho(X).$

We extend $\varphi$ to a bijection
${\mathfrak{X}}^{\cup}\to({\mathfrak{X}}^{\prime})^{\cup}$ in a natural way;
then $X\subseteq Y$ implies $\varphi(X)\subseteq\varphi(Y)$ for all
$X,Y\in{\mathfrak{X}}^{\cup}$.

An example of algebraic isomorphism of $m$-ary coherent configurations is
obtained for any two $\operatorname{WL}_{m}$-equivalent graphs ${\cal G}$ and
${\cal G}^{\prime}$. In this case, we have $\operatorname{im}(c_{{\cal
G}})=\operatorname{im}(c_{{\cal G}^{\prime}})$ and the mapping

(11) $\varphi_{{\cal G},{\cal G}^{\prime}}:\operatorname{WL}_{m}({\cal
G})\to\operatorname{WL}_{m}({\cal G}^{\prime}),\ X\mapsto c^{-1}_{{\cal
G}^{\prime}}(c_{{\cal G}}(X)),$

is a bijection. In view of equality (8), it satisfies the first relation in
(9), whereas the second relation follows from the description of the
$m$-dimensional Weisfeiler-Leman algorithm. Thus, $\varphi_{{\cal G},{\cal
G}^{\prime}}$ is an algebraic isomorphism from $\operatorname{WL}_{m}({\cal
G})$ to $\operatorname{WL}_{m}({\cal G}^{\prime})$.

###  3.3. Projections

Let $k\in M$. The _$k$ -projection_ of $\Omega^{m}$ is defined to be the
mapping

$\operatorname{pr}_{k}:\Omega^{m}\to\Omega^{k},\
(\alpha_{1},\ldots,\alpha_{m})\mapsto(\alpha_{1},\ldots,\alpha_{k}).$

The statement below follows from [12, Exercises 2.7,2.11] (and their proofs).
Below, for every $X\subseteq\Omega^{k}$, we put

(12) $\widehat{X}=\\{(x_{1},\ldots,x_{k},x_{k},\ldots,x_{k})\in\Omega^{m}:\
(x_{1},\ldots,x_{k})\in X\\}.$

######  Lemma 3.3.

Let ${\mathfrak{X}}$ be an $m$-ary coherent configuration. Then

$\operatorname{pr}_{k}({\mathfrak{X}})=\\{\operatorname{pr}_{k}(X):\
X\in{\mathfrak{X}}\\}$

is a $k$-ary coherent configuration.222In [1, 12], the partition
$\operatorname{pr}_{k}({\mathfrak{X}})$ is called the $k$-skeleton of
${\mathfrak{X}}$. Moreover,

(13)
$n_{X_{1},\ldots,X_{m}}^{X_{0}}=\sum_{Y_{1},\ldots,Y_{m-k}\in{\mathfrak{X}}}c_{\widehat{X}_{1},\ldots,\widehat{X}_{k},Y_{1},\ldots,Y_{m-k}}^{\widehat{X}_{0}}$

for all $X_{0},X_{1},\ldots,X_{m}\in\operatorname{pr}_{k}({\mathfrak{X}})$.

Let ${\cal G}=(\Omega,D)$ be a graph and $k=2$. From Lemma 3.1, it follows
that $\widehat{D}\in{\mathfrak{X}}^{\cup}$. Therefore,
$D=\operatorname{pr}_{2}(\widehat{D})$ is a relation of the coherent
configuration $\operatorname{pr}_{2}({\mathfrak{X}})$. Thus,

(14) $\operatorname{pr}_{2}(\operatorname{WL}_{m}({\cal
G}))\geq\operatorname{WL}({\cal G}).$

Let $\varphi:{\mathfrak{X}}\to{\mathfrak{X}}^{\prime}$ be an algebraic
isomorphism of $m$-ary coherent configurations. We define a mapping
$\varphi_{k}:\operatorname{pr}_{k}({\mathfrak{X}})\to\operatorname{pr}_{k}({\mathfrak{X}}^{\prime})$
by setting

$\varphi_{k}(\operatorname{pr}_{k}(X))=\operatorname{pr}_{k}(\varphi(X))$

for all $X\in{\mathfrak{X}}$. Note that if
$\operatorname{pr}_{k}(X)=\operatorname{pr}_{k}(Y)$ for some
$Y\in{\mathfrak{X}}$, then $X^{\sigma}=Y^{\sigma}$, where
$\sigma\in\operatorname{Mon}(M)$ takes $i$ to $\min\\{i,k\\}$. For this
$\sigma$, we have

$\operatorname{pr}_{k}(\varphi(X))=\operatorname{pr}_{k}(\varphi(X)^{\sigma})\quad\text{and}\quad\operatorname{pr}_{k}(\varphi(Y))=\operatorname{pr}_{k}(\varphi(Y)^{\sigma}).$

Since also
$\varphi(X)^{\sigma}=\varphi(X^{\sigma})=\varphi(Y^{\sigma})=\varphi(Y)^{\sigma}$,
we conclude that
$\operatorname{pr}_{k}(\varphi(X))=\operatorname{pr}_{k}(\varphi(Y))$. Thus
the mapping $\varphi_{k}$ is well-defined. Reversing the above argument, one
can see that it is injective. Finally, $\varphi_{k}$ is surjective, because it
is a composition of the surjections $\operatorname{pr}_{k}$ and $\varphi$.

######  Lemma 3.4.

Let $\varphi:{\mathfrak{X}}\to{\mathfrak{X}}^{\prime}$ be an algebraic
isomorphism of $m$-ary coherent configurations. Then the bijection
$\varphi_{k}:\operatorname{pr}_{k}({\mathfrak{X}})\to\operatorname{pr}_{k}({\mathfrak{X}}^{\prime})$
is an algebraic isomorphism.

###### Proof.

Let $X\in\operatorname{pr}_{k}({\mathfrak{X}})$ and
$\sigma\in\operatorname{Mon}(K)$ with $K=\\{1,\ldots,k\\}$. Then, obviously,

$X^{\sigma}=\operatorname{pr}_{k}(\widehat{X})^{\sigma}=\operatorname{pr}_{k}(\widehat{X}^{\widehat{\sigma}}),$

where $\widehat{\sigma}\in\operatorname{Mon}(M)$ is the mapping identical on
$M\setminus K$ and coinciding with $\sigma$ on $K$. It follows that

$\varphi_{k}(X^{\sigma})=\varphi_{k}(\operatorname{pr}_{k}(\widehat{X}^{\widehat{\sigma}}))=\operatorname{pr}_{k}(\varphi(\widehat{X}^{\widehat{\sigma}}))=\operatorname{pr}_{k}(\varphi(\widehat{X})^{\widehat{\sigma}})=(\operatorname{pr}_{k}(\varphi(\widehat{X}))^{\sigma}=\varphi_{k}(X)^{\sigma},$

which proves the first part of (9). To prove the second relation, let
$X_{i}\in\operatorname{pr}_{k}({\mathfrak{X}})$, where $i=0$ or $i\in K$. In
view of formula (10), we have
$\rho(\varphi(\widehat{X}_{i}))=\rho(\widehat{X}_{i})$. It follows that
$\varphi(\widehat{X}_{i})=\widehat{X^{\prime}}$ for some
$X^{\prime}\in\operatorname{pr}_{k}({\mathfrak{X}}^{\prime})$. Moreover,

$X^{\prime}=\operatorname{pr}_{k}(\widehat{X}^{\prime})=\operatorname{pr}_{k}(\varphi(\widehat{X}_{i}))=\varphi_{k}(\operatorname{pr}_{k}(\widehat{X}_{i}))=X^{\prime}_{i},$

where $X^{\prime}_{i}=\varphi_{k}(X_{i})$. Consequently,
$\varphi(\widehat{X}_{i})=\widehat{X^{\prime}_{i}}$ for all $i$. Now, the
required statement follows from formula (13). ∎

For arbitrary $K\subseteq M$ and $X\subseteq~{}\Omega^{m}$, one can define
$\operatorname{pr}_{K}(X)=(\operatorname{pr}_{k}(X^{\sigma}))^{\sigma^{-1}}$,
where $\sigma\in\operatorname{Sym}(M)$ is such that
$K^{\sigma}=\\{1,\ldots,k\\}$ with $k=|K|$. Using condition (C2’), one can
easily prove Lemmas 3.3 and 3.4 with $\operatorname{pr}_{k}$ replaced by
$\operatorname{pr}_{K}$.

###  3.4. Residues

Let again $k\in M$ and $y\in\Omega^{m-k}$. For arbitrary
$X\subseteq\Omega^{m}$, we define the residue $X_{y}$ of $X$ with respect to
$y$ to be the set of all $k$-tuples $\bar{x}$ such that
$(\bar{x}_{1},\ldots,\bar{x}_{k},y_{1},\ldots,y_{m-k})\in X$. The statement
below follows from [12, Exercise 2.13] (and its proof).

######  Lemma 3.5.

Let ${\mathfrak{X}}$ be an $m$-ary coherent configuration. Then for any
$y\in\Omega^{m-k}$,

${\mathfrak{X}}_{y}=\\{X_{y}:\ X\in{\mathfrak{X}},\
y\in\operatorname{pr}_{k}(X)\\}$

is a $k$-ary coherent configuration. Moreover,
${\mathfrak{X}}_{y}\geq\operatorname{pr}_{k}({\mathfrak{X}})$ and

(15)
$n_{X_{1},\ldots,X_{m}}^{X_{0}}=\sum_{Y_{1},\ldots,Y_{m-k}\in{\mathfrak{X}}}c_{X_{1}y,\ldots,X_{k}y,Y_{1},\ldots,Y_{m-k}}^{X_{0}y}$

for all $X_{0},X_{1},\ldots,X_{m}\in{\mathfrak{X}}_{y}$, where
$X_{i}y\in{\mathfrak{X}}$ contains $(x_{1},\ldots,x_{k},y_{1}\ldots,y_{m-k})$
for some (and hence for all) $(x_{1},\ldots,x_{k})\in X_{i}$, $i=0,\ldots,k$.

The $k$-ary coherent configuration ${\mathfrak{X}}_{y}$ contains the singleton
$\\{(y_{i},\ldots,y_{i})\\}$, where $i=1,\ldots,m-k$. For $k=2$, it is just
$1_{y_{i}}$, and the coherent configuration $\operatorname{WL}_{m}({\cal
G})_{y}$ is larger than or equal to the smallest coherent configuration on
$\Omega$, for which $D$ and the $1_{y_{i}}$ are relations. The last coherent
configuration is the point extension of $\operatorname{WL}({\cal G})$ with
respect to $y_{1},\ldots,y_{m-2}$. Thus,

(16) $(\operatorname{WL}_{m}({\cal G}))_{y}\geq\operatorname{WL}({\cal
G})_{y_{1},\ldots,y_{m-2}}.$

Let $\varphi:{\mathfrak{X}}\to{\mathfrak{X}}^{\prime}$ be an algebraic
isomorphism of $m$-ary coherent configurations. Assume that
$y^{\prime}\in\varphi_{m-k}(Y)$, where $y\in
Y\in\operatorname{pr}_{m-k}({\mathfrak{X}})$. Then by Lemma 3.4, we have for
every $Z\in{\mathfrak{X}}$,

$\operatorname{pr}_{m-k}(Z)=Y\quad\Leftrightarrow\quad\operatorname{pr}_{m-k}(\varphi(Z))=Y^{\prime}.$

In particular, the sets $\\{Xy:\ X\in{\mathfrak{X}}_{y}\\}$ and
$\\{X^{\prime}y^{\prime}:\
X^{\prime}\in{\mathfrak{X}}^{\prime}_{y^{\prime}}\\}$ are in a one-to-one
correspondence, where $Xy$ and $X^{\prime}y^{\prime}$ are as in Lemma 3.5. We
define a mapping

$\varphi_{y,y^{\prime}}:{\mathfrak{X}}_{y{}}\to{\mathfrak{X}}^{\prime}_{y^{\prime}},\
X\mapsto\varphi(Xy)_{y^{\prime}}.$

Note that for fixed $y$ and $y^{\prime}$, the mappings
${\mathfrak{X}}_{y}\to{\mathfrak{X}}$, $X\mapsto Xy$, and
${\mathfrak{X}}^{\prime}_{y^{\prime}}\to{\mathfrak{X}}^{\prime}$,
$X^{\prime}\mapsto X^{\prime}y^{\prime}$, are injective. By the choice of $y$
and $y^{\prime}$, this shows that $\varphi_{y,y^{\prime}}$ is a bijection.

######  Lemma 3.6.

Let $\varphi:{\mathfrak{X}}\to{\mathfrak{X}}^{\prime}$ be an algebraic
isomorphism of $m$-ary coherent configurations,
$Y\in\operatorname{pr}_{m-k}({\mathfrak{X}})$, and
$Y^{\prime}=\varphi_{m-k}(Y)$. Then for every $y\in Y$ and every
$y^{\prime}\in Y^{\prime}$, the bijection
$\varphi_{y,y^{\prime}}:{\mathfrak{X}}_{y}\to{\mathfrak{X}}^{\prime}_{y^{\prime}}$
is an algebraic isomorphism. Moreover, it extends the algebraic isomorphism
$\varphi_{k}$.

###### Proof.

Let $X\in{\mathfrak{X}}_{y}$ and $\sigma\in\operatorname{Mon}(K)$ with
$K=\\{1,\ldots,k\\}$. Then, obviously, $X^{\sigma}y=(Xy)^{\widehat{\sigma}}$,
where $\widehat{\sigma}\in\operatorname{Mon}(M)$ is the mapping identical on
$M\setminus K$ and coinciding with $\sigma$ on $K$. It follows that

$\varphi_{y,y^{\prime}}(X^{\sigma})=\varphi(X^{\sigma}y)_{y^{\prime}}=\varphi((Xy)^{\widehat{\sigma}})_{y^{\prime}}=(\varphi(Xy)^{\widehat{\sigma}})_{y^{\prime}}=(\varphi(X_{y})_{y^{\prime}})^{\sigma}=\varphi_{y,y^{\prime}}(X)^{\sigma},$

which proves the first part of (9). To prove the second relation, it suffices
to note that $\varphi(Xy)=\varphi_{y,y^{\prime}}(X)_{y^{\prime}}$ and make use
of formula (15). ∎

###  3.5. Reduction to coherent configurations

The main result of this subsection (Theorem 3.7 below) establishes a necessary
condition for two graphs to be $\operatorname{WL}_{m}$-equivalent in terms of
their coherent configurations.

######  Theorem 3.7.

Let ${\cal G}=(\Omega,D)$ and ${\cal G}^{\prime}=(\Omega^{\prime},D^{\prime})$
be $\operatorname{WL}_{m}$-equivalent graphs, $m\geq 2$. Then there is an
algebraic isomorphism $\varphi:\operatorname{WL}({\cal
G})\to\operatorname{WL}({\cal G}^{\prime})$ such that $\varphi(D)=D^{\prime}$.
Moreover, if $x\in\Omega^{m}$ and $x^{\prime}\in{\Omega^{\prime}}^{m}$ are
such that $c_{{\cal G}}(x)=c_{{\cal G}^{\prime}}(x^{\prime})$, then $\varphi$
has the $(y,y^{\prime})$-extension with $y=\operatorname{pr}_{m-2}(x)$ and
$y^{\prime}=\operatorname{pr}_{m-2}(x^{\prime})$.

###### Proof.

Denote by $\psi$ the algebraic isomorphism defined by (11). By Lemma 3.4 for
$k=2$, there is an algebraic isomorphism
$\psi_{2}:\operatorname{pr}_{2}(\operatorname{WL}_{m}({\cal
G}))\to\operatorname{pr}_{2}(\operatorname{WL}_{m}({\cal G}^{\prime}))$. Note
that $D$ is a relation of the coherent configuration ${\cal
X}=\operatorname{WL}({\cal G})$ (see formula (14)), and also

$\psi_{2}(D)=\operatorname{pr}_{2}(\psi(\widehat{D})=\operatorname{pr}_{2}(\psi(\widehat{D^{\prime}})=D^{\prime}.$

Since ${\cal X}$ is the smallest coherent configuration containing $D$ as a
relation, $\psi_{2}({\cal X}))$ is the smallest coherent configuration
containing $D^{\prime}$ as a relation, i.e., $\psi_{2}({\cal X})$ is equal to
${\cal X}^{\prime}=\operatorname{WL}({\cal G}^{\prime})$. Thus as the required
algebraic isomorphism $\varphi$ one can take the restriction of $\psi_{2}$ to
${\cal X}$.

Now, let $x\in\Omega^{m}$ and $x^{\prime}\in{\Omega^{\prime}}^{m}$ be such
that $c_{{\cal G}}(x)=c_{{\cal G}^{\prime}}(x^{\prime})$. Then the algebraic
isomorphism $\psi$ takes the class $X\ni x$ to the class $X^{\prime}\ni
x^{\prime}$. It follows that

$\psi_{m-2}(\operatorname{pr}_{m-2}(X))=\operatorname{pr}_{m-2}(X^{\prime}).$

Since $y\in\operatorname{pr}_{m-2}(X)$ and
$y^{\prime}\in\operatorname{pr}_{m-2}(X^{\prime})$, we can apply Lemma 3.6 to
find an algebraic isomorphism

$\psi_{y,y^{\prime}}:\operatorname{WL}_{m}({\cal
G})_{y}\to\operatorname{WL}_{m}({\cal G}^{\prime})_{y^{\prime}}$

which extends $\psi_{2}$ and hence extends $\varphi$. On the other hand, the
inclusion (16) yields

$\operatorname{WL}_{m}({\cal G})_{y}\geq{\cal
X}_{y_{1},\ldots,y_{m-2}}\quad\text{and}\quad\operatorname{WL}_{m}({\cal
G}^{\prime})_{y^{\prime}}\geq{\cal
X}^{\prime}_{y^{\prime}_{1},\ldots,y^{\prime}_{m-2}}.$

Furthermore, the pairs $(1,2),(1,i+2)$ belong to the equivalence relation
$\rho(1_{y_{i}}y)$. By formula (10), this implies that these pairs also belong
to $\rho(\psi(1_{y_{i}}y))$. It follows that
$\psi_{y,y^{\prime}}(1_{y_{i}})=\psi(1_{y_{i}}y)_{y^{\prime}}=1_{y^{\prime}_{i}}$
for $i=1,\ldots,m-2$. Thus,

$\psi_{y,y^{\prime}}({\cal X}_{y_{1},\ldots,y_{m-2}})={\cal
X}^{\prime}_{y^{\prime}_{1},\ldots,y^{\prime}_{m-2}},$

and the restriction of $\psi_{y,y^{\prime}}$ to ${\cal
X}_{y^{\prime}_{1},\ldots,y^{\prime}_{m-2}}$ is the $(y,y^{\prime})$-extension
of $\varphi$. ∎

##  4\. Sesquiclosed coherent configurations and algebraic isomorphisms

###  4.1. Sesquiclosed algebraic isomorphisms

In this subsection, we introduce a notion of a sesquiclosed algebraic
isomorphism, which weakens the notion of an (algebraic) $2$-isomorphism
studied in [2, Section 3.5.2].

######  Definition 4.1.

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}$.

Examples of sesquiclosed algebraic isomorphisms arise naturally in the context
of $\operatorname{WL}_{3}$-equivalent graphs, namely the following statement
is an almost immediate consequence of Theorem 3.7.

######  Lemma 4.2.

Let ${\cal G}$ and ${\cal G}^{\prime}$ be $\operatorname{WL}_{3}$-equivalent
graphs. Assume that ${\cal G}$ is vertex-transitive. Then there is a
sesquiclosed algebraic isomorphism $\varphi:\operatorname{WL}({\cal
G})\to\operatorname{WL}({\cal G}^{\prime})$ such that $\varphi(D)=D^{\prime}$,
where $D$ and $D^{\prime}$ are the arc sets of ${\cal G}$ and ${\cal
G}^{\prime}$, respectively.

###### Proof.

By the first part of Theorem 3.7 (for $m=3$), there is an algebraic
isomorphism $\varphi:\operatorname{WL}({\cal G})\to\operatorname{WL}({\cal
G}^{\prime})$ such that $\varphi(D)=D^{\prime}$. It suffices to verify that
$\varphi$ has $(\alpha,\alpha^{\prime})$-extension for all $\alpha\in\Omega$
and $\alpha^{\prime}\in\Omega^{\prime}$. Because ${\cal G}$ is vertex-
transitive, $X=\operatorname{Diag}(\Omega^{3})$ is a class of
$\operatorname{WL}_{3}({\cal G})$. Since ${\cal G}$ and ${\cal G}^{\prime}$ be
$\operatorname{WL}_{3}$-equivalent,
$X^{\prime}=\operatorname{Diag}({\Omega^{\prime}}^{3})$ is a class of
$\operatorname{WL}_{3}({\cal G}^{\prime})$, and $c_{{\cal G}}(X)=c_{{\cal
G}^{\prime}}(X^{\prime})$. It follows that $c_{{\cal G}}(x)=c_{{\cal
G}^{\prime}}(x^{\prime})$, where $x=(\alpha,\alpha,\alpha)$ and
$x^{\prime}=(\alpha^{\prime},\alpha^{\prime},\alpha^{\prime})$. By the second
part of Theorem 3.7, this implies that $\varphi$ has
$(\alpha,\alpha^{\prime})$-extension. ∎

Not every algebraic isomorphism is sesquiclosed, e.g., a straightforward
computation shows that a unique nontrivial algebraic automorphism of the
antisymmetric scheme of rank $3$ and degree $15$ is not sesquiclosed. On the
other hand, [2, Lemma 3.5.25] shows that every algebraic $2$-isomorphism is
sesquiclosed.

######  Lemma 4.3.

Let ${\cal X}$ be a coherent configuration, $\varphi:{\cal X}\to{\cal
X}^{\prime}$ a sesquiclosed algebraic isomorphism,
${\mathfrak{S}}\in{\mathfrak{S}}({\cal X})$, and
${\mathfrak{S}}^{\prime}\in{\mathfrak{S}}({\cal X}^{\prime})$. Assume that
$\varphi$ induces an algebraic isomorphism $\psi:{\cal
X}_{{\mathfrak{S}}}\to{\cal X}^{\prime}_{{\mathfrak{S}}^{\prime}}$. Then
$\psi$ is sesquiclosed.

###### Proof.

Let $\bar{\alpha}\in\bar{\Delta}\in F({\cal X}_{{\mathfrak{S}}})$ and
$\bar{\alpha}^{\prime}\in\bar{\Delta}^{\prime}\in F({\cal
X}^{\prime}_{{\mathfrak{S}}^{\prime}})$ be such that
$\bar{\Delta}^{\psi}=\bar{\Delta}^{\prime}$. Then there exist $\Delta\in
F({\cal X})$ and $\Delta^{\prime}\in F({\cal X}^{\prime})$ for which

$\Delta_{\mathfrak{S}}=\bar{\Delta},\quad\Delta^{\prime}_{{\mathfrak{S}}^{\prime}}=\bar{\Delta}^{\prime},\quad\Delta^{\varphi}=\Delta^{\prime}.$

Let $\alpha\in\Delta$ and $\alpha^{\prime}\in\Delta^{\prime}$ be such that
$\alpha_{{\mathfrak{S}}}=\overline{\alpha}$ and
$\alpha^{\prime}_{{\mathfrak{S}}^{\prime}}=\alpha^{\prime}$. The algebraic
isomorphism $\varphi$ being sesquiclosed has
$(\alpha,\alpha^{\prime})$-extension $\varphi_{\alpha,\alpha^{\prime}}$. Since
$\varphi$ induces $\psi$, one can define the algebraic isomorphism

$\psi_{\overline{\alpha},\overline{\alpha}^{\prime}}=(\varphi_{\alpha,\alpha^{\prime}})_{{\mathfrak{S}},{\mathfrak{S}}^{\prime}}$

from $({\cal X}_{\alpha})_{{\mathfrak{S}}}$ to $({\cal
X}^{\prime}_{\alpha^{\prime}})_{{\mathfrak{S}}^{\prime}}$. For any
$\overline{s}\in S({\cal X}_{\mathfrak{S}})$, we have

$\psi_{\overline{\alpha},\overline{\alpha}^{\prime}}(\overline{s})=(\varphi_{\alpha,\alpha^{\prime}})_{{\mathfrak{S}},{\mathfrak{S}}^{\prime}}(s_{\mathfrak{S}})=(\varphi_{\alpha,\alpha^{\prime}}(s))_{{\mathfrak{S}}^{\prime}}=\varphi(s)_{{\mathfrak{S}}^{\prime}}=\psi(s_{\mathfrak{S}}),$

where $s\in S$ is such that $s_{\mathfrak{S}}=\overline{s}$, and

$\psi_{\alpha,\alpha^{\prime}}(1_{\bar{\alpha}})=(\varphi_{\alpha,\alpha^{\prime}})_{\mathfrak{S}}((1_{\alpha})_{\mathfrak{S}})=(\varphi_{\alpha,\alpha^{\prime}}(1_{\alpha}))_{\mathfrak{S}}=(1_{\alpha^{\prime}})_{\mathfrak{S}}=1_{\bar{\alpha}^{\prime}},$

Thus the algebraic isomorphism $\psi_{\bar{\alpha},\bar{\alpha}^{\prime}}$ is
the $(\bar{\alpha},\bar{\alpha}^{\prime})$-extension of the algebraic
isomorphism $\psi$.∎

A coherent configuration ${\cal X}$ is said to be sesquiseparable if every
sesquiclosed algebraic isomorphism is induced by isomorphism. Clearly, every
separable coherent configuration is sesquiseparable; the converse is not true,
see Subsection 6.2.

######  Lemma 4.4.

A coherent configuration ${\cal X}$ is sesquiseparable if every one-point
extension of ${\cal X}$ is separable.

###### Proof.

Let $\varphi:{\cal X}\to{\cal X}^{\prime}$ be a sesquiclosed algebraic
isomorphism. Then it has a $(\alpha,\alpha^{\prime})$-extension
$\varphi_{\alpha,\alpha^{\prime}}$ for all appropriate $\alpha$ and
$\alpha^{\prime}$. Since the coherent configuration ${\cal X}_{\alpha}$ is
separable, $\varphi_{\alpha,\alpha^{\prime}}$ is induced by a certain
isomorphism $f$. Then $s^{f}=\varphi_{\alpha,\alpha^{\prime}}(s)=\varphi(s)$
for all $s\in S$. Hence, $f\in\operatorname{Iso}({\cal X},{\cal
X}^{\prime},\varphi)$ and ${\cal X}$ is sesquiseparable.∎

###  4.2. Sesquiclosed coherent configurations

In parallel with sesquiclosed algebraic isomorphisms, we introduce a notion
which weakens the notion of $2$-closed coherent configuration studied in [2,
Section 3.5.3]. Namely, in Lemma 3.5.25 there, it was proved that a coherent
configuration ${\cal X}$ is $2$-closed only if for every $\alpha\in\Omega$ the
following conditions are satisfied:

  1. (S1)

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

  2. (S2)

the trivial algebraic automorphism of ${\cal X}$ is sesquiclosed.

######  Definition 4.5.

A coherent configuration ${\cal X}$ satisfying (S1) and (S2) for all $\alpha$
is said to be sesquiclosed.

Though conditions (S1) and (S2) are satisfied in the schurian case, not every
sesquiclosed coherent configuration is schurian, for example, those are
coherent configurations constructed in [2, Theorem 4.2.4]. The same example
shows that the class of sesquiclosed coherent configurations is not invariant
with respect to algebraic isomorphisms.

######  Lemma 4.6.

Let ${\cal X}$ be a sesquiclosed coherent configuration and
${\mathfrak{S}}\in{\mathfrak{S}}({\cal X})$. Then the coherent configuration
${\cal X}_{\mathfrak{S}}$ is sesquiclosed.

###### Proof.

Condition (S2) is satisfied for ${\cal X}={\cal X}_{\mathfrak{S}}$ by Lemma
4.3 with ${\cal X}={\cal X}^{\prime}$ and $\varphi=\operatorname{id}$. Assume
that condition (S1) is not satisfied for ${\cal X}_{\mathfrak{S}}$. Then there
are $\alpha\in\Omega$ and $s\in S$ such that

(17) $\varnothing\neq\alpha_{\mathfrak{S}}s_{\mathfrak{S}}\not\in F(({\cal
X}_{\mathfrak{S}})_{\alpha_{\mathfrak{S}}}).$

Without loss of generality, we may assume that $\alpha s\neq\varnothing$. By
condition (S1), we have $\alpha s\in F({\cal X}_{\alpha})$ and hence $(\alpha
s)_{\mathfrak{S}}\in F(({\cal X}_{\alpha})_{\mathfrak{S}})$. However, $({\cal
X}_{\alpha})_{\mathfrak{S}}\geq({\cal
X}_{\mathfrak{S}})_{\alpha_{\mathfrak{S}}}$. Therefore, $(\alpha
s)_{\mathfrak{S}}$ is contained in some $\Delta\in F(({\cal
X}_{\mathfrak{S}})_{\alpha_{\mathfrak{S}}})$. Since $(\alpha
s)_{\mathfrak{S}}\subseteq\alpha_{\mathfrak{S}}s_{\mathfrak{S}}$, we have

(18) $(\alpha
s)_{\mathfrak{S}}\subseteq\Delta\subseteq\alpha_{\mathfrak{S}}s_{\mathfrak{S}}.$

In view of (17), there is $\Delta^{\prime}\in F(({\cal
X}_{\mathfrak{S}})_{\alpha_{\mathfrak{S}}})$ such that
$\Delta\neq\Delta^{\prime}\subseteq\alpha_{\mathfrak{S}}s_{\mathfrak{S}}$.
Take any point $\alpha^{\prime}$ for which $(\alpha^{\prime}s)_{\mathfrak{S}}$
intersects $\Delta^{\prime}$. Then as above

(19)
$(\alpha^{\prime}s)_{\mathfrak{S}}\subseteq\Delta^{\prime}\subseteq\alpha_{\mathfrak{S}}s_{\mathfrak{S}}.$

Note that $\alpha$ and $\alpha^{\prime}$ lie in the same fiber of ${\cal X}$,
because $\alpha s\neq\varnothing\neq\alpha^{\prime}s$ and $s\in S$. By
condition (S2), the trivial algebraic automorphism of ${\cal X}$ has the
$(\alpha,\alpha^{\prime})$-extension; denote it by $\psi$. Then there is an
algebraic isomorphism $\psi_{\mathfrak{S}}:({\cal
X}_{\alpha})_{\mathfrak{S}}\to({\cal X}_{\alpha^{\prime}})_{\mathfrak{S}}$
that induces the trivial algebraic automorphism of ${\cal X}_{\mathfrak{S}}$.
Using formulas (18) and (19), we obtain

$\Delta^{\psi_{\mathfrak{S}}}\supseteq((\alpha
s)_{\mathfrak{S}})^{\psi_{\mathfrak{S}}}=((\alpha
s)^{\psi})_{\mathfrak{S}}=(\alpha^{\prime}s)_{\mathfrak{S}}\subseteq\Delta^{\prime},$

whence $\Delta=\Delta^{\prime}$, a contradiction. ∎

######  Lemma 4.7.

Let ${\cal X}$ be a sesquiclosed coherent configuration and $\varphi:{\cal
X}\to{\cal X}^{\prime}$ a sesquiclosed algebraic isomorphism. Then the
coherent configuration ${\cal X}^{\prime}$ is sesquiclosed.

###### Proof.

Let $\alpha^{\prime}\in\Omega^{\prime}$ and $s^{\prime}\in S^{\prime}$. The
algebraic isomorphism $\varphi:{\cal X}\to{\cal X}^{\prime}$ being
sesquiclosed, has an $(\alpha,\alpha^{\prime})$-extension $\psi$ for some
$\alpha\in\Omega$ such that $\alpha s\neq\varnothing$, where
$s=\varphi^{-1}(s^{\prime})$. Since the coherent configuration ${\cal X}$ is
sesquiclosed, $\alpha s\in F({\cal X}_{\alpha})$. Consequently, the set
$\alpha^{\prime}s^{\prime}=\psi(\alpha s)$ belongs to $F({\cal
X}^{\prime}_{\alpha^{\prime}})$. This shows that ${\cal X}^{\prime}$ satisfies
condition (S1).

Let $\alpha^{\prime},\alpha^{\prime\prime}\in\Omega^{\prime}$ lie in the same
fiber of ${\cal X}^{\prime}$. The algebraic isomorphism $\varphi$ being
sesquiclosed, has an $(\alpha,\alpha^{\prime})$-extension $\psi$ and
$(\alpha,\alpha^{\prime\prime})$-extension $\psi^{\prime}$ for some
$\alpha\in\Omega$. It follows that $\psi^{-1}\psi^{\prime}$ is the
$(\alpha^{\prime},\alpha^{\prime\prime})$-extension of the trivial algebraic
automorphism of ${\cal X}^{\prime}$. This shows that ${\cal X}^{\prime}$
satisfies condition (S2). ∎

When a coherent configuration ${\cal X}$ is not sesquiclosed, one can
construct a uniquely determined sesquiclosed extension ${\cal X}^{\prime}$
such that $\operatorname{Aut}({\cal X}^{\prime})=\operatorname{Aut}({\cal
X})$. However, the explicit definition of ${\cal X}^{\prime}$ is outside the
scope of the present paper.

###  4.3. Partly regular sections

In this subsection, we prove two auxiliary lemmas for the sections of
sesquiclosed schemes, the restriction to which is partly regular. They will be
used in Subsection 5.4.

######  Lemma 4.8.

Let ${\cal X}$ be a commutative sesquiclosed scheme,
${\mathfrak{S}}_{0},{\mathfrak{S}}\in{\mathfrak{S}}({\cal X})$, and $\alpha$ a
point such that $\alpha_{{\mathfrak{S}}_{0}}\neq\varnothing$. Assume that
${\mathfrak{S}}_{0}\leq{\mathfrak{S}}$ and $(({\cal
X}_{\mathfrak{S}})_{\alpha_{\mathfrak{S}}})_{{\mathfrak{S}}_{0}}$ is partly
regular. Then

(20) $(({\cal
X}_{\mathfrak{S}})_{\alpha_{\mathfrak{S}}})_{{\mathfrak{S}}_{0}}=(({\cal
X}_{\alpha})_{\mathfrak{S}})_{{\mathfrak{S}}_{0}}.$

###### Proof.

The obvious inclusion $({\cal
X}_{\mathfrak{S}})_{\alpha_{\mathfrak{S}}}\leq({\cal
X}_{\alpha})_{\mathfrak{S}}$ implies $(({\cal
X}_{\mathfrak{S}})_{\alpha_{\mathfrak{S}}})_{{\mathfrak{S}}_{0}}\leq(({\cal
X}_{\alpha})_{\mathfrak{S}})_{{\mathfrak{S}}_{0}}.$ The coherent configuration
on the left-hand side is partly regular by the hypothesis. By Corollary 2.3,
it suffices to verify that every fiber $\Delta$ of $(({\cal
X}_{\alpha})_{\mathfrak{S}})_{{\mathfrak{S}}_{0}}$ is also a fiber of $(({\cal
X}_{\mathfrak{S}})_{\alpha_{\mathfrak{S}}})_{{\mathfrak{S}}_{0}}$.

By condition (S1), one can find $s\in S$ such that $\Delta=(\alpha
s)_{{\mathfrak{S}}_{0}}$. Since ${\cal X}$ is commutative, Lemma 2.1 yields

$\Delta=(\alpha s)_{{\mathfrak{S}}_{0}}=((\alpha
s)_{{\mathfrak{S}}})_{{\mathfrak{S}}_{0}}=(\alpha_{\mathfrak{S}}s_{\mathfrak{S}})_{{\mathfrak{S}}_{0}}.$

On the other hand, the scheme ${\cal X}_{\mathfrak{S}}$ is sesquiclosed by
Lemma 4.6. Therefore, the set $\alpha_{\mathfrak{S}}s_{\mathfrak{S}}$ is a
fiber of the coherent configuration $({\cal
X}_{\mathfrak{S}})_{\alpha_{\mathfrak{S}}}$. It follows that
$(\alpha_{\mathfrak{S}}s_{\mathfrak{S}})_{{\mathfrak{S}}_{0}}$ and hence
$\Delta$ is a fiber of the coherent configuration $(({\cal
X}_{\mathfrak{S}})_{\alpha_{\mathfrak{S}}})_{{\mathfrak{S}}_{0}}$. ∎

######  Lemma 4.9.

Let ${\cal X}$ and ${\cal X}^{\prime}$ be schemes, $\varphi:{\cal X}\to{\cal
X}^{\prime}$ an algebraic isomorphism having an
$(\alpha,\alpha^{\prime})$-extension $\varphi_{\alpha,\alpha^{\prime}}$ for
some $\alpha$ and $\alpha^{\prime}$, and
$f\in\operatorname{Iso}_{\alpha,\alpha^{\prime}}({\cal X},{\cal
X}^{\prime},\varphi)$. Assume that

  1. (i)

${\cal X}$ is schurian,

  2. (ii)

$({\cal X}_{\alpha})_{\mathfrak{S}}$ is partly regular for some
${\mathfrak{S}}\in{\mathfrak{S}}({\cal X})$ such that
$\alpha_{\mathfrak{S}}\neq\varnothing$.

Then

(21) $\operatorname{Iso}({\cal X}_{\alpha},{\cal
X}^{\prime}_{\alpha^{\prime}},\varphi_{\alpha,\alpha^{\prime}})^{\mathfrak{S}}=\operatorname{Iso}(({\cal
X}_{\alpha})_{{\mathfrak{S}}},({\cal
X}^{\prime}_{\alpha^{\prime}})_{{\mathfrak{S}}^{\prime}},(\varphi_{\alpha,\alpha^{\prime}})_{{\mathfrak{S}},{\mathfrak{S}}^{\prime}}),$

where ${\mathfrak{S}}^{\prime}={\mathfrak{S}}^{f}$.

###### Proof.

From the hypothesis, it follows that $f^{\mathfrak{S}}$ belongs to the sets on
the left- and right hand sides of (21); in particular, these sets are not
empty. Consequently,

$|\operatorname{Iso}({\cal X}_{\alpha},{\cal
X}^{\prime}_{\alpha^{\prime}},\varphi_{\alpha,\alpha^{\prime}})^{\mathfrak{S}}|=|\operatorname{Aut}({\cal
X}_{\alpha})^{\mathfrak{S}}|,$

and

$|\operatorname{Iso}(({\cal X}_{\alpha})_{{\mathfrak{S}}},({\cal
X}^{\prime}_{\alpha^{\prime}})_{{\mathfrak{S}}^{\prime}},(\varphi_{\alpha,\alpha^{\prime}})_{{\mathfrak{S}},{\mathfrak{S}}^{\prime}})|=|\operatorname{Aut}(({\cal
X}_{\alpha})_{{\mathfrak{S}}})|$

and it suffices to verify that

(22) $\operatorname{Aut}(({\cal
X}_{\alpha})_{\mathfrak{S}})=\operatorname{Aut}({\cal
X}_{\alpha})^{{\mathfrak{S}}}.$

Obviously, $\operatorname{Aut}({\cal
X}_{\alpha})^{{\mathfrak{S}}}\leq\operatorname{Aut}(({\cal
X}_{\alpha})_{\mathfrak{S}})$. Conversely, by condition (ii), the group
$\operatorname{Aut}(({\cal X}_{\alpha})_{\mathfrak{S}})$ has a faithful
regular orbit $\Delta$. Since the coherent configuration $({\cal
X}_{\alpha})_{\mathfrak{S}}$ is schurian (Lemma 2.2),
$\Delta=\Lambda_{\mathfrak{S}}$ for some fiber $\Lambda\in F({\cal
X}_{\alpha})$. By the first part of condition (i), $\Lambda$ is an orbit of
the group $\operatorname{Aut}({\cal X}_{\alpha})$. It follows that
$\Delta=\Lambda_{\mathfrak{S}}$ is an orbit of the group
$\operatorname{Aut}({\cal
X}_{\alpha})^{\mathfrak{S}}\leq\operatorname{Aut}(({\cal
X}_{\alpha})_{\mathfrak{S}})$. This proves (22), because $\Delta$ is a
faithful regular orbit of the last group.∎

##  5\. $e_{1}/e_{0}$-condition

###  5.1. Definition

Let ${\cal X}=(\Omega,S)$ be a scheme, and let $e_{0}$ and $e_{1}$ be
parabolics of ${\cal X}$ such that $e_{0}\subseteq e_{1}$. Following [6], we
say that ${\cal X}$ satisfies the _$e_{1}/e_{0}$ -condition_ if for all $s\in
S$,

$s\cap e_{1}=\varnothing\quad\Rightarrow\quad
e_{0}\subseteq\operatorname{Rad}(s).$

This is always true if $e_{0}=1_{\Omega}$ or $e_{1}={\bf 1}_{\Omega}$; in the
other cases, we say that the $e_{1}/e_{0}$-condition is satisfied
nontrivially. When $e_{0}=e_{1}$, the condition exactly means that the scheme
${\cal X}$ is isomorphic to the wreath product ${\cal X}_{\Delta}\wr{\cal
X}_{\Omega/e_{0}}$ for any $\Delta\in\Omega/e_{0}$. Finally, we note that if
$e^{\prime}_{0}\subseteq e_{0}$ and $e^{\prime}_{1}\supseteq e_{1}$ are
parabolics, then ${\cal X}$ satisfies also the
$e^{\prime}_{1}/e^{\prime}_{0}$-condition.

######  Remark 5.1.

The $e_{1}/e_{0}$-condition provides internal definition of the operation
wedge product of association schemes, introduced and studied in [15]. Namely,
${\cal X}$ satisfies the $e_{1}/e_{0}$-condition if and only if ${\cal X}$ is
isomorphic to the wedge product of the schemes ${\cal X}_{\Delta}$,
$\Delta\in\Omega/e_{1}$, and the scheme ${\cal X}_{\Omega/e_{0}}$.

In the sequel, we simplify the notation as follows. First, we put
$\Omega_{0}=\Omega/e_{0}$, ${\cal X}_{0}={\cal X}_{\Omega/e_{0}}$, and
$\Omega_{1}=\Omega/e_{1}$. Second, for every $\Delta\in\Omega_{1}$, we put
$\Delta_{0}=\Delta/e_{0}$. Finally, for an algebraic isomorphism
$\varphi:{\cal X}\to{\cal X}^{\prime}$, we put
$\varphi_{0}=\varphi_{\Omega_{0}}$.

###  5.2. Admissible pairs

Let $\varphi:{\cal X}\to{\cal X}^{\prime}$, $s\mapsto s^{\prime}$ be an
algebraic isomorphism, where ${\cal X}^{\prime}=(\Omega^{\prime},S^{\prime})$.
In view of formula (4), ${\cal X}^{\prime}$ satisfies the
$e^{\prime}_{1}/e^{\prime}_{0}$-condition, where
$e^{\prime}_{0}=\varphi(e_{0})$ and $e^{\prime}_{1}=\varphi(e_{1})$. As above,
we define the sets $\Omega^{\prime}_{0}$, $\Omega^{\prime}_{1}$, and
$\Delta^{\prime}_{0}$ for all $\Delta^{\prime}\in\Omega^{\prime}_{1}$. In what
follows, we are interested in finding the set $\operatorname{Iso}({\cal
X},{\cal X}^{\prime},\varphi)$; for $\varphi=\operatorname{id}$, this was done
in [6].

Suppose we are given a bijection $f_{0}:\Omega_{0}\to\Omega^{\prime}_{0}$
taking $(e_{1})_{\Omega_{0}}$ to $(e^{\prime}_{1})_{\Omega^{\prime}_{0}}$, and
bijections $f_{\Delta}:\Delta\to\Delta^{\prime}$ for each
$\Delta\in\Omega_{1}$, where $\Delta^{\prime}$ is a uniquely determined class
of $e^{\prime}_{1}$, for which $(\Delta_{0})^{f_{0}}=\Delta^{\prime}_{0}$. The
pair $P=(\\{f_{\Delta}\\}_{\Delta\in\Omega_{1}},f_{0})$ is said to be
_$e_{1}/e_{0}$ -admissible_ if

(23) $(f_{\Delta})^{\Delta_{0}}=(f_{0})^{\Delta_{0}}$

for all $\Delta\in\Omega_{1}$. In this case there exists a uniquely determined
bijection $f:\Omega\to\Omega^{\prime}$ for which $f^{\Omega_{0}}=f_{0}$ and
$f^{\Delta}=f_{\Delta}$ for all $\Delta\in\Omega_{1}$. We say that $f$ is
induced by the pair $P$.

######  Theorem 5.2.

Let ${\cal X}$ be a scheme satisfying the $e_{1}/e_{0}$-condition, ${\cal
X}^{\prime}$ a scheme on $\Omega^{\prime}$, and $\varphi:{\cal X}\to{\cal
X}^{\prime}$ an algebraic isomorphism. Then $f\in\operatorname{Iso}({\cal
X},{\cal X}^{\prime},\varphi)$ if and only if $f$ is induced by an
$e_{1}/e_{0}$-admissible pair $(\\{f_{\Delta}\\},f_{0})$ such that

(24) $f_{0}\in\operatorname{Iso}({\cal X}_{0},{\cal
X}^{\prime}_{0},\varphi_{0})\quad\text{and}\quad
f_{\Delta}\in\operatorname{Iso}({\cal X}_{\Delta},{\cal
X}^{\prime}_{\Delta^{\prime}},\varphi_{\Delta,\Delta^{\prime}})\ \,\text{for
all}\ \Delta\in\Omega_{1}.$

###### Proof.

The “only if” part is clear, because every $f\in\operatorname{Iso}({\cal
X},{\cal X}^{\prime},\varphi)$ is obviously induced by the pair
$(\\{f^{\Delta}\\},f^{\Omega_{0}})$ which satisfies the conditions (24).
Conversely, suppose that $f$ is induced by an $e_{1}/e_{0}$-admissible pair
$(\\{f_{\Delta}\\},f_{0})$ satisfying conditions (24). We need to verify that
$s^{f}=\varphi(s)$ for all $s\in S$.

Let $s\subseteq e_{1}$. Then $s$ is equal to the union of $s_{\Delta}$,
$\Delta\in\Omega_{1}$. By the second part of (24), this implies that

$s^{f}=\bigcup_{\Delta\in\Omega_{1}}(s_{\Delta})^{f_{\Delta}}=\bigcup_{\Delta\in\Omega_{1}}\varphi_{\Delta,\Delta^{\prime}}(s_{\Delta})=\bigcup_{\Delta^{\prime}\in\Omega^{\prime}_{1}}\varphi(s)_{\Delta^{\prime}}=\varphi(s).$

Now, we may assume that $s\cap e_{1}=\varnothing$. Then
$e_{0}\subseteq\operatorname{Rad}(s)$, because ${\cal X}$ satisfies the
$e_{1}/e_{0}$-condition. It follows that $s$ is equal to the union of all
$\Gamma\times\Lambda$ for which $(\Gamma,\Lambda)$ lies in
$s_{0}=s_{\Omega/e_{0}}$. Because $f^{\Omega/e_{0}}=f_{0}$, we obtain

$s^{f}=\bigl{(}\bigcup_{(\Gamma,\Lambda)\in
s_{0}}\Gamma\times\Lambda\bigr{)}^{f}=\bigcup_{(\Gamma^{f},\Lambda^{f})\in
s_{0}^{f}}\Gamma^{f}\times\Lambda^{f}=\bigcup_{(\Gamma^{\prime},\Lambda^{\prime})\in
s^{\prime}_{0}}\Gamma^{\prime}\times\Lambda^{\prime},$

where $s^{\prime}_{0}$, $\Gamma^{\prime}$, and $\Lambda^{\prime}$ are the
$f_{0}$-images of $s_{0}$, $\Gamma$, and $\Lambda$, respectively. As was noted
above, ${\cal X}^{\prime}$ satisfies the
$e^{\prime}_{1}/e^{\prime}_{0}$-condition with
$e^{\prime}_{0}=\varphi(e_{0})$, and $e^{\prime}_{1}=\varphi(e_{1})$. Since
also $f_{0}$ induces $\varphi_{0}$, the relation $\varphi(s)$ equals the union
of all $\Gamma^{\prime}\times\Lambda^{\prime}$ with
$(\Gamma^{\prime},\Lambda^{\prime})\in s^{\prime}_{0}$. Thus,

$s^{f}=\bigcup_{(\Gamma^{\prime},\Lambda^{\prime})\in
s_{0}^{\prime}}\Gamma^{\prime}\times\Lambda^{\prime}=\varphi(s),$

as required.∎

###  5.3. General sufficient condition

A quite natural sufficient condition for the existence of admissible
$e_{1}/e_{0}$-pair satisfying (24) could be given by the equality

$\operatorname{Iso}({\cal X}_{0},{\cal
X}^{\prime}_{0},\varphi_{0})^{\Delta_{0}}=\operatorname{Iso}({\cal
X}_{\Delta},{\cal
X}^{\prime}_{\Delta^{\prime}},\varphi_{\Delta,\Delta^{\prime}})^{\Delta_{0}}$

for all $\Delta\in\Omega_{1}$ (cf., (23)). In this subsection, we weaken this
equality by considering smaller sets of isomorphisms, while assuming that the
algebraic isomorphism $\varphi$ has a one-point extension.

######  Lemma 5.3.

Let ${\cal X}$ be a scheme on $\Omega$, satisfying the
$e_{1}/e_{0}$-condition, ${\cal X}^{\prime}$ a scheme on $\Omega^{\prime}$,
and $\varphi:{\cal X}\to{\cal X}^{\prime}$ an algebraic isomorphism. Assume
that for all $\alpha\in\Omega$, $\alpha^{\prime}\in\Omega^{\prime}$,

(25) $\operatorname{Iso}_{\alpha_{0},\alpha^{\prime}_{0}}({\cal X}_{0},{\cal
X}^{\prime}_{0},\varphi_{0})^{\Delta_{0}}=\operatorname{Iso}_{\alpha,\alpha^{\prime}}({\cal
X}_{1},{\cal X}^{\prime}_{1},\varphi_{1})^{\Delta_{0}},$

where $\alpha_{0}=\alpha e_{0}$,
$\alpha^{\prime}_{0}=\alpha^{\prime}e^{\prime}_{0}$, and ${\cal X}_{1}={\cal
X}_{\Delta}$ with $\Delta\in\Omega_{1}$ containing $\alpha$, ${\cal
X}^{\prime}_{1}={\cal X}^{\prime}_{\Delta^{\prime}}$ with
$\Delta^{\prime}\in\Omega^{\prime}_{1}$ containing $\alpha^{\prime}$, and
$\varphi_{1}=\varphi_{\Delta,\Delta^{\prime}}$. Then for all $\alpha\in\Omega$
and $\alpha^{\prime}\in\Omega^{\prime}$,

  1. (i)

$\operatorname{Iso}_{\alpha,\alpha^{\prime}}({\cal X},{\cal
X}^{\prime},\varphi)^{\Omega_{0}}=\operatorname{Iso}_{\alpha_{0},\alpha^{\prime}_{0}}({\cal
X}_{0},{\cal X}^{\prime}_{0},\varphi_{0})$,

  2. (ii)

$\operatorname{Iso}_{\alpha,\alpha^{\prime}}({\cal X},{\cal
X}^{\prime},\varphi)^{\Delta}=\operatorname{Iso}_{\alpha,\alpha^{\prime}}({\cal
X}_{1},{\cal X}^{\prime}_{1},\varphi_{1})$.

###### Proof.

In both cases, it suffices to verify only the inclusion $\supseteq$ under the
assumption that the set on the right-hand side is nonempty. In the case (i),
we take arbitrary
$f_{0}\in\operatorname{Iso}_{\alpha_{0},\alpha^{\prime}_{0}}({\cal
X}_{0},{\cal X}^{\prime}_{0},\varphi_{0})$. For every $\Delta\in\Omega_{1}$,
we will define a certain bijection $f_{\Delta}:\Delta\to\Delta^{\prime}$,
where $\Delta^{\prime}$ is a unique class of $e^{\prime}_{1}$, for which
$(\Delta_{0})^{f_{0}}=\Delta^{\prime}_{0}$. First, assume that
$\alpha\in\Delta$. Then $\alpha^{\prime}\in\Delta^{\prime}$ and

$(f_{0})^{\Delta_{0}}\in\operatorname{Iso}_{\alpha_{0},\alpha^{\prime}_{0}}({\cal
X}_{0},{\cal X}^{\prime}_{0},\varphi_{0})^{\Delta_{0}}.$

In view of (25), one can find an isomorphism
$f_{\Delta}\in\operatorname{Iso}_{\alpha,\alpha^{\prime}}({\cal X}_{1},{\cal
X}^{\prime}_{1},\varphi_{1})$ for which
$(f_{\Delta})^{\Delta_{0}}=(f_{0})^{\Delta_{0}}$; in particular,
$\alpha^{f_{\Delta}}=\alpha^{\prime}$. Now if $\alpha\not\in\Delta$, then we
define $f_{\Delta}$ as above, but instead of $\alpha$ and $\alpha^{\prime}$ we
take arbitrary points $\delta\in\Delta$ and
$\delta^{\prime}\in(\delta_{0})^{f_{0}}$, respectively.

The constructed family $\\{f_{\Delta}:\ \Delta\in\Omega_{1}\\}$ together with
the isomorphism $f_{0}$ forms an $e_{1}/e_{0}$-admissible pair. Let
$f:\Omega\to\Omega^{\prime}$ be the bijection induced by this pair. By
definition, $f$ satisfies conditions (24) for all $\Delta$. Hence,
$f\in\operatorname{Iso}({\cal X},{\cal X}^{\prime},\varphi)$ by Theorem 5.2.
Since also $\alpha^{f}=\alpha^{\prime}$ and $f^{\Omega_{0}}=f_{0}$, we are
done.

In the case (ii), let $f_{1}\in\operatorname{Iso}_{\alpha,\alpha}({\cal
X}_{1},{\cal X}^{\prime}_{1},\varphi_{1})$, where $\alpha\in\Delta$ and
$\alpha^{\prime}\in\Delta^{\prime}$. In view of (25), one can find

$f_{0}\in\operatorname{Iso}_{\alpha_{0},\alpha^{\prime}_{0}}({\cal
X}_{0},{\cal X}^{\prime}_{0},\varphi_{0})$

such that $(f_{1})^{\Delta_{0}}=f_{0}$. Let $\Gamma\in\Omega_{1}$ be the class
of $e_{1}$, other that $\Delta$. Denote by $\Gamma^{\prime}$ a unique class of
$e^{\prime}_{1}$, for which $(\Gamma_{0})^{f_{0}}=\Gamma^{\prime}_{0}$, and
take arbitrary $\gamma\in\Gamma$. Then
$(\gamma_{0})^{f_{0}}=\gamma^{\prime}_{0}$ for some
$\gamma^{\prime}_{0}\in\Gamma^{\prime}$. Using (25) again, we find
$f_{\Gamma}\in\operatorname{Iso}_{\gamma,\gamma^{\prime}}({\cal
X}_{\Gamma},{\cal
X}^{\prime}_{\Gamma^{\prime}},\varphi_{\Gamma,\Gamma^{\prime}})$ such that
$(f_{\Gamma})^{\Gamma_{0}}=(f_{0})^{\Gamma_{0}}$.

The constructed family $\\{f_{\Lambda}:\ \Lambda\in\Omega_{1}\\}$ together
with the isomorphism $f_{0}$ forms an $e_{1}/e_{0}$-admissible pair. Let
$f:\Omega\to\Omega^{\prime}$ is the bijection induced by this pair. By
definition, $f$ satisfies conditions (24). Hence,
$f\in\operatorname{Iso}({\cal X},{\cal X}^{\prime},\varphi)$ by Theorem 5.2.
Since also $\alpha^{\prime}=\alpha^{f_{1}}=\alpha^{f}$ and $f^{\Delta}=f_{1}$,
we are done.∎

######  Corollary 5.4.

In the hypothesis and notation of Lemma 5.3, the following statements are
equivalent for all $\alpha\in\Omega$ and $\alpha^{\prime}\in\Omega^{\prime}$:

  1. (1)

$\operatorname{Iso}_{\alpha,\alpha^{\prime}}({\cal X},{\cal
X}^{\prime},\varphi)\neq\varnothing$,

  2. (2)

$\operatorname{Iso}_{\alpha_{0},\alpha^{\prime}_{0}}({\cal X}_{0},{\cal
X}^{\prime}_{0},\varphi_{0})\neq\varnothing$,

  3. (3)

$\operatorname{Iso}_{\alpha,\alpha^{\prime}}({\cal X}_{1},{\cal
X}^{\prime}_{1},\varphi_{1})\neq\varnothing$.

######  Corollary 5.5.

In the hypothesis and notations of Lemma 5.3, assume that ${\cal X}={\cal
X}^{\prime}$ and $\varphi=\operatorname{id}$. Then ${\cal X}$ is schurian if
and only if ${\cal X}_{0}$ is schurian and ${\cal X}_{1}$ is schurian for some
$\alpha$.

###### Proof.

It suffices to prove the “if” part only. Assume that ${\cal X}_{0}$ is
schurian and ${\cal X}_{1}$ is schurian for some $\alpha\in\Omega$. Since
$\varphi=\operatorname{id}$, we have ${\cal X}^{\prime}_{0}={\cal X}_{0}$ (but
not necessarily ${\cal X}^{\prime}_{1}={\cal X}_{1}$, because, in general,
$\alpha\neq\alpha^{\prime}$). Let $\alpha^{\prime}\in\Omega$. By the schurity
of ${\cal X}_{0}$, there exists $f\in\operatorname{Aut}({\cal X}_{0})$ such
that $(\alpha_{0})^{f}=\alpha^{\prime}_{0}$, or, equivalently,

$\operatorname{Iso}_{\alpha_{0},\alpha^{\prime}_{0}}({\cal X}_{0},{\cal
X}_{0},\operatorname{id})\neq\varnothing.$

By Lemma 5.3(i), this yields
$\operatorname{Iso}_{\alpha,\alpha^{\prime}}({\cal X},{\cal
X},\operatorname{id})\neq\varnothing$. Since $\alpha^{\prime}$ is arbitrary,
this means that the group $\operatorname{Aut}({\cal
X})=\operatorname{Iso}({\cal X},{\cal X},\operatorname{id})$ is transitive.
Moreover, by statements (i) and (ii) of Lemma 5.3 for
$\alpha=\alpha^{\prime}$, we have, respectively,

$(\operatorname{Aut}({\cal X})_{\alpha})^{\Omega_{0}}=\operatorname{Aut}({\cal
X}_{0})_{\alpha_{0}}\quad\text{and}\quad(\operatorname{Aut}({\cal
X})_{\alpha})^{\Delta}=\operatorname{Aut}({\cal X}_{1})_{\alpha}.$

By the transitivity of $\operatorname{Aut}({\cal X})$ and the schurity of
${\cal X}_{0}$ and ${\cal X}_{1}$, this implies that ${\cal X}$ is schurian.∎

###  5.4. Concrete sufficient condition

The key point in our general sufficiency condition established in Lemma 5.3 is
equality (25). In general, checking this equality is not an easy task. The
lemma below gives a more or less simple criterion to be used in Section 6.

######  Lemma 5.6.

Let ${\cal X}$ be a sesquiclosed commutative scheme on $\Omega$, satisfying
the $e_{1}/e_{0}$-condition, ${\cal X}^{\prime}$ a scheme on
$\Omega^{\prime}$, and $\varphi:{\cal X}\to{\cal X}^{\prime}$ a sesquiclosed
algebraic isomorphism. In the notation of Lemma 5.3, assume that for
$\alpha\in\Omega$ and $\alpha^{\prime}\in\Omega^{\prime}$,

  1. (i)

${\cal X}_{0}$ and ${\cal X}_{1}$ are schurian, $\operatorname{Iso}({\cal
X}_{0},{\cal
X}^{\prime}_{0},\varphi_{0})\neq\varnothing\neq\operatorname{Iso}({\cal
X}_{1},{\cal X}^{\prime}_{1},\varphi_{1})$,

  2. (ii)

$(({\cal X}_{0})_{\alpha_{0}})_{\Delta_{0}}$ and $(({\cal
X}_{1})_{\alpha})_{\Delta_{0}}$ are partly regular.

Then equality (25) holds.

###### Proof.

Let $f_{0}\in\operatorname{Iso}({\cal X}_{0},{\cal
X}^{\prime}_{0},\varphi_{0})$. Because ${\cal X}_{0}$ is a schurian scheme, we
may assume that $(\alpha_{0})^{f_{0}}=\alpha^{\prime}_{0}$. Then the algebraic
isomorphism $\psi_{0}$ induced by $f_{0}$ is the
$(\alpha_{0},\alpha^{\prime}_{0})$-extension of the algebraic isomorphism
$\varphi_{0}$. It easily follows that

(26) $\operatorname{Iso}_{\alpha_{0},\alpha^{\prime}_{0}}({\cal X}_{0},{\cal
X}^{\prime}_{0},\varphi_{0})^{\Delta_{0}}=\operatorname{Iso}(({\cal
X}_{0})_{\alpha_{0}},({\cal
X}^{\prime}_{0})_{\alpha^{\prime}_{0}},\psi_{0})^{\Delta_{0}}.$

Next, by the first parts of conditions (i) and (ii), the scheme ${\cal X}_{0}$
and algebraic isomorphism $\varphi_{0}$ satisfy the hypothesis of Lemma 4.9
for ${\mathfrak{S}}=\Delta_{0}$,
${\mathfrak{S}}^{\prime}=\Delta^{\prime}_{0}$, and $\alpha=\alpha_{0}$.
Therefore,

(27) $\operatorname{Iso}(({\cal X}_{0})_{\alpha_{0}},({\cal
X}^{\prime}_{0})_{\alpha^{\prime}_{0}},\psi_{0})^{\Delta_{0}}=\operatorname{Iso}((({\cal
X}_{0})_{\alpha_{0}})_{\Delta_{0}},(({\cal
X}^{\prime}_{0})_{\alpha^{\prime}_{0}})_{\Delta^{\prime}_{0}},(\psi_{0})_{\Delta_{0},\Delta^{\prime}_{0}}).$

Furthermore, the scheme ${\cal X}$, sections ${\mathfrak{S}}=\Omega_{0}$,
${\mathfrak{S}}_{0}=\Delta_{0}$, and point $\alpha$ satisfy the hypothesis of
Lemma 4.8. Therefore,

(28) $(({\cal X}_{0})_{\alpha_{0}})_{\Delta_{0}}=(({\cal
X}_{\alpha})_{\Omega_{0}})_{\Delta_{0}}=({\cal X}_{\alpha})_{\Delta_{0}}.$

By Lemma 4.7, the scheme ${\cal X}^{\prime}$ is sesquiclosed. Furthermore, the
isomorphism $f_{0}$ induces an isomorphism from $(({\cal
X}_{0})_{\alpha_{0}})_{\Delta_{0}}$ to the coherent configuration $(({\cal
X}^{\prime}_{0})_{\alpha^{\prime}_{0}})_{\Delta^{\prime}_{0}}$, which is
therefore partly regular. Thus, the scheme ${\cal X}^{\prime}$, sections
${\mathfrak{S}}=\Omega^{\prime}_{0}$,
${\mathfrak{S}}_{0}=\Delta^{\prime}_{0}$, and point $\alpha^{\prime}$ satisfy
the hypothesis of Lemma 4.8, whence

(29) $(({\cal X}^{\prime}_{0})_{\alpha^{\prime}_{0}})_{\Delta_{0}}=(({\cal
X}^{\prime}_{\alpha^{\prime}})_{\Omega^{\prime}_{0}})_{\Delta^{\prime}_{0}}.=({\cal
X}^{\prime}_{\alpha^{\prime}})_{\Delta^{\prime}_{0}}.$

The $(\alpha,\alpha^{\prime})$-extension $\varphi_{\alpha,\alpha^{\prime}}$ of
the (sesquiclosed) algebraic isomorphism $\varphi$ takes $\alpha_{0}$ to
$\alpha^{\prime}_{0}$. Therefore, $\varphi_{\alpha,\alpha^{\prime}}$ extends
$\varphi_{0}$ and takes $\Delta_{0}$ to $\Delta^{\prime}_{0}$. It follows that
the algebraic isomorphism $\psi_{\Delta_{0},\Delta^{\prime}_{0}}$ defined as
the restriction of $\varphi_{\alpha,\alpha^{\prime}}$ to $(({\cal
X}_{0})_{\alpha_{0}})_{\Delta}$ coincides with
$(\psi_{0})_{\Delta_{0},\Delta^{\prime}_{0}}$. With taking equalities (28) and
(29) into account, we can continue formula (27) as follows:

$\operatorname{Iso}((({\cal X}_{0})_{\alpha_{0}})_{\Delta_{0}},(({\cal
X}^{\prime}_{0})_{\alpha^{\prime}_{0}})_{\Delta^{\prime}_{0}},(\psi_{0})_{\Delta_{0},\Delta^{\prime}_{0}})=\operatorname{Iso}(({\cal
X}_{\alpha})_{\Delta_{0}},({\cal
X}^{\prime}_{\alpha^{\prime}})_{\Delta^{\prime}_{0}},\psi_{\Delta_{0},\Delta^{\prime}_{0}}).$

This together with (26), yields

$\operatorname{Iso}_{\alpha_{0},\alpha^{\prime}_{0}}({\cal X}_{0},{\cal
X}^{\prime}_{0},\varphi_{0})^{\Delta_{0}}=\operatorname{Iso}(({\cal
X}_{\alpha})_{\Delta_{0}},({\cal
X}^{\prime}_{\alpha^{\prime}})_{\Delta^{\prime}_{0}},\psi_{\Delta_{0},\Delta^{\prime}_{0}}).$

Arguing in a similar way with ${\cal X}_{0}$ and $\varphi_{0}$ replaced by
${\cal X}_{1}$ and $\varphi_{1}$, we obtain

$\operatorname{Iso}_{\alpha,\alpha^{\prime}}({\cal X}_{1},{\cal
X}^{\prime}_{1},\varphi_{1})^{\Delta_{0}}=\operatorname{Iso}(({\cal
X}_{\alpha})_{\Delta_{0}},({\cal
X}^{\prime}_{\alpha^{\prime}})_{\Delta^{\prime}_{0}},\psi_{\Delta_{0},\Delta^{\prime}_{0}}).$

Comparing the expressions on the right-hand sides of the last two equalities,
we get (25).∎

##  6\. Circulant sesquiseparable schemes

###  6.1. Circulant schemes

In this subsection, we follow [2, Sections 2.4 and 4.4]. Let $G$ be a cyclic
group. A coherent configuration ${\cal X}$ on the elements of $G$ is said to
be circulant if for every $g\in G$, the permutation

$\rho_{g}:x\mapsto xg,\ x\in G,$

is an automorphism of ${\cal X}$; in particular, ${\cal X}$ is a commutative
scheme. There is a one-to-one correspondence between circulant schemes and the
Schur rings over cyclic groups (see, e.g., [5]). The reader should not be
embarrassed that most of the results cited in the present paper were
formulated and proved in the language of Schur rings. In the rest of this
subsection, we will change our terminology slightly to match that used for
circulant schemes (and Schur rings). In the sequel, ${\cal X}$ is a circulant
scheme on $G$, $S=S({\cal X})$, $E=E({\cal X})$, and $\alpha=1_{G}$.

Every group $H\leq G$ defines an equivalence relation $e=e(H)$ on $G$, the
classes of which are the cosets of $H$ in $G$. In particular,
$e(\alpha)=\operatorname{Diag}(G\times G)$ and $e(G)=G\times G$. Note that
$H=\alpha e$ and $H\leq H^{\prime}$ if and only if $e(H)\subseteq
e(H^{\prime})$.

We say that $H$ is an ${\cal X}$-group if $e(H)\in E$. The mapping $H\mapsto
e(H)$ defines a one-to-one correspondence between the ${\cal X}$-groups and
parabolics of ${\cal X}$. The parabolics $\langle{s}\rangle$ and
$\operatorname{Rad}(s)$, where $s\in S$, correspond to $e(H)$ with
$H=\langle{\alpha s}\rangle$ and $H=\\{h\in G:\ (\alpha s)h=\alpha s\\}$,
respectively. Note that the parabolic $\operatorname{Rad}(s)=e(H)$, and hence
the group $H$, does not depend on the relation $s=r(\alpha,g)$, where $g$ is a
generator of $G$. This group is called the radical of ${\cal X}$ and is
denoted by $\operatorname{Rad}({\cal X})$.

In the context of circulant schemes, we are interested in those sections
${\mathfrak{S}}=\Delta/e$ for which $\alpha\in\Delta$. In this case,
$\Delta=U$ and $e=e(L)$ for some ${\cal X}$-groups $U$ and $L$ such that
$L\leq U$; in particular, ${\mathfrak{S}}=U/L$. The set of all such sections
is denoted by ${\mathfrak{S}}_{0}({\cal X})$. It is important to note that
every ${\mathfrak{S}}\in{\mathfrak{S}}_{0}({\cal X})$ is treated as a cyclic
group and the scheme ${\cal X}_{\mathfrak{S}}$ is treated as a circulant
scheme on ${\mathfrak{S}}$. We say that a section ${\mathfrak{S}}$ is
_trivial_ (respectively, _primitive_) if the scheme ${\cal X}_{\mathfrak{S}}$
is primitive (respectively, contains no proper ${\cal
X}_{\mathfrak{S}}$-groups). It is known that every primitive section of
composite order is trivial.

###  6.2. Normal circulant schemes

The scheme ${\cal X}$ is said to be normal if the group $\langle{\rho_{g}:\
g\in G}\rangle$ is normal in $\operatorname{Aut}({\cal X})$, or equivalently,
$\operatorname{Aut}({\cal X})_{\alpha}\leq\operatorname{Aut}(G)$. This
condition is always satisfied when $G$ is of prime order and ${\cal X}$ is not
trivial.

######  Lemma 6.1.

[5, Theorem 6.1 and Corollary 6.2] Every normal circulant scheme ${\cal X}$ is
schurian. Moreover, any one-point extension of ${\cal X}$ is partly regular.

There are normal circulant schemes that are not separable, see, e.g., [2,
Section 4.5]. However, from Lemmas 6.1 and 2.2, it follows that every normal
circulant scheme is schurian and any one-point extension of it is separable.
By Lemma 4.4, this proves the following statement.

######  Corollary 6.2.

Every normal circulant scheme is sesquiseparable.

The following auxiliary statement is crucial for the proof of Theorem 6.4
below, because it enables us to verify condition (ii) in Lemma 5.6.

######  Lemma 6.3.

Let ${\cal X}$ be a normal circulant scheme and $\alpha=1_{G}$. Then the
coherent configuration $({\cal X}_{\alpha})_{\mathfrak{S}}$ is partly regular
for every ${\mathfrak{S}}\in{\mathfrak{S}}_{0}({\cal X})$.

###### Proof.

Let ${\mathfrak{S}}=U/L$, where $U$ and $L$ are ${\cal X}$-subgroups, and let
$u$ be a generator of $U$. It suffices to verify that $\bar{u}=uL$ is a
regular point of the coherent configuration $({\cal
X}_{\alpha})_{\mathfrak{S}}$. Assume on the contrary that there exist
$x,x^{\prime}\in U$ such that

(30)
$\bar{x}\neq\bar{x}^{\prime}\quad\text{and}\quad\bar{r}(\bar{x},\bar{u})=\bar{r}(\bar{x}^{\prime},\bar{u}),$

where $\bar{x}=xL$, $\bar{x}^{\prime}=x^{\prime}L$, and for all
$\overline{y},\overline{z}\in{\mathfrak{S}}$ we denote by
$\bar{r}(\overline{y},\overline{z})$ the basis relation of the coherent
configuration $({\cal X}_{\alpha})_{\mathfrak{S}}$, containing the pair
$(\overline{y},\overline{z})$. By the second equality in (30), there is
$u^{\prime}\in\bar{u}$ such that

$r(x,u)=r(x^{\prime},u^{\prime}).$

The normality of ${\cal X}$ implies that every element of
$\operatorname{Aut}({\cal X}_{\alpha})=\operatorname{Aut}({\cal X})_{\alpha}$
is induced by raising to a power coprime to the order $n$ of the underlying
cyclic group $G$. Furthermore, the coherent configuration ${\cal X}_{\alpha}$
is partly regular by Lemma 6.1 and hence is schurian by Lemma 2.2. Thus there
is an integer $m$ coprime to $n$ and such that

$x^{m}=x^{\prime}\quad\text{and}\quad u^{m}=u^{\prime}.$

In particular, $\bar{x}^{m}=\bar{x}^{\prime}$ and
$\bar{u}^{m}=\bar{u}^{\prime}=\bar{u}$. On the other hand, since $u$ is a
generator of $U\geq L$, there is an integer $a$ for which $x=u^{a}$.
Furthermore, $(uL)^{m}=\bar{u}^{m}=\bar{u}=uL$ and hence $u^{m}=yu$ for some
$y\in L$. Thus for every $\ell\in L$, we have

$(x\ell)^{m}=(u^{a}\ell)^{m}=(u^{a})^{m}\ell^{m}=(u^{m})^{a}\ell^{m}=(yu)^{a}\ell^{m}=u^{a}(y^{a}\ell^{m})=x\ell^{\prime},$

where the element $\ell^{\prime}=y^{a}\ell^{m}$ belongs to $L$. Consequently,
$\bar{x}^{m}=\bar{x}$, implying $\bar{x}^{\prime}=\bar{x}^{m}=\bar{x}$ in
contrast to the first inequality in (30).∎

Let ${\cal X}$ be an arbitrary circulant scheme. A section
${\mathfrak{S}}\in{\mathfrak{S}}_{0}({\cal X})$ is said to be _normal_ if the
(circulant) scheme ${\cal X}_{\mathfrak{S}}$ is normal, and _subnormal_ if
there exists a normal section
${\mathfrak{S}}^{\prime}\in{\mathfrak{S}}_{0}({\cal X})$ such that
${\mathfrak{S}}\leq{\mathfrak{S}}^{\prime}$. Note that every normal section is
subnormal and any primitive section of composite order greater than $4$ is not
subnormal.

###  6.3. The ${\mathfrak{S}}$-wreath product of circulant schemes

Let ${\cal X}$ be a circulant scheme and
${\mathfrak{S}}\in{\mathfrak{S}}_{0}({\cal X})$. Assume that ${\cal X}$
satisfies the $e(U)/e(L)$-condition, where $U$ and $L$ are ${\cal X}$-groups
such that ${\mathfrak{S}}=U/L$. In this case, we say that ${\cal X}$ is the
${\mathfrak{S}}$-wreath product of schemes ${\cal X}_{1}={\cal X}_{U}$ and
${\cal X}_{0}={\cal X}_{G/L}$. The ${\mathfrak{S}}$-wreath product is
nontrivial if $1<L\leq U<G$, i.e., if ${\cal X}$ satisfies the
$e(U)/e(L)$-condition nontrivially. When $U=L$, we say that ${\cal X}$ is a
wreath product.

The main result of this subsection is to establish a simple criterion for the
${\mathfrak{S}}$-wreath product to be schurian and sesquiseparable.

######  Theorem 6.4.

Let ${\cal X}$ be a circulant sesquiclosed scheme on $G$. Assume that ${\cal
X}$ is the ${\mathfrak{S}}$-wreath product of (circulant) schemes ${\cal
X}_{0}$ and ${\cal X}_{1}$ for some ${\mathfrak{S}}\in{\mathfrak{S}}_{0}$, and
also

  1. (1)

the section ${\mathfrak{S}}$ is subnormal in both ${\cal X}_{0}$ and ${\cal
X}_{1}$,

  2. (2)

the schemes ${\cal X}_{0}$ and ${\cal X}_{1}$ are schurian and
sesquiseparable.

Then ${\cal X}$ is schurian and sesquiseparable.

###### Proof.

By condition (1), the section ${\mathfrak{S}}$ is contained in certain
sections ${\mathfrak{S}}_{0}\in{\mathfrak{S}}({\cal X}_{0})$ and
${\mathfrak{S}}_{1}\in{\mathfrak{S}}({\cal X}_{1})$ such that the schemes

${\cal X}_{{\mathfrak{S}}_{0}}=({\cal
X}_{0})_{{\mathfrak{S}}_{0}}\quad\text{and}\quad{\cal
X}_{{\mathfrak{S}}_{1}}=({\cal X}_{1})_{{\mathfrak{S}}_{1}}$

are normal circulant. By Lemma 6.1, the one-point extensions $({\cal
X}_{{\mathfrak{S}}_{0}})_{\alpha}$ and $({\cal
X}_{{\mathfrak{S}}_{1}})_{\beta}$ are partly regular, where
$\alpha=1_{{\mathfrak{S}}_{0}}$ and $\beta=1_{{\mathfrak{S}}_{1}}$ treated as
points of the schemes ${\cal X}_{{\mathfrak{S}}_{0}}$ and ${\cal
X}_{{\mathfrak{S}}_{1}}$, respectively. By Lemma 6.3, the coherent
configurations

$(({\cal X}_{{\mathfrak{S}}_{0}})_{\alpha})_{\mathfrak{S}}\leq(({\cal
X}_{0})_{\alpha})_{\mathfrak{S}}\quad\text{and}\quad(({\cal
X}_{{\mathfrak{S}}_{1}})_{\beta})_{\mathfrak{S}}\leq(({\cal
X}_{1})_{\beta})_{\mathfrak{S}}$

are partly regular. It follows that so are the coherent configurations
$(({\cal X}_{0})_{\alpha})_{\mathfrak{S}}$ and $(({\cal
X}_{{\mathfrak{S}}_{1}})_{\beta})_{\mathfrak{S}}$. Consequently, condition
(ii) of Lemma 5.6 is satisfied for $e_{0}=e(L)$, $e_{1}=e(U)$, and
$\alpha=1_{G}$. Since $\operatorname{Aut}({\cal X})$ is transitive, this
condition is true for all points of ${\cal X}$.

The schemes ${\cal X}_{0}$ and ${\cal X}_{1}$ are schurian by the first part
of condition (2). Thus condition (i) of Lemma 5.6 is satisfied for
$\varphi=\operatorname{id}$ (the condition $\operatorname{Iso}({\cal
X}_{1},{\cal X}^{\prime}_{1},\varphi_{1})\neq\varnothing$ is true, because the
group $\operatorname{Aut}({\cal X})$ is transitive). By that lemma, equality
(25) holds for all $\alpha$ and $\alpha^{\prime}$, and hence the scheme ${\cal
X}$ satisfies the hypothesis of Corollary 5.5. Thus, ${\cal X}$ is schurian.

Let $\varphi:{\cal X}\to{\cal X}^{\prime}$ be a sesquiclosed algebraic
isomorphism. Then the algebraic isomorphisms $\varphi_{0}$ and $\varphi_{1}$
are also sesquiclosed by Lemma 4.3. By the second part of condition (2), this
implies that $\operatorname{Iso}({\cal X}_{0},{\cal
X}^{\prime}_{0},\varphi_{0})\neq\varnothing$, and $\operatorname{Iso}({\cal
X}_{1},{\cal X}^{\prime}_{1},\varphi_{1})\neq\varnothing$ . Thus condition (i)
of Lemma 5.6 is satisfied. By that lemma, equality (25) holds for all
$\alpha\in\Omega$ and $\alpha^{\prime}\in\Omega$. Thus,
$\operatorname{Iso}({\cal X},{\cal X}^{\prime},\varphi)\neq\varnothing$ by
Corollary 5.4, and hence ${\cal X}$ is sesquiseparable.∎

The conditions of Theorem 6.4 are always true when the circulant schemes
${\cal X}_{0}$ and ${\cal X}_{1}$ are normal. Thus this theorem implies the
following statement.

######  Corollary 6.5.

Let ${\cal X}$ be a circulant sesquiclosed scheme on $G$. Assume that ${\cal
X}$ is the ${\mathfrak{S}}$-wreath product for some
${\mathfrak{S}}\in{\mathfrak{S}}_{0}({\cal X})$ such that the both operands
are normal. Then ${\cal X}$ is schurian and sesquiseparable.

###  6.4. Circulant schemes of prime power degree

In this subsection, ${\cal X}$ is a circulant scheme on a cyclic $p$-group
$G$. The structure of ${\cal X}$ has been completely described in [17] and
[10] for $p\geq 3$ and $p=2$, respectively. In particular, ${\cal X}$ is
schurian. Another important consequence of the description is the radical
monotonicity for $p\geq 3$, namely,

(31)
$\langle{s}\rangle\leq\langle{t}\rangle\quad\Rightarrow\quad\operatorname{Rad}(s)\leq\operatorname{Rad}(t).$

for all $s,t\in S$. Using this fact, we show in the lemma below that the
wreath product can be lifted from any section of ${\cal X}$.

######  Lemma 6.6.

Let $p\geq 3$ and ${\mathfrak{S}}\in{\mathfrak{S}}_{0}({\cal X})$. If ${\cal
X}_{\mathfrak{S}}$ is a nontrivial wreath product, then so is ${\cal X}$.

###### Proof.

Let ${\mathfrak{S}}=U/L$ and ${\cal X}_{\mathfrak{S}}$ a nontrivial wreath
product. Then there is an ${\cal X}$-subgroup $H$ such that $L<H<U$ and for
every $s\in S$,

$s\subseteq e(U)\setminus e(H)\quad\Rightarrow\quad
e(H/L)\subseteq\operatorname{Rad}(s_{\mathfrak{S}}),$

Without loss of generality, we may assume that $H$ is the only ${\cal
X}$-subgroup strictly between $L$ and $U$ (here we use the fact that $G$ is a
cyclic $p$-group and hence the ${\cal X}$-groups are linearly ordered with
respect to inclusion). It suffices to verify that

(32) $s\subseteq e(U)\setminus
e(H)\quad\Rightarrow\quad\operatorname{Rad}(s)\geq e(H).$

Indeed, then by formula (31), we have $\operatorname{Rad}(s)\geq e(H)$ for all
$s\in S$ not contained in $e_{H}$. But this means that ${\cal X}$ satisfies
the $e(H)/e(H)$-condition, i.e., ${\cal X}$ is a nontrivial wreath product.

Suppose on the contrary that (32) is not true for some $s$. Then the ${\cal
X}$-subgroup $L^{\prime}$, for which $\operatorname{Rad}(s)=e(L^{\prime})$, is
strictly contained in $H$. By the assumption on $H$, this implies that
$L^{\prime}<L$, and hence ${\mathfrak{S}}$ is a subsection of
${\mathfrak{S}}^{\prime}=U/L^{\prime}$. Note that

$\operatorname{Rad}({\cal X}_{\mathfrak{S}})\neq
1\quad\text{and}\quad\operatorname{Rad}({\cal
X}_{{\mathfrak{S}}^{\prime}})=1.$

However, this contradicts the fact (see [3, Corollary 7.4]) that if a
circulant scheme (in our case ${\cal X}_{{\mathfrak{S}}^{\prime}}$) of odd
prime power degree is of trivial radical, then every its section (in our case
${\mathfrak{S}}$) is also of trivial radical. ∎

In the following lemma, we collect some known properties of circulant schemes
of prime power degree, that will be used in the proof of Theorem 6.8. Below,
we say that a circulant scheme ${\cal X}$ is _dense_ if
${\mathfrak{S}}_{0}({\cal X})$ contains no trivial section of composite order.

######  Lemma 6.7.

Let ${\cal X}$ be a circulant scheme of prime power degree. Then

  1. (1)

if $\operatorname{Rad}({\cal X})=1$, then ${\cal X}$ is trivial or normal,

  2. (2)

if $\operatorname{Rad}({\cal X})\neq 1$ and ${\cal X}$ is dense, then ${\cal
X}$ is a nontrivial ${\mathfrak{S}}$-wreath product, and also
$\operatorname{Rad}({\cal X}_{\mathfrak{S}})=1$ or $|{\mathfrak{S}}|=4$,

  3. (3)

if ${\mathfrak{S}}_{0}({\cal X})$ contains a proper primitive non-subnormal
section, then ${\cal X}$ is a nontrivial wreath product.

###### Proof.

Statements (1) and (3) are consequences of [5, Corollary 6.4], and the
statement cited in [8, p.29] (and proved in [7, Theorem 4.6]), specified for
schemes of prime power degree. Statement (2) is exactly [8, Lemma 6.1]. ∎

Now we are ready to prove the main result of this subsection.

######  Theorem 6.8.

Every circulant scheme of prime power degree is sesquiseparable.

###### Proof.

Let ${\cal X}$ be a circulant scheme of degree $p^{n}$, where $p$ is a prime
and $n\geq 1$. Assume first that ${\cal X}$ is trivial or normal. In the
former case, ${\cal X}$ is separable and hence sesquiseparable. In the latter
case, ${\cal X}$ is sesquiseparable by Corollary 6.2.

Claim. Let ${\cal X}$ be neither trivial nor normal. Then ${\cal X}$ is a
nontrivial ${\mathfrak{S}}$-wreath product with ${\mathfrak{S}}$ subnormal in
both operands.

###### Proof.

By Lemma 6.7(3), we may assume that ${\mathfrak{S}}_{0}({\cal X})$ contains no
proper primitive non-subnormal section (otherwise we have a section
${\mathfrak{S}}$ for which $|{\mathfrak{S}}|=1$). Then
${\mathfrak{S}}_{0}({\cal X})$ contains no trivial section of composite order,
i.e., ${\cal X}$ is dense. By statements (1) and (2) of Lemma 6.7, the scheme
${\cal X}$ is a nontrivial ${\mathfrak{S}}$-wreath product, and also
$\operatorname{Rad}({\cal X}_{\mathfrak{S}})=1$ or $|{\mathfrak{S}}|=4$. In
the last case, ${\mathfrak{S}}$ is normal (because all circulant schemes of
degree at most $4$ are normal) and hence is subnormal in both operands.

Let $\operatorname{Rad}({\cal X}_{\mathfrak{S}})=1$. Then by Lemma 6.7(1), the
section ${\mathfrak{S}}$ is either normal or trivial. In the first case, we
are done as above. In the second case, $|{\mathfrak{S}}|=p\geq 5$ (otherwise
${\mathfrak{S}}$ is normal). It remains to verify that ${\mathfrak{S}}$ is
subnormal in both operands. But if this is not true, then one of the operands
is a nontrivial wreath product by Lemma 6.7(3). Then so is ${\cal X}$ by Lemma
6.6, and we are done as above. The claim is proved. ∎

To complete the proof of the theorem, we may assume by claim that ${\cal X}$
is a nontrivial ${\mathfrak{S}}$-wreath product of circulant schemes ${\cal
X}_{0}$ and ${\cal X}_{1}$ such that the section ${\mathfrak{S}}$ is subnormal
both in ${\cal X}_{0}$ and ${\cal X}_{1}$. Note that ${\cal X}_{0}$ and ${\cal
X}_{1}$ are circulant schemes of prime power degrees, which are less than
$p^{n}$. By induction, this implies that they are sesquiseparable. Because
they are also schurian, the scheme ${\cal X}$ is sesquiseparable by Theorem
6.4.∎

###  6.5. Proof of Theorem 1.1

Let ${\cal G}$ be a circulant graph of prime power order; in particular,
${\cal G}$ is vertex-transitive and $\operatorname{WL}({\cal G})$ is a
schurian circulant scheme. Let ${\cal G}^{\prime}$ be a graph
$\operatorname{WL}_{3}$-equivalent to ${\cal G}$. By Lemma 4.2, there is a
sesquiclosed algebraic isomorphism $\varphi:\operatorname{WL}({\cal
G})\to\operatorname{WL}({\cal G}^{\prime})$ such that $\varphi(D)=D^{\prime}$,
where $D$ and $D^{\prime}$ are the arc sets of ${\cal G}$ and ${\cal
G}^{\prime}$, respectively. On the other hand, the scheme
$\operatorname{WL}({\cal G})$ is sesquiseparable by Theorem 6.8. Thus the
algebraic isomorphism $\varphi$ is induced by an isomorphism $f$. It follows
that $D^{f}=\varphi(D)=D^{\prime}$. Hence, $f\in\operatorname{Iso}({\cal
G},{\cal G}^{\prime})$, i.e., the graphs ${\cal G}$ and ${\cal G}^{\prime}$
are isomorphic. Consequently,
$\dim_{\scriptscriptstyle\operatorname{WL}}({\cal G})\leq 3$.

## References

  * [1] L. Babai, _Group, Graphs, Algorithms: the Graph Isomorphism Problem_ , Proceedings of the International Congress of Mathematicians (ICM 2018), vol. 3, WORLD SCIENTIFIC, 2019, see also L. Babai, Graph Isomorphism in Quasipolynomial Time (2016), arXiv:1512.03547v2 [cs.DS]), pp. 3319–3336.
  * [2] 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.
  * [3] S. Evdokimov, I. Kovács, and I. Ponomarenko, _Characterization of cyclic Schur groups_ , St. Petersburg Math. J. 25 (2014), no. 5, 755–773.
  * [4] S. Evdokimov and I. Ponomarenko, _On a family of Schur rings over a finite cyclic group_ , St. Petersburg Math. J. 13 (2002), no. 3, 441–451.
  * [5] S. Evdokimov and I. Ponomarenko, _Characterization of cyclotomic schemes and normal schur rings over a cyclic group_ , St. Petersburg Math. J. 14 (2003), no. 2, 189–221.
  * [6] S. Evdokimov and I. Ponomarenko, _Recognizing and isomorphism testing circulant graphs in polynomial time_ , St. Petersburg Math. J. 15 (2004), no. 6, 813–835.
  * [7] S. Evdokimov and I. Ponomarenko, _Schurity of S-rings over a cyclic group and generalized wreath product of permutation groups_ , St. Petersburg Math. J. 24 (2013), no. 3, 431–460.
  * [8] S. Evdokimov and I. Ponomarenko, _On the separability problem for circulant S-rings_ , St. Petersburg Math. J. 28 (2017), no. 1, 21–35.
  * [9] 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.
  * [10] Y. Y. Gol’fand, M. H. Klin, and N. L. Naimark, _The structure of S-rings over ${Z}_{2^{m}}$_, Sixteenth All Union Algebraic Conference. Part 2, Leningrad, 1981, pp. 195–196.
  * [11] M. Grohe, _Descriptive complexity, canonisation, and definable graph structure theory_ , Cambridge University Press, 2017.
  * [12] H. Helfgott, J. Bajpai, and D. Dona, _Graph isomorphisms in quasi-polynomial time_ , 2017, arXiv:1710.04574, pp. 1–67.
  * [13] A. Herman, J. Bagherian, and H. Memarzadeh, _The generalized X-join of Cayley graphs_ , ArXiv e-prints, math.CO:4211718 (2022), 1–14.
  * [14] M. Muzychuk, _A solution of the isomorphism problem for circulant graphs_ , Proc. London Math. Soc. 88 (2004), 1–41.
  * [15] M. Muzychuk, _A wedge product of association schemes_ , European J. Combin. 30 (2009), no. 3, 705–715.
  * [16] O. Pikhurko and O. Verbitsky, _Logical complexity of graphs: a survey_ , Model theoretic methods in finite combinatorics, Contemp. Math., vol. 558, Amer. Math. Soc., Providence, RI, 2011, pp. 129–179.
  * [17] R. Pöschel, _Untersuchungen von S‐Ringen, insbesondere im Gruppenring von p‐Gruppen_ , Math. Nachr. 60 (1974), no. 1-6, 1–27.
  * [18] 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.