# On the Weisfeiler-Leman dimension of permutation graphs

,  Jin Guo  Hainan University, Haikou, China<EMAIL_ADDRESS>,  Alexander
L. Gavrilyuk  Shimane University, Matsue, Japan
<EMAIL_ADDRESS>and  Ilia Ponomarenko  Hainan University,
Haikou, China  Steklov Institute of Mathematics at St. Petersburg, Russia
<EMAIL_ADDRESS>
###### Abstract.

It is proved that the Weisfeiler-Leman dimension of the class of permutation
graphs is at most 18. Previously it was only known that this dimension is
finite (Grußien, 2017).

The research of Alexander Gavrilyuk is supported by JSPS KAKENHI Grant Number
22K03403. The research of Jin Guo is supported by the National Natural Science
Foundation of China (Grant No. 11961017).

##  1\. Introduction

The Weisfeiler-Leman (WL) algorithm, originally introduced in [27], is a graph
isomorphism test. It first colors the ordered pairs of vertices of the input
graphs and then iteratively refines the coloring. The procedure is
isomorphism-invariant, i.e., isomorphic graphs eventually receive the same
canonical coloring. The converse is not true in general. Stronger isomorphism-
invariant colorings can be obtained if one considers coloring the $d$-tuples
of vertices with $d>2$; the corresponding generalization, called the
$d$-dimensional Weisfeiler-Lehman algorithm (or the $d$-dim WL for short), was
introduced in the late 1970s (see [6, 4]) and played a crucial role in Babai’s
breakthrough quasipolynomial-time isomorphism test [3]. For $d=1$ and $d=2$,
the $d$-dim WL is in fact the naive refinement and ordinary WL, respectively.
The family of $d$-dim WL algorithms has striking connections with other areas
in theoretical computer science and algebraic combinatorics (see [10, 2, 20,
9]).

Given a graph $X$, there exists the smallest integer $d$ such that the $d$-dim
WL correctly identifies $X$. Following Grohe [17], this $d$ is called the WL
dimension $\dim_{\mathsf{WL}}(X)$ of the graph $X$. The seminal paper of Cai,
Fürer and Immerman [6] shows that the WL dimension in the class of all graphs
cannot be bounded from above by a constant. However, graphs belonging to
various interesting classes often have a bounded dimension.

More precisely, the WL dimension of a class $\mathcal{K}$ of graphs is defined
to be the maximum of $\dim_{\mathsf{WL}}(X)$ over all $X\in\mathcal{K}$ if it
exists, or $\infty$ otherwise. If $\dim_{\mathsf{WL}}(X)\leq m$, then the
graph isomorphism problem restricted to $\mathcal{K}$ is solved by the $m$-dim
WL, which, for fixed $m$, runs in polynomial time [22]. This yields a uniform
purely combinatorial isomorphism test for all graph classes of bounded WL
dimension.

By a celebrated result of Grohe [16], all graph classes with an excluded minor
have a bounded WL dimension. In many recent studies, the explicit upper bounds
on the WL dimension have been obtained for various graph classes: the interval
graphs [11], planar graphs [23], graphs of given Euler genus [18], or rank
width [19], to name a few. The graphs of WL dimension 1 have completely been
characterized in [1] and independently in [12] (however, such a
characterization for the graphs of higher WL dimension seems unachievable
[12]).

In the present paper, we study the WL dimension of the class of permutation
graphs. This subclass of the perfect graphs has a large number of applications
[15] and has been intensely studied since the late 1960s [24]. The original
definition is somewhat cumbersome: a permutation graph is a graph $X$ such
that there exists a labeling $\alpha_{1},\ldots,\alpha_{n}$ of its vertices
and a permutation $\pi\in\operatorname{Sym}(n)$ satisfying
$(i-j)(\pi(i)-\pi(j))<0$ if and only if $\alpha_{i}$ is adjacent to
$\alpha_{j}$. For our purpose, we will make use of the following equivalent
characterization (see [24]): a graph $X$ is a permutation graph if and only if
both $X$ and its complement are transitively orientable (see Section 2.2 for
further details). Based on this property, Coulborn [8] described a first
polynomial-time algorithm for testing isomorphism of permutation graphs. Some
other characterizations of the permutation graphs are known, e.g., as the
comparability graphs of partially ordered sets of order dimension at most two
[5]: this was used by Spinrad [26] to construct efficient recognition and
isomorphism algorithms.

A characterization of permutation graphs in terms of excluded induced
subgraphs was obtained by Gallai [13]. In the spirit of the above mentioned
result by Grohe [16], Grußien [21] considered the question of whether there is
a logic that captures polynomial time on all classes of graphs with excluded
induced subgraphs. The main result obtained there implies that the Weisfeiler-
Leman dimension of any permutation graph is bounded from above by an absolute
constant; however, its value has not been estimated (and it is unclear whether
it can be obtained within the approach of [21]). Our main result is as
follows.

######  Theorem 1.1.

The Weisfeiler-Leman dimension of the class of permutation graphs is at most
$18$.

It is shown in [25] that the Weisfeiler-Leman dimension of bipartite
permutation graphs is $2$ or $3$; thus, we expect that the bound from Theorem
1.1 can be improved.

The proof of Theorem 1.1 is based on the theory of coherent configurations and
is presented in Section 6. Let us discuss the scheme of the proof briefly. Let
$X$ be a (permutation) graph with vertex set $\Omega$. The coherent
configuration ${\cal X}$ of $X$ is the output of the 2-dim WL algorithm
applied to $X$ and can be thought of as an arc-colored directed complete graph
on $\Omega$.

We were not able to prove that a permutation graph can be identified by the
properties of its coherent configuration. To resolve this problem, we invoke
the theory of extensions of coherent configurations (see [7] and Section 3.6
in the present paper for further details). For each positive integer $m$, the
coherent configuration ${\cal X}$ can canonically be extended to a coherent
configuration $\widehat{{\cal X}}^{(m)}$ on the Cartesian power $\Omega^{m}$.
On the other hand, the number $\dim_{\mathsf{WL}}(X)$ is known to be less than
or equal to the tripled so-called separability number of ${\cal X}$, which is
estimated from above by means of $\widehat{\cal X}^{(m)}$. For our purpose, we
take $m=2$ and then it suffices to verify that the separability number of
${\cal X}$ is at most $6$.

The proof goes by induction the base of which is the case when the permutation
graph $X$ is uniquely orientable. In Section 5, this property is used to prove
that the individualization of two elements belonging to $\Omega^{2}$ is
sufficient for the Weisfeiler-Leman algorithm to split the coherent
configuration $\widehat{{\cal X}}^{(2)}$ into the discrete one. This in turn
implies that the separability number of ${\cal X}$ is at most $6$.

Now, let $X$ be a permutation graph which is not uniquely orientable. Then $X$
admits a non-trivial modular decomposition, and, as was implicitly proved in
[8], this decomposition can be chosen in a canonical way. In Section 4, we use
this fact to prove that this decomposition “can be seen” inside the coherent
configuration $\widehat{{\cal X}}^{(2)}$. This enables us to guarantee that
the separability number of ${\cal X}$ is less than or equal to the maximum
separability number of the coherent configurations of the smaller graphs
associated with the modular decomposition of $X$.

The paper is organized as follows. In order to make the proof as self-
contained as possible, we present in Section 2 the necessary notation and
facts about permutation graphs and in Section 3 those from the theory of
coherent configurations. More details about these topics can be found in the
monographs [15] and [7], respectively. In Section 4 we study an interplay
between modular decompositions of graphs and their coherent configurations, as
applied to algebraic isomorphisms. Sections 5 and 6 are devoted to the proof
of Theorem 1.1 by induction as described above.

### Notation.

Throughout the paper, $\Omega$ stands for a finite set. For
$\Delta\subseteq\Omega$, the diagonal of the Cartesian product
$\Delta\times\Delta$ is denoted by $1_{\Delta}$. For an equivalence relation
$e$ on a subset of $\Omega$, we denote by $\Omega/e$ the set of all classes of
$e$.

For a binary relation $r\subseteq\Omega\times\Omega$, we set
$r^{*}=\\{(\beta,\alpha)\\!:\ (\alpha,\beta)\in r\\}$, and
$r^{f}=\\{(\alpha^{f},\beta^{f})\\!:\ (\alpha,\beta)\in r\\}$ for any
bijection $f$ from $\Omega$ to another set. The left support of $r$ is defined
to be the set $\\{\alpha\in\Omega\\!:\ \alpha r\neq\varnothing\\}$, where
$\alpha r=\\{\beta\in\Omega\\!:\ (\alpha,\beta)\in r\\}$ is the neighborhood
of a point $\alpha\in\Omega$ in the relation $r$. The right support of $r$ is
the left support of $r^{*}$. For relations $r,s\subseteq\Omega\times\Omega$,
we put

$r\cdot s=\\{(\alpha,\beta)\\!:\ (\alpha,\gamma)\in r,\ (\gamma,\beta)\in
s\text{ for some }\gamma\in\Omega\\}.$

For $\Delta,\Gamma\subseteq\Omega$, we set
$r_{\Delta,\Gamma}=r\cap(\Delta\times\Gamma)$ and abbreviate
$r_{\Delta}:=r_{\Delta,\Delta}$.

For a set $S$ of relations on $\Omega$, we denote by $S^{\cup}$ the set of all
unions of the elements of $S$ and put $S^{*}=\\{s^{*}\\!:\ s\in S\\}$ and
$S^{f}=\\{s^{f}\\!:s\in S\\}$ for any bijection $f$ from $\Omega$ to another
set.

##  2\. Permutation graphs and their modular decomposition

###  2.1. Basic definitions.

By a graph we mean a finite simple undirected graph, i.e., a pair
$X=(\Omega,E)$ of a finite set $\Omega$ of vertices and an irreflexive
symmetric relation $E\subseteq\Omega\times\Omega$. The elements of $E=:E(X)$
are called edges111Traditionally, an _edge_ means a subset of two adjacent
vertices. In this paper, by an edge we mean an ordered pair of adjacent
vertices, which is usually called an _arc_., and $E$ is the edge set of the
graph $X$. Two vertices $\alpha$ and $\beta$ are adjacent (in $X$) whenever
$(\alpha,\beta)\in E$ (equivalently, $(\beta,\alpha)\in E$). The subgraph of
$X$ induced by a set $\Delta\subseteq\Omega$ is denoted by
$X_{\Delta}=(\Delta,E_{\Delta})$. A graph $X=(\Omega,E)$ is connected if the
transitive reflexive closure of $E$ equals $\Omega^{2}$. The complement of $X$
is the graph $\overline{X}=(\Omega,\overline{E})$ where
$\overline{E}=\Omega^{2}\setminus\left(E\cup 1_{\Omega}\right)$. A graph is
coconnected if its complement is connected.

###  2.2. Orientations of graphs.

An orientation of a graph $X=(\Omega,E)$ is a subset $A\subseteq E$ such that
$A\cap A^{*}=\varnothing$ and $A\cup A^{*}=E$. A orientation $A$ is called
transitive if $A\cdot A\subseteq A$, which means that
$(\alpha,\beta),(\beta,\gamma)\in A$ implies $(\alpha,\gamma)\in A$. A graph
is called transitively orientable (or a comparability graph) if it admits a
transitive orientation. A transitive orientation of a complete graph is called
a transitive tournament.

Following [15, Chapter 5], we define the $\Gamma$-relation of $X$ as a binary
relation on $E$ consisting of all pairs $(\alpha,\beta)$ and
$(\alpha^{\prime},\beta^{\prime})$ such that

$\quad\left(\alpha=\alpha^{\prime}\mbox{ and }(\beta,\beta^{\prime})\notin
E\right)\quad\mbox{or}\quad\left(\beta=\beta^{\prime}\mbox{ and
}(\alpha,\alpha^{\prime})\notin E\right).$

It is easily seen that this relation is symmetric and reflexive. The
transitive closure of the $\Gamma$-relation is an equivalence relation and
hence partitions $E$ into equivalence classes called the implication classes
of $X$. The implication class of $X$ containing an edge $\mathbf{e}\in E$ is
denoted by $I_{X}(\mathbf{e})$. In what follows, given a graph $X$, we
abbreviate, $I(\mathbf{e})=I_{X}(\mathbf{e})$ if $\mathbf{e}\in E$ and
$I(\mathbf{e})=I_{\overline{X}}(\mathbf{e})$ if $\mathbf{e}\in\overline{E}$.

######  Lemma 2.1.

([15, Theorem 5.1, Theorem 5.4])

Let $X$ be a transitively orientable graph and $\mathbf{e}$ any of its edges.
Then:

  * (i)

$I_{X}(\mathbf{e})\cap I_{X}(\mathbf{e})^{*}=\varnothing$;

  * (ii)

if $A$ is a transitive orientation of $X$, then $I_{X}(\mathbf{e})\subseteq A$
or $I_{X}(\mathbf{e})^{*}\subseteq A$.

A graph is said to be uniquely partially orderable (UPO) if it admits at most
two transitive orientations. (Note that if a UPO graph contains at least one
edge, then there are exactly two transitive orientations, one being the
reversal of the other.) For example, a connected bipartite graph is always
UPO, while a complete graph $K_{n}$ on $n$ vertices is UPO if and only if
$n\leq 2$.

A graph $X$ is called a permutation graph if and only if $X$ and
$\overline{X}$ are transitively orientable. Clearly, the class of permutation
graph is closed under taking complement and induced subgraphs. A (permutation)
graph $X$ is uniquely orientable if both $X$ and $\overline{X}$ are UPO
graphs. It follows from Lemma 2.1 that a permutation graph $X=(\Omega,E)$ is
uniquely orientable if and only if

(1) $I_{X}(\mathbf{e})\cup I_{X}(\mathbf{e})^{*}\cup
I_{\overline{X}}(\mathbf{f})\cup
I_{\overline{X}}(\mathbf{f})^{*}=\Omega^{2}\setminus 1_{\Omega}$

holds for every $\mathbf{e}\in E$ and every $\mathbf{f}\in\overline{E}$.

######  Lemma 2.2.

(cf. [15, Chapter 5, Exercise 5]) Let $A$ and $\overline{A}$ be transitive
orientations of a (permutation) graph and its complement, respectively. Then
$A\cup\overline{A}$ is a transitive tournament.

###### Proof.

Clearly, the relation $A\cup\overline{A}$ is anti-symmetric and irreflexive.
To prove that it is transitive, it suffices to show that it does not contain a
cycle of length $3$. Suppose on the contrary that
$(\alpha,\beta),(\beta,\gamma),(\gamma,\alpha)\in A\cup\overline{A}$. Without
loss of generality, we may assume $(\alpha,\beta),(\beta,\gamma)\in A$. Then
$(\alpha,\gamma)\in A$, as $A$ is a transitive orientation of the graph, a
contradiction. ∎

###  2.3. Composition graph.

Let $X_{0}$ be a graph with vertex set
$\\{\alpha_{1},\alpha_{2},\ldots,\alpha_{n}\\}$ and let ${\cal
C}=\\{X_{1},\ldots,X_{n}\\}$ be a collection of graphs whose vertex sets are
pairwise disjoint. The composition graph

$X:=X_{0}[X_{1},X_{2},\ldots,X_{n}]=X_{0}[{\cal C}]$

is formed as follows: for all $1\leq i,j\leq n$, replace the vertex
$\alpha_{i}$ in $X_{0}$ with the graph $X_{i}$ and join each vertex of $X_{i}$
to each vertex of $X_{j}$ whenever $\alpha_{i}$ is adjacent to $\alpha_{j}$ in
$X_{0}$. The vertex set $\Omega_{i}$ of the graph $X_{i}$, $i=1,\ldots,n$, is
partitive, i.e., every vertex of $X$, not belonging to $\Omega_{i}$, is
adjacent to either all or none of the vertices of $\Omega_{i}$. The sets
$\Omega_{i}$ are called the modules of $X$, and the corresponding
decomposition of the vertex set of $X$ is called modular. The composition
graph $X$ is non-trivial if $n\geq 2$ and $|\Omega_{i}|\geq 2$ for at least
one $i$.

######  Lemma 2.3.

Let $e$ be an equivalence relation on $\Omega$. Then a graph $(\Omega,E)$ is a
composition graph whose modules are the equivalence classes of $e$ if and only
if

(2) $e\cdot(E-e)=E-e=(E-e)\cdot e.$

###### Proof.

One has $(\alpha,\beta)\in E-e$ if and only if $(\alpha,\beta)\in E$ and
$\alpha,\beta$ belong to different equivalence classes of $e$. Thus, Eq. (2)
holds if and only if, for every two distinct $\Delta,\Gamma\in\Omega/e$, the
graph $(\Delta\cup\Gamma,E_{\Delta,\Gamma})$ is empty or complete bipartite.
The latter condition holds if and only if $(\Omega,E)$ is a composition graph
whose modules are the classes of $\Omega/e$. ∎

In what follows, a graph $X=(\Omega,E)$ satisfying Eq. (2) for some
equivalence relation $e$ will be refereed to as a composition graph with
respect to $e$. Note that this is equivalent to saying that $X=X_{0}[{\cal
C}]$ where ${\cal C}=\\{X_{\Delta}\mid\Delta\in\Omega/e\\}$ and $X_{0}$ is the
quotient graph of $X$ modulo $e$ (that is, the vertex set of $X_{0}$ is
$\Omega/e$ and two distinct vertices are adjacent in $X_{0}$ whenever there is
an edge between them).

Let $X=(\Omega,E)$ be a graph. Two vertices $\alpha,\beta$ are called
$0$-twins ($1$-twins, respectively) if $\alpha,\beta$ are not adjacent (are
adjacent, respectively) and, for any vertex
$\gamma\in\Omega\setminus\\{\alpha,\beta\\}$, the set $\gamma E$ contains
either both $\alpha$ and $\beta$ or none of them. A graph is irreducible if it
contains neither distinct $0$-twins nor $1$-twins, and reducible otherwise.
The relation “to be $0$-twins in $X$” is an equivalence relation on $\Omega$,
called the $0$-equivalence of $X$. The relation “to coincide or to be
$1$-twins in $X$” is also an equivalence relation on $\Omega$, called the
$1$-equivalence of $X$. The following statement is obvious.

######  Lemma 2.4.

A reducible graph is a non-trivial composition graph whose modules are either
all classes of the $0$-equivalence or all classes of the $1$-equivalence.

Let $P_{m}$ denote a path graph on $m$ vertices.

######  Lemma 2.5.

A uniquely orientable graph is either connected and coconnected or is $P_{m}$
or $\overline{P_{m}}$, $m=2,3$. In particular, an irreducible uniquely
orientable graph is connected and coconnected.

###### Proof.

Without loss of generality, suppose that a uniquely orientable graph $X$ is
not connected. Then $\overline{X}$ is connected and it is a composition graph
with two modules, namely, the vertex set of any connected component of $X$ and
its complement in $\Omega$. By [15, Theorem 5.12], every partitive set of a
UPO graph induces an empty graph. It follows that $X=K_{n}\cup K_{m}$ for some
integers $n,m$. Since $X$ is a UPO graph, it follows that $n\cdot m\leq 2$,
and we are done. ∎

For a graph $X=(\Omega,E)$ and $\mathbf{e}\in E\cup\overline{E}$, let us
denote by $\Omega(\mathbf{e})$ the set of vertices incident to at least one
element from $I(\mathbf{e})$, and by $X(\mathbf{e})$ the subgraph induced by
$\Omega(\mathbf{e})$ in $X$ or in $\overline{X}$ depending on whether
$\mathbf{e}\in E$ or $\mathbf{e}\in\overline{E}$.

######  Corollary 2.6.

Let $X=(\Omega,E)$ be an irreducible uniquely orientable graph. Then
$\Omega=\Omega(\mathbf{e})$ for every $\mathbf{e}\in E\cup\overline{E}$.

###### Proof.

Since $P_{m}$ and $\overline{P_{m}}$, $m=2,3$, are not irreducible, $X$ and
$\overline{X}$ are connected by Lemma 2.5. The lemma then follows from Eq.
(1). ∎

In the rest of this section, we show that an irreducible permutation graph is
a certain composition graph; this observation was implicitly used in [8].
Given a graph $X=(\Omega,E)$, define a binary relation $\sim$ on $\Omega$ as
follows: $\alpha\sim\beta$ if and only if $\alpha=\beta$ or there is an edge
$\mathbf{e}\in E$ such that the graph $X(\mathbf{e})$ is uniquely orientable
and $\alpha,\beta\in\Omega(\mathbf{e})$.

######  Lemma 2.7.

Let $X$ be an irreducible permutation graph that is not uniquely orientable.
Then the relation $\sim$ defined by $X$ is a non-trivial equivalence relation,
the classes of which induce uniquely orientable graphs.

###### Proof.

It follows from [8, Lemma 6] that whenever, for
$\mathbf{e},\mathbf{e}^{\prime}\in E$, the subgraphs $X(\mathbf{e})$ and
$X(\mathbf{e}^{\prime})$ are uniquely orientable, the sets
$\Omega(\mathbf{e})$ and $\Omega(\mathbf{e}^{\prime})$ are either equal or
disjoint. Therefore, $\sim$ is an equivalence relation whose equivalence
classes induce uniquely orientable graphs. Moreover, by [8, Lemma 5] and the
fact that $X$ is irreducible, there exist an edge $\mathbf{e}$ such that the
subgraph $X(\mathbf{e})$ is uniquely orientable. Since $X$ is not uniquely
orientable, $X\neq X(\mathbf{e})$ and we are done. ∎

######  Lemma 2.8.

In the notation of Lemma 2.7, $X$ is a non-trivial composition graph with
respect to the equivalence relation $\sim$.

###### Proof.

It suffices to show that every $\Delta\in\Omega/{\sim}$ is a partitive set of
$X$. This is obviously true if $|\Delta|=1$. If $|\Delta|>1$, then, by the
definition of $\sim$, there exists $\mathbf{e}\in E$ such that
$\Delta=\Omega(\mathbf{e})$. It follows from [8, Lemma 3] that the set
$\Omega(\mathbf{e})$ is partitive. Therefore, $X$ a composition graph with
respect to the equivalence relation $\sim$. By Lemma 2.7 this relation is non-
trivial, hence so is the composition graph. ∎

######  Remark 2.9.

Every module of the composition graph in Lemma 2.8 either induces a uniquely
orientable non-empty subgraph of $X$ or is a singleton.

Note that the composition graph defined in Lemma 2.8 is minimal with respect
to $|{\cal C}|$ among all composition graphs $X=X_{0}[{\cal C}]$ where $X_{0}$
is a permutation graph and ${\cal C}$ is a collection of uniquely orientable
subgraphs of $X$.

######  Lemma 2.10.

(cf. [15, Theorem 5.8]) Let $X$ be the composition graph as in Lemma 2.8. Then
for all distinct modules $\Delta,\Delta^{\prime}$ and every
$\mathbf{e}\in\Delta\times\Delta^{\prime}$, the implication class
$I(\mathbf{e})$ intersects neither $\Delta\times\Delta$ nor
$\Delta^{\prime}\times\Delta^{\prime}$, and, moreover,
$\Delta\times\Delta^{\prime}\subseteq I(\mathbf{e})$ and
$\Delta^{\prime}\times\Delta\subseteq I(\mathbf{e})^{*}$.

###### Proof.

Assume on the contrary that $I(\mathbf{e})$ contains, say,
$\mathbf{f}\in\Delta\times\Delta$. Then
$I(\mathbf{f})\subseteq\Delta\times\Delta$ by the definition of $\sim$ and Eq.
(1). Since two implication classes either coincide or are disjoint, we obtain
$I(\mathbf{e})=I\left(\mathbf{f}\right)\subseteq\Delta\times\Delta$, a
contradiction.

Further, let $\mathbf{e}=(\alpha,\beta)$ and $\mathbf{e}\in E$ (the case
$\mathbf{e}\in\overline{E}$ is similar). Then
$\\{\alpha\\}\times\Delta^{\prime}\subseteq E_{\Delta,\Delta^{\prime}}$. Note
the complement of $X_{\Delta^{\prime}}$ is connected by Lemma 2.5, since the
graph $X$ is irreducible and so is $X_{\Delta^{\prime}}$. Therefore, for every
$\beta^{\prime}\in\Delta^{\prime}$, there is a path from $\beta$ to
$\beta^{\prime}$ in the complement of $X_{\Delta^{\prime}}$. This implies that
$(\alpha,\beta^{\prime})\in I(\mathbf{e})$ and hence we obtain
$\\{\alpha\\}\times\Delta^{\prime}\subseteq I(\mathbf{e})$. Similarly, one can
see that $\Delta\times\\{\beta\\}\subseteq I(\mathbf{e})$. Thus, the
implication class $I(\mathbf{e})$ intersects non-trivially the implication
class $I(\mathbf{e^{\prime}})$ of every other edge $\mathbf{e^{\prime}}\in
E_{\Delta,\Delta^{\prime}}$, and hence $I(\mathbf{e})=I(\mathbf{e^{\prime}})$.
This implies $E_{\Delta,\Delta^{\prime}}\subseteq I(\mathbf{e})$ and, by
symmetry, $E_{\Delta^{\prime},\Delta}\subseteq I(\mathbf{e})^{*}$. ∎

##  3\. Coherent configurations and their extensions

In this section we provide a short background of the theory of coherent
configurations. We mainly follow the notation and terminology from [7], where
further details and all unexplained facts can be found.

###  3.1. Basic definitions

Let $\Omega$ be a finite set and $S$ a partition of $\Omega^{2}$; in
particular, the elements of $S$ are treated as binary relations on $\Omega$. A
pair $\mathcal{X}=(\Omega,S)$ is called a coherent configuration on $\Omega$
if the following conditions are satisfied:

  1. (C1)

the diagonal relation $1_{\Omega}$ is a union of some relations of $S$,

  2. (C2)

for each $s\in S$, the relation $s^{*}$ belongs to $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$.

In what follows, we write $S=S({\cal X})$; any relation belonging to $S$
(respectively, $S^{\cup}$) is called a basis relation (respectively, a
relation of ${\cal X}$). A set $\Delta\subseteq\Omega$ is called a fiber of
${\cal X}$ if the relation $1_{\Delta}$ is basis. The set of all fibers is
denoted by $F=F({\cal X})$. Any element of $F^{\cup}$ is called a homogeneity
set of ${\cal X}$. In particular, the (left, right) support of every relation
of ${\cal X}$ is a homogeneity set.

###  3.2. Isomorphisms and separability

Let ${\cal X}=(\Omega,S)$ and ${\cal X}^{\prime}=(\Omega^{\prime},S^{\prime})$
be two coherent configurations. A bijection $f\colon\Omega\to\Omega^{\prime}$
is called a (combinatorial) isomorphism from ${\cal X}$ to ${\cal X}^{\prime}$
if the relation $s^{f}$ belongs to $S^{\prime}$ for every $s\in S$. The
combinatorial isomorphism $f$ induces a natural bijection $\varphi\colon S\to
S^{\prime}$, $s\mapsto s^{f}$. One can see that $\varphi$ preserves the
numbers from the condition (C3), namely, the numbers $c_{rs}^{t}$ and
$c_{r^{\varphi},s^{\varphi}}^{t^{\varphi}}$ are equal for all $r,s,t\in S$.
Every bijection $\varphi\colon S\to S^{\prime}$ having this property is called
an algebraic isomorphism, written as $\varphi\colon{\cal X}\to{\cal
X}^{\prime}$. A coherent configuration is called separable if every algebraic
isomorphism from it to another coherent configuration is induced by an
isomorphism.

An algebraic isomorphism $\varphi\colon{\cal X}\to{\cal X}^{\prime}$ induces a
uniquely determined bijection $S^{\cup}\to{S^{\prime}}^{\cup}$ denoted also by
$\varphi$. For any $\Delta\in F^{\cup}$, we have
$\varphi(1_{\Delta})=1_{\Delta^{\varphi}}$ for a uniquely determined
$\Delta^{\varphi}\in{F^{\prime}}^{\cup}$. The induced mapping
$\Delta\mapsto\Delta^{\varphi}$ defines a bijection
$F^{\cup}\to{F^{\prime}}^{\cup}$ that takes $F$ to $F^{\prime}$.

###  3.3. Parabolics.

An equivalence relation $e$ on a set $\Delta\subseteq\Omega$ is called a
partial parabolic of the coherent configuration ${\cal X}$ if $e$ is the union
of some basis relations; if, in addition, $\Delta=\Omega$, then $e$ is called
a parabolic of ${\cal X}$. Note that the transitive closure of any symmetric
relation of ${\cal X}$ is a partial parabolic.

A (partial) parabolic $e$ is said to be decomposable if $e$ is the union of
pairwise disjoint non-empty partial parabolics; we say that $e$ is
indecomposable if it is not decomposable. Every partial parabolic is the
disjoint union of uniquely determined indecomposable partial parabolics; they
are called the indecomposable components of $e$.

Let $e$ be a partial parabolic, and let $\Delta\in\Omega/e$. Denote by
$S_{\Omega/e}$ and $S_{\Delta}$ the sets of all non-empty relations

$s_{\scriptscriptstyle{\Omega/e}}=\\{(\Delta,\Gamma)\in\Omega/e\times\Omega/e\colon\
s_{\scriptscriptstyle{\Delta,\Gamma}}\neq\varnothing\\}\quad\text{and}\quad
s_{\scriptscriptstyle{\Delta}}=s_{\scriptscriptstyle{\Delta,\Delta}},$

respectively, where $s\in S$. Then the pairs ${\cal
X}_{\Omega/e}=(\Omega/e,S_{\Omega/e})$ and ${\cal
X}_{\Delta}=(\Delta,S_{\Delta})$ are coherent configurations called the
quotient of ${\cal X}$ modulo $e$ and restriction of ${\cal X}$ to $\Delta$.
Note that when $e=1_{\Delta}$ for a homogeneity set $\Delta$, we have ${\cal
X}_{\Omega/e}={\cal X}_{\Delta}$.

Let $e^{\circ}$ be an indecomposable component of $e$. Then
$e^{\circ}_{\Omega/e}$ is a reflexive relation of ${\cal X}_{\Omega/e}$, that
is, $e^{\circ}_{\Omega/e}=1_{\Delta^{\circ}}$ where $\Delta^{\circ}$ is a
homogeneity set of ${\cal X}_{\Omega/e}$. Let $\Pi(e)$ denote the set of all
$\Delta^{\circ}$ as $e^{\circ}$ runs over the set of all indecomposable
component of $e$. Note that $\Pi(e)$ is a partition of $\Omega/e$, while the
corresponding equivalence relation is a parabolic of ${\cal X}_{\Omega/e}$.

Any algebraic isomorphism $\varphi\colon{\cal X}\to{\cal X}^{\prime}$ induces
a bijection between partial parabolics of ${\cal X}$ and ${\cal X}^{\prime}$
that preserves the property of a partial parabolic to be indecomposable. Let
$e$ be a partial parabolic of ${\cal X}$ and $e^{\prime}=\varphi(e)$. Then the
mapping
$s_{\scriptscriptstyle{\Omega/e}}\mapsto\varphi(s)_{\scriptscriptstyle{\Omega^{\prime}/e^{\prime}}}$,
$s\in S$, defines an algebraic isomorphism $\varphi_{\Omega/e}\colon{\cal
X}_{\Omega/e}\to{\cal X}^{\prime}_{\Omega^{\prime}/e^{\prime}}$.

We say that the classes $\Delta\in\Omega/e$ and
$\Delta^{\prime}\in\Omega^{\prime}/e^{\prime}$ are $\varphi$-associated if
$\varphi$ takes the indecomposable component of $e$ containing $\Delta$ as a
class to the indecomposable component of $e^{\prime}$ containing
$\Delta^{\prime}$ as a class. According to [7, Example 2.3.16], in this case
$\varphi$ induces an algebraic isomorphism
$\varphi_{\Delta,\Delta^{\prime}}\colon{\cal X}_{\Delta}\to{\cal
X}^{\prime}_{\Delta^{\prime}}$ such that
$\varphi_{\Delta,\Delta^{\prime}}(s_{\Delta})=\varphi(s)_{\Delta^{\prime}}$
for every $s\in S$.

###  3.4. Coherent closure

There is a natural partial order $\leq$ on the set of all coherent
configurations on the same set $\Omega$. Namely, given two such coherent
configurations ${\cal X}$ and ${\cal X}^{\prime}$, we set ${\cal X}\leq{\cal
X}^{\prime}$ if and only if each basis relation of ${\cal X}$ is the union of
some basis relations of ${\cal X}^{\prime}$. In other words, this means that
the partition of $\Omega^{2}$ into basis relations of ${\cal X}^{\prime}$ is
finer than the partition of $\Omega^{2}$ into basis relations of ${\cal X}$.
The minimal and maximal elements with respect to this ordering are the trivial
and discrete coherent configurations: the basis relations of the former one
are the reflexive relation $1_{\Omega}$ and its complement in
$\Omega\times\Omega$ (if $|\Omega|\geq 1$), whereas the basis relations of the
latter one are singletons. Note that the trivial and discrete coherent
configurations are separable.

######  Lemma 3.1.

A coherent configuration on $\Omega$ having a transitive tournament on
$\Omega$ as a relation is discrete.

###### Proof.

Let $s$ be a relation of a coherent configuration on $\Omega$. Suppose that
the supports of $s$ equal $\Omega$ and $s$ is a transitive tournament. Then
there are no two distinct points $\alpha,\beta$ such that $|\alpha s|=|\beta
s|$. Hence, no two distinct points lie in the same fiber, which means that the
coherent configuration is discrete. ∎

The coherent closure $\operatorname{\mathsf{WL}}(T)$ of a set $T$ of binary
relations on $\Omega$, is defined to be the smallest coherent configuration on
$\Omega$ such that each relation of $T$ is a union of some basis relations.
The coherent closure is canonical with respect to algebraic isomorphisms in
the sense that if
$\varphi,\psi\colon\operatorname{\mathsf{WL}}{(T)}\to\operatorname{\mathsf{WL}}{(T^{\prime})}$
are algebraic isomorphisms such that $\varphi(t)=\psi(t)$ for all $t\in T$,
then $\varphi=\psi$. Furthermore, the coherent closure is a closure
operator222with respect to the natural partial order on the partitions of the
same set. on the set of all partitions of $\Omega^{2}$ satisfying conditions
(C1) and (C2) in the definition of a coherent configuration.

For points $\alpha,\beta,\ldots\in\Omega$, we denote by ${\cal
X}_{\alpha,\beta,\ldots}$ the coherent closure of the union of $S$ and the set
$\\{1_{\\{\alpha\\}},1_{\\{\beta\\}},\ldots\\}$.

For an equivalence relation $e$ on $\Omega$, we denote by ${\cal X}_{e}$ the
coherent closure of the union of $S$ and $\\{e\\}$.

For a partition $\pi$ of $\Omega$, we denote by ${\cal X}_{\pi}$ the coherent
closure of the union of $S$ and all of $1_{\Delta}$, $\Delta\in\pi$.

The coherent configuration of a graph $X$ is defined to be the coherent
closure of its edge set:
$\operatorname{\mathsf{WL}}(X)=\operatorname{\mathsf{WL}}(\\{E(X)\\})$. Note
that $\operatorname{\mathsf{WL}}(X)=\operatorname{\mathsf{WL}}(\overline{X})$.

######  Lemma 3.2.

The $0$-equivalence and $1$-equivalence of a graph are parabolics of its
coherent configuration.

###### Proof.

Follows from [14, Proposition 4.10].∎

###  3.5. Direct sum and tensor product.

Let ${\cal X}=(\Omega,S)$ and ${\cal X}^{\prime}=(\Omega^{\prime},S^{\prime})$
be two coherent configurations. Denote by $\Omega\sqcup\Omega^{\prime}$ the
disjoint union of $\Omega$ and $\Omega^{\prime}$, and by $S\boxplus
S^{\prime}$ the union of the set $S\sqcup S^{\prime}$ and the set of all
relations $\Delta\times\Delta^{\prime}$ and $\Delta^{\prime}\times\Delta$ with
$\Delta\in F$ and $\Delta^{\prime}\in F^{\prime}$. Then the pair

${\cal X}\boxplus{\cal X}^{\prime}=(\Omega\sqcup\Omega^{\prime},S\boxplus
S^{\prime})$

is a coherent configuration called the direct sum of ${\cal X}$ and ${\cal
X}^{\prime}$. One can see that ${\cal X}\boxplus{\cal X}^{\prime}$ is the
smallest coherent configuration ${\cal Y}$ on $\Omega\sqcup\Omega^{\prime}$
such that ${\cal X}={\cal Y}_{\Omega}$ and ${\cal X}^{\prime}={\cal
Y}_{\Omega^{\prime}}$. It should be noted that ${\cal X}\boxplus{\cal
X}^{\prime}$ is separable if and only if so are ${\cal X}$ and ${\cal
X}^{\prime}$, see [7, Corollary 3.2.8].

######  Lemma 3.3.

Let $X$ be a composition graph and $\pi$ be the partition of the vertex set of
$X$ into the modules of this composition. Then
$\operatorname{\mathsf{WL}}{(X)}_{\pi}=\boxplus_{\Delta\in\pi}\operatorname{\mathsf{WL}}{(X_{\Delta})}$.

###### Proof.

Let $X=(\Omega,E)$. Then, given distinct $\Delta,\Gamma\in\pi$, we have

$E_{\Delta,\Gamma}=\varnothing\ \text{ or }\ \Delta\times\Gamma\subseteq E.$

Let $X^{\prime}=(\Omega,E^{\prime})$ be the graph obtained from $X$ by
removing the set $E_{0}$ of all edges $E_{\Delta,\Gamma}$, $\Delta\neq\Gamma$.
Then the vertex set of every connected component of $X^{\prime}$ is contained
in some $\Delta\in\pi$. Moreover, $E^{\prime}=E\setminus E_{0}$ and
$E=E^{\prime}\cup E_{0}$. Since $E_{0}$ is a relation of both
$\operatorname{\mathsf{WL}}{(X^{\prime})}_{\pi}$ and
$\operatorname{\mathsf{WL}}{(X)}_{\pi}$, we obtain

$\operatorname{\mathsf{WL}}{(X^{\prime})}_{\pi}=\operatorname{\mathsf{WL}}{(X)}_{\pi}.$

It is easily seen that each graph $X_{\Delta}$ is a union of connected
components of the graph $X^{\prime}$, so that the lemma follows from [7,
Exercise 3.7.35]. ∎

Given coherent configurations ${\cal X}_{1}=(\Omega_{1},S_{1})$ and ${\cal
X}_{2}=(\Omega_{2},S_{2})$ denote by $S_{1}\otimes S_{2}$ the set of all
relations

$s_{1}\otimes
s_{2}=\left\\{((\alpha_{1},\alpha_{2}),(\beta_{1},\beta_{2}))\in(\Omega_{1}\times\Omega_{2})^{2}:\
(\alpha_{1},\beta_{1})\in s_{1},\ (\alpha_{2},\beta_{2})\in s_{2}\right\\},$

where $s_{1}\in S_{1}$ and $s_{2}\in S_{2}$. Then the pair ${\cal
X}_{1}\otimes{\cal X}_{2}=(\Omega_{1}\times\Omega_{2},S_{1}\otimes S_{2})$ is
a coherent configuration. It is called the tensor product of ${\cal X}_{1}$
and ${\cal X}_{2}$. For each positive integer $m$, the $m$-tensor power of
${\cal X}$ is denoted by ${\cal X}^{m}$.

###  3.6. Extensions of coherent configurations and their algebraic
isomorphisms

Let ${\cal X}$ be a coherent configuration on $\Omega$ and $m$ a positive
integer. The $m$-extension of ${\cal X}$ is by definition the following
coherent configuration on $\Omega^{m}$:

$\widehat{\cal X}^{(m)}=\operatorname{\mathsf{WL}}\left(S\left({\cal
X}^{m}\right)\cup\\{1_{\operatorname{Diag}(\Omega^{m})}\\}\right)$

where ${\cal X}^{m}$ is the $m$-fold tensor power of ${\cal X}$. We observe
that except for trivial cases the $m$-extension is a non-homogeneous coherent
configuration for all $m\geq 2$. From the definition it follows that
$\widehat{\cal X}^{(1)}={\cal X}$ and $\widehat{\cal X}^{(m)}\geq{\cal
X}^{m}$.

Let $\varphi\colon{\cal X}\to{\cal X}^{\prime}$ be an algebraic isomorphism.
Then $\varphi$ induces the component-wise algebraic isomorphism
$\varphi^{m}:{\cal X}^{m}\to{{\cal X}^{\prime}}^{m}$. An algebraic isomorphism
$\psi\colon\widehat{\cal X}^{(m)}\to\widehat{{\cal X}}^{\prime(m)}$ is called
an $m$-extension if

  1. (1)

$(\operatorname{Diag}(\Omega^{m}))^{\psi}=\operatorname{Diag}((\Omega^{\prime})^{m})$,

  2. (2)

$s^{\psi}=s^{\varphi^{m}}$ for all $s\in S({\cal X}^{m})$.

Each algebraic isomorphism obviously has a 1-extension, which always coincides
with it. Furthermore, for any $m$ the existence of the $m$-extension of
$\varphi$ implies its uniqueness (this follows from the canonicity of the
coherent closure with respect to algebraic isomorphisms); we denote it by
$\widehat{\varphi}^{(m)}$. We note that not every algebraic isomorphism has an
$m$-extension.

An algebraic isomorphism is called an $m$-isomorphism if it has the
$m$-extension. Every algebraic isomorphism induced by some isomorphism is an
$m$-isomorphism for all $m$. Note that every $m$-isomorphism is a
$k$-isomorphism for all $k\leq m$.

The coherent configuration

$\overline{\cal X}=\overline{\cal X}^{(m)}=((\widehat{\cal
X}^{(m)})_{\operatorname{Diag}(\Omega^{m})})^{\partial_{m}^{-1}},$

where $\partial_{m}\colon\alpha\mapsto(\alpha,\ldots,\alpha)$ is the diagonal
mapping from $\Omega$ to $\Omega^{m}$, is called the $m$-closure of ${\cal
X}$; if ${\cal X}={\overline{\cal X}}^{(m)}$, then ${\cal X}$ is said to be
$m$-closed (in particular, any coherent configuration is $1$-closed). Any
$m$-isomorphism $\varphi$ uniquely extends to the algebraic isomorphism
$\overline{\varphi}^{(m)}$ between the corresponding $m$-closures.

A coherent configuration ${\cal X}$ is said to be $m$-separable if, for all
${\cal X}^{\prime}$, every $m$-isomorphism from ${\cal X}$ to ${\cal
X}^{\prime}$ is induced by an isomorphism. The integer

$s({\cal X})=\min\\{m:\ {\cal X}\ \text{is $m$-separable}\\}$

is called the separability number of ${\cal X}$. Obviously, $s({\cal X})=1$ if
and only if a coherent configuration ${\cal X}$ is separable.

We will frequently use throughout the paper the following lemma (see [10,
Lemma 6.2]). Below, given $s\subseteq\Omega^{2}$ and $i,j\in\\{1,\ldots,m\\}$,
we set

$\operatorname{cyl}_{s}(i,j)=\\{(x,y)\in\Omega^{m}\times\Omega^{m}\colon\
(x_{i},y_{j})\in s\\}.$

######  Lemma 3.4.

Let ${\cal X}$ be a coherent configuration on $\Omega$ and $m$ a positive
integer. For all $s\in S({\cal X})^{\cup}$ and $i,j\in\\{1,\ldots,m\\}$, one
has:

  1. (i)

$\operatorname{cyl}_{s}(i,j)$ is a relation of the coherent configuration
$\widehat{\cal X}^{(m)}$;

  2. (ii)

$\operatorname{cyl}_{s}(i,j)^{\widehat{\varphi}}=\operatorname{cyl}_{s^{\overline{\varphi}}}(i,j)$
for any $m$-isomorphism $\varphi$, where
$\widehat{\varphi}=\widehat{\varphi}^{(m)}$ and
$\overline{\varphi}=\overline{\varphi}^{(m)}$.

##  4\. Composition graphs and their coherent configurations

In this section we study the coherent configurations of composition graphs and
their algebraic isomorphisms. Throughout the section, let $X=(\Omega,E)$ be a
composition graph with respect to an equivalence relation $e$ on $\Omega$,
$X_{0}$ the quotient graph of $X$ modulo $e$, and $\pi=\Omega/e$.

######  Lemma 4.1.

In the above notation, one has

$\operatorname{\mathsf{WL}}{(X)}_{\pi}=\boxplus_{\Delta\in\pi}\operatorname{\mathsf{WL}}{(X_{\Delta})}\quad\mbox{and}\quad\operatorname{\mathsf{WL}}{(X)}_{\pi}\geq\operatorname{\mathsf{WL}}{(X)}_{e}.$

In particular, the restriction of $\operatorname{\mathsf{WL}}{(X)}_{e}$ to any
$\Delta\in\pi$ equals $\operatorname{\mathsf{WL}}{(X_{\Delta})}$.

###### Proof.

The first formula follows from Lemma 3.3. Further, as $e$ is a parabolic of
$\operatorname{\mathsf{WL}}{(X)}_{\pi}$ and
$\operatorname{\mathsf{WL}}{(X)}_{\pi}\geq\operatorname{\mathsf{WL}}{(X)}$,
one has
$\operatorname{\mathsf{WL}}{(X)}_{\pi}\geq\operatorname{\mathsf{WL}}{(X)}_{e}$
and hence:

$\operatorname{\mathsf{WL}}{(X_{\Delta})}=\left(\operatorname{\mathsf{WL}}{(X)}_{\pi}\right)_{\Delta}\geq\left(\operatorname{\mathsf{WL}}{(X)}_{e}\right)_{\Delta}\geq\operatorname{\mathsf{WL}}{(X_{\Delta})},$

whence the lemma follows. ∎

The next theorem involves the notation and definitions from Section 3.3.

######  Theorem 4.2.

In the above notation, let ${\cal X}^{\prime}$ be a coherent configuration on
$\Omega^{\prime}$, $\varphi\colon\operatorname{\mathsf{WL}}{(X)_{e}}\to{\cal
X}^{\prime}$ be an algebraic isomorphism, $e^{\prime}=\varphi(e)$,
$\pi^{\prime}=\Omega^{\prime}/e^{\prime}$, and $E^{\prime}=\varphi(E)$. Then
the graph $X^{\prime}=(\Omega^{\prime},E^{\prime})$ is a composition graph
with respect to $e^{\prime}$. Moreover, one has:

  * (i)

${\cal X}^{\prime}=\operatorname{\mathsf{WL}}{(X^{\prime})_{e^{\prime}}}$;

  * (ii)

$\varphi_{\Delta,\Delta^{\prime}}\left(\operatorname{\mathsf{WL}}{(X_{\Delta})}\right)=\operatorname{\mathsf{WL}}{(X^{\prime}_{\Delta^{\prime}})}$
for all $\varphi$-associated $\Delta\in\pi$ and
$\Delta^{\prime}\in\pi^{\prime}$;

  * (iii)

$\varphi$ induces an algebraic isomorphism
$\varphi_{0}\colon\operatorname{\mathsf{WL}}(X_{0})_{\Pi}\to\operatorname{\mathsf{WL}}(X^{\prime}_{0})_{\Pi^{\prime}}$,
where $\Pi=\Pi(e)$ and $\Pi^{\prime}=\Pi(e^{\prime})$.

###### Proof.

Recall that $E$ is a relation of the coherent configuration ${\cal
X}=\operatorname{\mathsf{WL}}{(X)}_{e}$ and, by Lemma 2.3, one has
$e\cdot(E-e)=(E-e)\cdot e=E-e$. Since algebraic isomorphism respect the set-
theoretical operations with relations, we obtain
$e^{\prime}\cdot(E^{\prime}-e^{\prime})=(E^{\prime}-e^{\prime})\cdot
e^{\prime}=E^{\prime}-e^{\prime}$. Hence, by Lemma 2.3, $X^{\prime}$ is a
composition graph with respect to $e^{\prime}$. Then (i) follows from the
definition of $X^{\prime}$, whereas (ii) follows from the last statement of
Lemma 4.1. Finally, the algebraic isomorphism $\varphi$ induces an algebraic
isomorphism $\varphi_{0}\colon{\cal X}_{\Omega/e}\to{\cal
X}^{\prime}_{\Omega^{\prime}/e^{\prime}}$ which takes the edge set
$E_{\Omega/e}$ of $X_{0}$ to the edge set
$E^{\prime}_{\Omega^{\prime}/e^{\prime}}$ of $X_{0}^{\prime}$. Therefore,
$\varphi_{0}(\operatorname{\mathsf{WL}}(X_{0}))=\operatorname{\mathsf{WL}}(X^{\prime}_{0})$.
It remains to observe that $\varphi$ and hence $\varphi_{0}$ takes the classes
of $\Pi$ to those of $\Pi^{\prime}$. ∎

######  Theorem 4.3.

In the notation of Theorem 4.2, the following holds:

  * (i)

if $\varphi_{0}$ and each of $\varphi_{\Delta,\Delta^{\prime}}$ are induced by
isomorphisms, then so is $\varphi$;

  * (ii)

if $\varphi$ is an $m$-isomorphism for some natural $m$, then so are
$\varphi_{0}$ and each of $\varphi_{\Delta,\Delta^{\prime}}$.

###### Proof.

Let $f_{0}\colon\pi\to\pi^{\prime},\Delta\mapsto\Delta^{\prime}$ be a
bijection that induces $\varphi_{0}$. Further, let
$f_{\Delta,\Delta^{\prime}}\colon\Delta\to\Delta^{\prime}$ be a bijection that
induces $\varphi_{\Delta,\Delta^{\prime}}$. Then there exists a uniquely
determined bijection $f\colon\Omega\to\Omega^{\prime}$ such that
$f\mid_{\Delta}=f_{\Delta,\Delta^{\prime}}$ for all $\Delta\in\pi$. We shall
prove that $f$ induces $\varphi$, i.e., $s^{f}=\varphi(s)$ for all basis
relations $s$ of the coherent configuration
$\operatorname{\mathsf{WL}}{(X)}_{e}$.

Let us first assume that $s\cap e=\varnothing$. Then, by Lemma 4.1 and by the
definition of a direct sum of coherent configurations, one can see that

$s=\bigcup_{(\Delta_{1},\Delta_{2})\in
s_{\Omega/e}}\Delta_{1}\times\Delta_{2}$

and then

$s^{f}=\bigcup_{(\Delta_{1}^{\prime},\Delta_{2}^{\prime})\in(s_{\Omega/e})^{f_{0}}}\Delta_{1}^{\prime}\times\Delta_{2}^{\prime}.$

Since $f_{0}$ induces $\varphi_{0}$, it follows that
$(s_{\Omega/e})^{f_{0}}=\varphi_{0}(s_{\Omega/e})=\varphi(s)_{\Omega^{\prime}/\varphi(e)}=s^{\prime}_{\Omega^{\prime}/e^{\prime}}$,
where $s^{\prime}=\varphi(s)$. Thus, $s^{f}=\varphi(s)$.

Now let $s\subseteq e$. Denote by $e^{\circ}$ be the indecomposable component
of $e$ that contains $s$. Then $s=\bigcup_{\Delta\in\Lambda}s_{\Delta}$, where
$\Lambda=\Omega/e^{\circ}$ is a class of $\Pi$. Define
$\Lambda^{\prime}=\Omega^{\prime}/{\varphi(e^{\circ})}$, which is a class of
$\Pi^{\prime}$. Then:

$s^{f}=\bigcup_{\Delta^{f}\in\Lambda^{f}}\left(s_{\Delta}\right)^{f}=\bigcup_{\Delta^{\prime}\in\Lambda^{\prime}}\left(s_{\Delta}\right)^{f_{\Delta,\Delta^{\prime}}}=\bigcup_{\Delta^{\prime}\in\Lambda^{\prime}}\varphi_{\Delta,\Delta^{\prime}}\left(s_{\Delta}\right)=\bigcup_{\Delta^{\prime}\in\Lambda^{\prime}}\varphi(s)_{\Delta^{\prime}}=\varphi(s).$

(ii) Put ${\cal X}=\operatorname{\mathsf{WL}}{(X)}_{e}$ and let ${\cal
X}^{\prime}$ be as in Theorem 4.2(i). Denote by $\widehat{{\cal
X}},\widehat{\cal X}^{\prime}$ the $m$-extensions of ${\cal X}$ and ${\cal
X}^{\prime}$, respectively, and by $\widehat{\varphi}\colon\widehat{\cal
X}\to\widehat{\cal X}^{\prime}$ the $m$-extension of $\varphi$. Then, for
every $\Delta\in\pi$, we have $\operatorname{\mathsf{WL}}(X_{\Delta})={\cal
X}_{\Delta}$ by Lemma 4.1 and

$\widehat{{\cal X}}_{\Delta^{m}}\geq\widehat{{\cal X}_{\Delta}}^{(m)}.$

It follows from Lemma 3.4(i) that $\cap_{1\leq i,j\leq
m}\operatorname{cyl}_{e}(i,j)$ is a relation of $\widehat{\cal X}$. Therefore,
the support of this relation, which equals
$\Omega^{\prime}=\cup_{\Delta\in\pi}\Delta^{m}$, is a homogeneity set of
$\widehat{\cal X}$. Furthermore, since $e^{m}$ is a parabolic of ${\cal
X}^{m}$, it follows that $(e^{m})_{\Omega^{\prime}}$ is a partial parabolic of
$\widehat{\cal X}$, whose classes are $\Delta^{m}$, $\Delta\in\pi$. Hence we
can define an algebraic isomorphism
$\widehat{\psi}=\widehat{\varphi}_{\Delta^{m}}$ from $\widehat{\cal
X}_{\Delta^{m}}$ to $\widehat{\cal X}^{\prime}_{(\Delta^{\prime})^{m}}$. Since
$\operatorname{Diag}{(\Delta^{m})}=\operatorname{Diag}{(\Omega^{m})}\cap\Delta^{m}$,
one can see that $\widehat{\psi}$ takes $\operatorname{Diag}{(\Delta^{m}})$ to
$\operatorname{Diag}{((\Delta^{\prime})^{m})}$. Moreover, for a basis relation
$s=s_{1}\otimes\cdots\otimes s_{m}$ of ${\cal X}^{m}$,

$\widehat{\psi}(s_{\Delta^{m}})=\widehat{\varphi}_{\Delta^{m}}((s_{1})_{\Delta}\otimes\cdots\otimes(s_{m})_{\Delta})=\widehat{\varphi}(s_{1}\otimes\cdots\otimes
s_{m})_{\Delta^{m}}=(\varphi_{\Delta,\Delta^{\prime}})^{m}(s).$

Thus, $\widehat{\psi}$ is the $m$-extension of
$\varphi_{\Delta,\Delta^{\prime}}$. ∎

##  5\. Uniquely orientable graphs

In this section, we obtain an upper bound on the separability number of
uniquely orientable graphs. This bound follows from Theorem 5.2. Its proof
requires the lemma below, which will also be used in Section 6. In what
follows, let $X=(\Omega,E)$ be a graph, ${\cal
X}=\operatorname{\mathsf{WL}}(X)$, $\widehat{\cal X}$ denote ${\cal X}^{(2)}$,
and $\partial=\partial_{2}\colon\alpha\mapsto(\alpha,\alpha)$ be the diagonal
mapping from $\Omega$ to $\Omega^{2}$.

######  Lemma 5.1.

Let $X$ be an irreducible permutation graph. Denote by $e_{1}=e_{1}(X)$ and
$e_{2}=e_{2}(X)$ partial equivalence relations on $\Omega^{2}$ such that

$\Omega^{2}/e_{1}=\\{I(\mathbf{e})\mid\mathbf{e}\in
E\\}\quad\text{and}\quad\Omega^{2}/e_{2}=\\{\Delta^{2}\setminus\operatorname{Diag}{\left(\Delta^{2}\right)}\mid\Delta\in\Omega/{\sim}\\}.$

Then $e_{1},e_{2}$ are partial parabolics of $\widehat{{\cal X}}$.

###### Proof.

By Lemma 3.4, the coherent configuration $\widehat{{\cal X}}$ has the
following relations

$\displaystyle L_{1}$ $\displaystyle=$
$\displaystyle\operatorname{cyl}_{1_{\Omega}}(2,2)\cap\operatorname{cyl}_{\overline{E}}(1,1)\cap\operatorname{cyl}_{E}(1,2)\cap\operatorname{cyl}_{E}(2,1),$
$\displaystyle L_{2}$ $\displaystyle=$
$\displaystyle\operatorname{cyl}_{1_{\Omega}}(1,1)\cap\operatorname{cyl}_{\overline{E}}(2,2)\cap\operatorname{cyl}_{E}(1,2)\cap\operatorname{cyl}_{E}(2,1).$

Hence $\widehat{\cal X}$ has the relation $L_{1}\cup L_{2}$, which is exactly
the $\Gamma$-relation on the edges of $X$. Therefore, $e_{1}$ coincides with
the transitive closure of $L_{1}\cup L_{2}$, which is a partial parabolic of
$\widehat{{\cal X}}$.

Let us prove that $e_{2}$ is a partial parabolic of $\widehat{\cal X}$. Define
a partial parabolic $e_{0}=e_{1}(X)\cup e_{1}(\overline{X}){\cup
1_{\operatorname{Diag}(\Omega^{2})}}$ of $\widehat{\cal X}$. Observe that by
Eq. (1) every class
$\Delta^{2}\setminus\operatorname{Diag}{\left(\Delta^{2}\right)}$ of $e_{2}$,
$\Delta\in\Omega/{\sim}$, is the union of the four implication classes of
$X_{\Delta}$, which are classes of $e_{0}$. In order to identify the classes
of $e_{2}$, let us define an auxiliary relation

$s:=\left(\operatorname{cyl}_{1_{\Omega}}(1,1)\cup\operatorname{cyl}_{1_{\Omega}}(2,2)\right)\cap\left(\left(E\cup\overline{E}\right)\times\operatorname{Diag}{\left(\Omega^{2}\right)}\right)$

Observe that $s$ is a relation of $\widehat{{\cal X}}$. Indeed, $E$ coincides
with the support of
$\operatorname{cyl}_{1_{\Omega}}(1,1)\cap\operatorname{cyl}_{E}(1,2)\cap\operatorname{cyl}_{1_{\Omega}}(2,2)$,
which is a relation of $\widehat{{\cal X}}$ by Lemma 3.4. Hence $E$ (and
similarly $\overline{E}$) is a homogeneity set of $\widehat{{\cal X}}$, whence
$s\in S({\cal X})^{\cup}$.

Note that $s$ consists of all pairs $((\alpha,\beta),(\gamma,\gamma))$ where
$(\alpha,\beta)\in E\cup\overline{E}$ and $\gamma\in\\{\alpha,\beta\\}$. Put
$N(\mathbf{e}):=\cup_{\mathbf{f}\in I(\mathbf{e})}\mathbf{f}s$ (here we recall
that $\mathbf{f}s$ means the neighborhood of a point $\mathbf{f}$ in the
relation $s$). Then, for every $\mathbf{e}\in E\cup\overline{E}$, it follows
from the definition of $\Omega(\mathbf{e})$ (see the paragraph before
Corollary 2.6) that

$N(\mathbf{e})=\Omega(\mathbf{e})^{\partial}.$

Suppose that $\Delta\in\Omega/{\sim}$ and $\mathbf{e}\in E\cup\overline{E}$.
If $\mathbf{e}\in\Delta\times\Delta^{\prime}$ for some
$\Delta^{\prime}\in\Omega/{\sim}$, $\Delta\neq\Delta^{\prime}$, then
$\Delta^{\partial},\Delta^{\prime\partial}\subsetneq N(\mathbf{e})$ by Lemma
2.10. On the other hand, if
$\mathbf{e}\in\Delta^{2}\setminus\operatorname{Diag}{\left(\Delta^{2}\right)}$,
then $N(\mathbf{e})=\Omega(\mathbf{e})^{\partial}=\Delta^{\partial}$ by
Corollary 2.6; hence, given $\mathbf{f}\in E\cup\overline{E}$, one has

(3) $N(\mathbf{e})=N(\mathbf{f})\quad\text{if and only
if}\quad\mathbf{f}\in\Delta^{2}\setminus\operatorname{Diag}{\left(\Delta^{2}\right)}.$

Now, if $\rho$ denotes the natural surjection
$\rho\colon\Omega^{2}\to\Omega^{2}/e_{0}$, then:

  * •

the $\rho$-image of $\operatorname{Diag}{\left(\Omega^{2}\right)}$ is
naturally identified with $\operatorname{Diag}{\left(\Omega^{2}\right)}$
itself;

  * •

the $\rho$-image of $I(\mathbf{e})$ is a singleton for every $\mathbf{e}\in
E\cup\overline{E}$;

  * •

the set of all pairs $\rho(I(\mathbf{e}))$ and $\rho(I(\mathbf{f}))$ such that
$\rho(N(\mathbf{e}))=\rho(N(\mathbf{f}))$ is an equivalence relation, say
$e^{\prime}$, on $\rho\left(E\cup\overline{E}\right)$.

Further, since $s$ is a relation of $\widehat{\cal X}$, $\rho(s)$ is a
relation of the quotient of the coherent configuration $\widehat{{\cal X}}$
modulo $e_{0}$. Therefore, according to [7, Exercise 2.7.8(1)], we see that
the equivalence relation $e^{\prime}$ is a partial parabolic of this quotient.
It follows that $e^{*}=\rho^{-1}(e^{\prime})$ is a partial parabolic of
$\widehat{{\cal X}}$ (see [7, Theorem 3.1.11]). Clearly, every class of
$e^{*}$ is a union of some classes of $e_{0}$.

Every class of $e_{2}$ that intersects some class $\Lambda$ of $e^{*}$ must
coincide with $\Lambda$ by virtue of Eq. (3). To complete the proof, put
$\overline{e}=e^{*}\setminus e_{2}$ and define a binary relation

$s_{1}=\\{\left((\alpha,\beta),(\alpha^{\prime},\beta^{\prime})\right)\in(E\cup\overline{E})^{2}:\
\left((\alpha,\alpha^{\prime}),(\alpha,\beta)\right)\in\overline{e}\\},$

It is easily seen that
$s_{1}=(\overline{e}\cap\operatorname{cyl}_{1_{\Omega}}(1,1))\cdot\operatorname{cyl}_{1_{\Omega}}(2,1)$
and hence $s_{1}$ is a relation of $\widehat{{\cal X}}$. By the above, a class
$\Lambda$ of $e^{*}$ belongs to $e_{2}$ if and only if
$s_{1}\cap\Lambda^{2}=\varnothing$. Consequently,
$e_{2}=e^{*}\setminus\left(e^{*}\cdot\left(s_{1}\cap e^{*}\right)\cdot
e^{*}\right)$, which implies that $e_{2}$ is a partial parabolic of
$\widehat{{\cal X}}$. ∎

######  Theorem 5.2.

Let $X$ be a uniquely orientable graph. Then for all $\mathbf{e}\in E$ and
$\mathbf{f}\in\overline{E}$ the coherent configuration $\widehat{{\cal
X}}_{\mathbf{e},\mathbf{f}}$ is discrete.

###### Proof.

Choose an arbitrary $\mathbf{e}\in E$ and show that
$I(\mathbf{e})^{\partial}=\\{(\alpha^{\partial},\beta^{\partial})\mid(\alpha,\beta)\in
I(\mathbf{e})\\}$ is a relation of $\widehat{{\cal X}}_{\mathbf{e}}$ (the case
$\mathbf{e}\in\overline{E}$ is similar, as the graph $\overline{X}$ is also
uniquely orientable). Since $I(\mathbf{e})$ and $I(\mathbf{e})^{*}$ are the
only transitive orientations of $X$, the partial parabolic $e_{1}$ of
$\widehat{\cal X}$, defined in Lemma 5.1, has the set of classes
$\Omega^{2}/e_{1}=\\{I(\mathbf{e}),I(\mathbf{e})^{*}\\}$. It follows that
$I(\mathbf{e})$, which is the neighborhood of $\mathbf{e}$ in $e_{1}$, is a
homogeneity set of $\widehat{{\cal X}}_{\mathbf{e}}$ (see [7, Lemma 3.3.5]).
Since $\Delta:=\operatorname{Diag}{(\Omega^{2})}$ is a homogeneity set of
$\widehat{{\cal X}}$,

$s_{1}=(\Delta\times
I(\mathbf{e}))\cap\operatorname{cyl}_{1_{\Omega}}(1,1)\quad\text{and}\quad
s_{2}=(I(\mathbf{e})\times\Delta)\cap\operatorname{cyl}_{1_{\Omega}}(2,2)$

are relations of $\widehat{{\cal X}}_{\mathbf{e}}$. Hence $s_{1}\cdot
s_{2}=\\{(\alpha^{\partial},\beta^{\partial})\mid(\alpha,\beta)\in
I(\mathbf{e})\\}$ is a relation of $\widehat{{\cal X}}_{\mathbf{e}}$, as
required.

Let $\mathbf{e}\in E$ and $\mathbf{f}\in\overline{E}$. By the above,
$I(\mathbf{e})^{\partial}\cup I(\mathbf{f})^{\partial}$ is a relation of
$\widehat{{\cal X}}_{\mathbf{e},\mathbf{f}}$, as the set of relations of
$\widehat{{\cal X}}_{\mathbf{e},\mathbf{f}}$ includes the relations of both
$\widehat{{\cal X}}_{\mathbf{e}}$ and $\widehat{{\cal X}}_{\mathbf{f}}$.
Furthermore, by Lemma 2.2, it is a transitive tournament on $\Delta$.
Therefore, by Lemma 3.1, the restriction of $\widehat{{\cal
X}}_{\mathbf{e},\mathbf{f}}$ to $\Delta$ is discrete, and so is
$\widehat{{\cal X}}_{\mathbf{e},\mathbf{f}}$. The theorem is proved. ∎

######  Proposition 5.3.

The separability number of a uniquely orientable graph is at most $6$.

###### Proof.

Let $X$ be a uniquely orientable graph and ${\cal
X}=\operatorname{\mathsf{WL}}{(X)}$. By Theorem 5.2, a $2$-point extension of
$\widehat{{\cal X}}$ is a discrete coherent configuration. Hence, by Theorem
[10, Theorem 4.6(1)], the separability number of $\widehat{{\cal X}}$ is at
most $3$. Finally, by Theorem [10, Theorem 4.6(3)], the separability number of
${{\cal X}}$ is at most $2\cdot 3=6$. ∎

##  6\. Proof of Theorem 1.1

We follow the notation from Section 5. Let $X$ be a permutation graph. By [7,
Corollary 4.6.24], it suffices to verify that the separability number of the
coherent configuration ${\cal X}=\operatorname{\mathsf{WL}}{(X)}$ is at most
6. If $X$ is uniquely orientable, then the result follows from Proposition
5.3. Suppose that $X$ is not uniquely orientable. Let $\psi\colon{\cal
X}\to{\cal X}^{\prime}$ be a 6-isomorphism. Then $\psi$ has the $2$-extension
$\widehat{\psi}$. We will need the following lemma.

######  Lemma 6.1.

Assume that $X$ is not uniquely orientable. Then it is a non-trivial
composition graph with respect to an equivalence relation $e$ such that
$e^{\partial}$ is a partial parabolic of the coherent configuration
$\widehat{{\cal X}}$.

###### Proof.

If $X$ is reducible, the result follows from Lemmas 2.4 (with $e$ being either
the $0$\- or $1$-equivalence) and 3.2. Hence, in what follows, we assume that
$X$ is irreducible. Then $X$ is a non-trivial composition graph as defined in
Lemma 2.8, and let $e$ denote the equivalence relation $\sim$ (see the
paragraph before Lemma 2.7).

Let $e_{2}$ denote the partial parabolic of $\widehat{{\cal X}}$ as defined in
Lemma 5.1, and $\Lambda$ the support of $e_{2}$. Denote by $s$ a relation on
$\Lambda\times\operatorname{Diag}{(\Omega^{2})}$ such that two points are in
$s$ if their first or second coordinates are equal, i.e.,

$s=\left(\Lambda\times\operatorname{Diag}{(\Omega^{2})}\right)\cap\left(\operatorname{cyl}_{1_{\Omega}}(1,1)\cup\operatorname{cyl}_{1_{\Omega}}(2,2)\right).$

Then the transitive closure $t$ of $s^{*}\cdot s$ (which is obviously
reflexive and symmetric) is a partial parabolic of $\widehat{{\cal
X}}_{\operatorname{Diag}{(\Omega^{2})}}$. By the definition of $e_{2}$, the
classes of $t$ coincide with $\Delta^{\partial}$, where $\Delta$ runs over the
non-singleton classes of $e$. Thus, $e^{\partial}=t\cup
1_{\operatorname{Diag}{(\Omega^{2})\setminus T}}$, where $T$ is the support of
$t$. Since $T$ is a homogeneity set, $e^{\partial}$ is a partial parabolic of
$\widehat{\cal X}$. The lemma is proved. ∎

Let $e$ be the equivalence relation as defined in Lemma 6.1. By induction, we
may assume that the coherent configuration
$\operatorname{\mathsf{WL}}{(X_{0})}$, where $X_{0}$ is the quotient graph of
$X$ modulo $e$, and the coherent configurations
$\operatorname{\mathsf{WL}}{(X_{\Delta})}$, $\Delta\in\Omega/e$, are all
6-separable.

Put $\widehat{e}=e^{\partial}$. Then ${\cal X}^{\prime}$ coincides with the
image of $\widehat{\psi}({\cal X}^{\partial})$ under the bijection
$\partial^{\prime}\colon(\alpha^{\prime},\alpha^{\prime})\mapsto\alpha^{\prime}$,
$\alpha^{\prime}\in\Omega^{\prime}$. It follows that $\widehat{\psi}$ induces
an algebraic isomorphism $\varphi\colon{\cal X}_{e}\to{\cal
X}^{\prime}_{e^{\prime}}$ where
$e^{\prime}=(\widehat{\psi}(\widehat{e}))^{\partial^{\prime}}$, and such that

(4) $\varphi(s)=\psi(s)\mbox{~{}for all~{}}s\in S({\cal X}).$

Therefore, ${\cal X}$, ${\cal X}^{\prime}$ and $\varphi$ satisfy the
hypothesis of Theorem 4.2. Hence there exist the algebraic isomorphisms
$\varphi_{\Delta,\Delta^{\prime}}$ and $\varphi_{0}$ as defined in Theorem
4.2(ii) and (iii). Further, by Theorem 4.3(ii), they are $6$-isomorphisms.
Since $\operatorname{\mathsf{WL}}{(X_{0})}$ and
$\operatorname{\mathsf{WL}}{(X_{\Delta})}$, for all $\Delta\in\Omega/e$, are
6-separable, $\varphi_{0}$ and all $\varphi_{\Delta,\Delta^{\prime}}$ are
induced by isomorphisms. Thus, by Theorem 4.3(i), $\varphi$ is also induced by
isomorphism. By Eq. (4), it follows that $\psi$ is induced by isomorphism,
whence ${\cal X}$ is 6-separable.

## References

  * [1] V. Arvind, J. Köbler, G. Rattan, and O. Verbitsky, _Graph isomorphism, color refinement, and compactness_ , Computational Complexity 26 (2017), no. 3, 627–685.
  * [2] A. Atserias and E.N. Maneva, _Sherali-Adams relaxations and indistinguishability in counting logics_ , SIAM J. Comput. 42(1) (2013), 112–137.
  * [3] L. Babai, _Group, graphs, algorithms: the graph isomorphism problem_ , Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018\. Vol. IV. Invited lectures, World Sci. Publ., 2015, pp. 3319–3336.
  * [4] by same author, _Graph isomorphism in quasipolynomial time [extended abstract]_ , Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016, pp. 684–697.
  * [5] K.A. Baker, P.C. Fishburn, and F.S. Roberts, _Partial orders of dimension 2_ , Networks 2 (1971), 11–28.
  * [6] J.-Y. Cai, M. Fürer, and N. Immerman, _An optimal lower bound on the number of variables for graph identification_ , Combinatorica 12 (1992), no. 4, 389–410.
  * [7] 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.
  * [8] C.J. Colbourn, _On testing isomorphism of permutation graphs_ , Networks 11 (1981), no. 1, 13–21.
  * [9] Conference, _Algebraic Graph Theory, Symmetry vs Regularity. the first 50 years since Weisfeiler-Leman stabilization_ , July 1 - July 7, 2018, Pilsen, Czech Republic; https://www.iti.zcu.cz/wl2018/index.html.
  * [10] S. Evdokimov and I. Ponomarenko, _Separability number and schurity number of coherent configurations_ , Electronic J. Combin. 7 (2000), no. R31.
  * [11] S. Evdokimov, I. Ponomarenko, and G. Tinhofer, _Forestal algebras and algebraic forests (on a new class of weakly compact graphs)_ , Discrete Mathematics 225 (2000), no. 1–3, 149–172.
  * [12] 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.
  * [13] T. Gallai, _Transitiv orientierbare graphen_ , Acta Mathematica Academiae Scientiarum Hungarica 18 (1967), no. 1, 25–66.
  * [14] A. L. Gavrilyuk, R. Nedela, and I. Ponomarenko, _The Weisfeiler-Leman dimension of distance-hereditary graphs_ , arXiv (2020), https://arxiv.org/abs/2005.11766.
  * [15] M. C. Golumbic, _Algorithmic graph theory and perfect graphs_ , Annals of Discrete Mathematics, vol. 57, Elsevier, 2004.
  * [16] M. Grohe, _Fixed-point definability and polynomial time on graphs with excluded minors_ , Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science (LICS), 2010, pp. 179–188.
  * [17] by same author, _Descriptive complexity, canonisation and definable graph structure theory_ , Cambridge University Press, 2017.
  * [18] M. Grohe and S. Kiefer, _A linear upper bound on the Weisfeiler-Leman dimension of graphs of bounded genus_ , Proc. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Dagstühl Publishing, 2019, pp. 117:1–117:15.
  * [19] M. Grohe and D. Neuen, _Canonisation and definability for graphs of bounded rank width_ , Proc. 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2019, pp. 1–13.
  * [20] M. Grohe and M. Otto, _Pebble games and linear equations_ , CSL, LIPIcs, vol. 16, 2012, pp. 289–304.
  * [21] B. Grußien, _Capturing polynomial time using modular decomposition_ , Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017, pp. 1–12.
  * [22] N. Immerman and E. Lander, _Describing graphs: A first-order approach to graph canonization_ , Complexity Theory Retrospective (A. Selman, ed.), Springer-Verlag, 1990, pp. 59–81.
  * [23] S. Kiefer, I. Ponomarenko, and P. Schweitzer, _The Weisfeiler-Leman dimension of planar graphs is at most 3_ , J. ACM 66 (2019), no. 6, Article 44.
  * [24] A. Pnueli, A. Lempel, and S. Even, _Transitive orientation of graphs and identification of permutation graphs_ , Canadian Journal of Mathematics 23 (1971), no. 1, 160–175.
  * [25] I. Ponomarenko and G. Ryabov, _The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw_ , Graphs and Combinatorics 37 (2021), 1089–1102.
  * [26] J. Spinrad, _On comparability and permutation graphs_ , SIAM J. Comput. 14 (1985), 658–670.
  * [27] B. Weisfeiler and A. Leman, _The reduction of a graph to canonical form and the algebra which appears therein_ , Nauchno-Technicheskaya Informatsia 2(9) (1968), 12–16.


# THE TRANSPORT OF SELF-PROPELLED ELLIPSOIDAL PARTICLES CONFINED IN $2D$
SMOOTH CORRUGATED CHANNEL

BING WANG  School of Mechanics and Optoelectronic Physics, Anhui University of
Science and Technology
Huainan, 232001, P.R.China
<EMAIL_ADDRESS>WENFEI WU  School of Mechanics and Optoelectronic Physics,
Anhui University of Science and Technology
Huainan, 232001, P.R.China

(Day Month Year; Day Month Year)

###### Abstract

Directed transport of self-propelled ellipsoidal particles confined in a
smooth corrugated channel with asymmetric potential and Gaussian colored noise
is investigated. Effects of the channel, potential and colored noise on the
system are discussed. Large $x$ axis noise intensity inhibits the transport in
$-x$ and $+x$ direction. The directed transport speed $|\langle V\rangle|$ has
a maximum with increasing $y$ axis noise intensity. Proper size of the
bottleneck is good for the directed transport of the ellipsoidal particles,
but large and small size of bottleneck inhibits this directed transport. The
transport reverse phenomenon appears with increasing load and self-propelled
speed. Perfect sphere particle is easier to directed transport than needlelike
ellipsoid particle.

###### keywords:

Self-Propelled Ellipsoidal Particle; Confined Channel; Directed Transport.

##  1 Introduction

Recent years, we have seen enormous activities in the study of the properties
of the confined Brownian particles. These studies, both theoretical and
experimental, revealed that there are two ways of confinement fundamentally
effect a system. One way is by regulating the transport space accessible to
its diffusing components[1], and the other way is by increasing the
hydrodynamic drag on the particles[2]. There exists a large number of natural
and artificial confined geometries, e.g., biological cells[3, 4, 5, 6],
zeolites[7], artificial nanopores[8, 9], ionpumps[10, 11, 12, 13] and micro
fluidic devices[14, 15, 16, 17].

Confined particle shows a series of novel features, e.g. current reversal[18,
19, 20, 21, 22], self-organization[23, 24], geometry-induced stochastic
resonance phenomenon[25, 26] and so on. Hänggi _et al_. proposed a model of
asymmetry particles confined in a compartmentalized channel and found the
absolute negative mobility[27]. Ghosh _et al_. investigated directed transport
of suspended particles and found inertial corrections must be considered when
the width of the bottlenecks is smaller than an appropriate particle diffusion
length[28]. Using the hybrid molecular dynamics method, Chen _et al_. studied
the properties of self-propelled synthetic motors[29]. Pu _et al_.
investigated the reentrant phase separation behavior of active particles and
found that phase separation shows a re-entrance behavior with variation of the
interaction strength[30]. Li _et al_. found non-Gaussian normal diffusion
phenomenon of Brownian particles floating in a narrow corrugated channel with
fluctuating cross section[31]. Yang _et al_. experimentally investigated the
diffusion of particles moving in a planar channel[32].

In many biological systems, transport particles are often nonspherical, such
as proteins diffusing in membranes and fine grains migrating through the pores
of micro media[34, 33]. Han _et al_. studied the transport of ellipsoid
particles confined in a two dimensional channel and quantified the crossover
from short-time anisotropic to long-time isotropic diffusion[35]. Ohta _et
al_. found deformable particles exhibit bifurcation and circular motion
phenomenon[36]. Ai _et al_. investigated the rectified transport of active
ellipsoidal particles in a two-dimensional asymmetric potential[37]. Ghosh _et
al_. numerically simulated the transport of elliptic particles confined in
two-dimensional channels with reflecting walls and observed long diffusion
transients[38]. Traditionally, stochastic differential equations used in
physical and biological science have involved Gaussian white noise.
Investigation of laser noise problems [39, 40], bistable systems[41] and self-
propelled particle systems[42, 43] found that it is necessary to consider
colored noise in those systems.

In this paper, we investigate the directed transport of self-propelled
ellipsoidal Brownian particles confined in a two dimensional($2D$) smooth
channel. The paper is organized as follows: The basic model of the system is
provided in Sect.2. In Sect.3, the effects of the channel, the potential and
the colored noise on the ellipsoidal particles are investigated by means of
simulations. In Sect. 4, we get the conclusions.

##  2 Basic model and methods

In this work, we consider self-propelled ellipsoidal particles confined in a
$2D$ smooth corrugated channel with potential and Gaussian colored noise. In
the lab frame, the displacement $\delta\vec{R}(t)$ of the particle can be
described by the mass center($\delta{x}$, $\delta{y}$). We use the following
Langevin equations to describe the dynamics of the particle[35, 44]

$\frac{\partial{x}}{\partial
t}=v_{0}\cos\theta(t)+F_{x}[\bar{\Gamma}+\Delta\Gamma\cos
2\theta(t)]+\Delta\Gamma F_{y}\sin 2\theta(t)+\xi_{x}(t),$ (1)

$\frac{\partial{y}}{\partial
t}=v_{0}\sin\theta(t)+F_{y}[\bar{\Gamma}-\Delta\Gamma\cos
2\theta(t)]+\Delta\Gamma F_{x}\sin 2\theta(t)+\xi_{y}(t),$ (2)

$\frac{\partial{\theta(t)}}{\partial t}={\xi}_{\theta}(t).$ (3)

The angle between the lab frame $x$ axis and the body frame $\hat{x}$ axis is
$\theta(t)$. The self-propelled velocity is $v_{0}$, and $v_{0}$ is along the
long axis of the particle. The quantities
$\bar{\Gamma}=\frac{1}{2}(\Gamma_{x}+\Gamma_{y})$ and
$\Delta{\Gamma}=\frac{1}{2}(\Gamma_{x}-\Gamma_{y})$ are the average and
difference mobilities of the body, respectively. The mobilities along its long
axis and short axis are $\Gamma_{x}$ and $\Gamma_{y}$, respectively.
$\Delta\Gamma$ determines the asymmetry of the body of the ellipsoidal
particle. The particle is a perfect sphere when $\Delta\Gamma=0$ and a very
needlelike ellipsoid when $\Delta\Gamma\rightarrow\bar{\Gamma}$. $\xi_{x}$,
$\xi_{y}$ and $\xi_{\theta}$ are the noises. $\xi_{x}$ and $\xi_{y}$ parallel
to $x$ axis and $y$ axis, respectively. $\xi_{\theta}$ is the angle noise.
$\xi_{x}$, $\xi_{y}$ and $\xi_{\theta}$ satisfy the following relations,

$\langle\xi_{i}(t)\rangle=0,(i=x,y,\theta),$ (4)
$\langle\xi_{i}(t)\xi_{j}(t^{\prime})\rangle=\delta_{ij}\frac{Q_{i}}{\tau_{i}}\exp[-\frac{|t-t^{\prime}|}{\tau_{i}}],(i=x,y,\theta),$
(5)

where $Q_{i}$ and $\tau_{i}$ are the noise intensity and the self-correlation
time of the noises, respectively.

Figure 1: Illustrations of the smooth corrugated channel with $\Delta=0.8$,
$x_{L}=y_{L}=1.0$, $\eta=2.0$.

The particles are confined in a two dimensional smooth corrugated channel. As
shown in Fig.1, the channel is consisted of many cavities and is periodic in
spatial along the $x$-axis. The walls of the cavity are modeled by the
following sinusoidal functions,[45]

$W_{+}(x)=\frac{1}{2}[\Delta+(y_{L}-\Delta)\sin^{\eta}(\frac{\pi x}{x_{L}})],$
(6) $W_{-}(x)=-\frac{1}{2}[\Delta+(y_{L}-\Delta)\sin^{\eta}(\frac{\pi
x}{x_{L}})],$ (7)

where $x_{L}=1.0$ and $y_{L}=1.0$ are the length and width of the cavity,
respectively. The additional tunable geometric parameter is $\eta$. The cavity
represents the compartment of sinusoidally corrugated channel when $\eta=2$.
When $\eta\rightarrow 0$, the cavity reproduces the compartment of sharply
corrugated channels. The channel width is $h(x)=W_{+}-W_{-}$. The minimal
channel width(the bottleneck) is $h_{min}=h(x)|_{x=\pm
k,k=0,1,2,\cdot\cdot\cdot}=\Delta$, and through which the particles can exit
the cavity. The maximal channel width is
$h_{max}=h(x)|_{x=\pm(2k+1)\frac{1}{2},k=0,1,2,\cdot\cdot\cdot}=y_{L}$.

Figure 2: The asymmetric potential $U(x,y)$ with $U_{0}=1.0$,
$\varepsilon=0.5$:(a)3D view with $f=-0.3$;(b)Front view with $f=-0.3$; (c)3D
view with $f=0.3$; (d)Front view with $f=0.3$.

The asymmetric potential is described by the following equation[37](shown in
Fig.8),

$U(x,y)=\frac{U_{0}}{2}y^{2}[\cos(x+\varepsilon\ln{\cosh y})+1.1]+fx,$ (8)

where $U_{0}$ is the height of the potential, and $f$ is the load. The
asymmetric parameter of the potential is $\varepsilon$, and the potential is
symmetric for $\varepsilon=0.0$. The equipotential is look like a herringbone
pattern if $\varepsilon\neq 0$. The forces $F_{x}=-\frac{\partial U}{\partial
x}$ and $F_{y}=-\frac{\partial U}{\partial y}$ are along $x$ and $y$
directions of the lab frame, respectively.

In the theory of Brownian motion, the central question is the particle’s over
all long time behavior. The velocity of the particle is one of the key
quantities. We only calculate the average velocity in $x$ direction because
the channel in $y$ direction is confined,

$\langle
V_{\theta_{0}}\rangle=\lim_{t\to\infty}\frac{\langle{x(t)-x(t_{0})}\rangle}{t-t_{0}},$
(9)

the position of particles at time $t_{0}$ is $x(t_{0})$. The initial angle of
the trajectory is $\theta_{0}$. The full average velocity after another
average over all $\theta_{0}$ is

$\langle V\rangle=\frac{1}{2\pi}\int^{2\pi}_{0}\langle V_{\theta_{0}}\rangle
d\theta_{0}.$ (10)

##  3 Results and discussion

In order to give a simple and clear analysis of the system. We integrate
Eqs.(1,2,3) with time step $\Delta t=10^{-4}$ using the Euler algorithm. The
average velocity is obtained as ensemble averages over $10^{5}$ trajectories
with random initial conditions. In the simulation, we set $x_{L}=y_{L}=1.0$,
$\bar{\Gamma}=1.0$ and $U_{0}=1.0$ throughout the paper.

Figure 3: The average velocity $\langle V\rangle$ as a function of $Q_{x}$ for
different values of $f$. The other parameters are $\Delta=0.8$,
$\varepsilon=0.5$, $\eta=2.0$, $v_{0}=0.5$, $Q_{x}=Q_{y}=Q_{\theta}=1.0$,
$\tau_{x}=\tau_{y}=\tau_{\theta}=1.0$.

Fig.3 displays the average velocity $\langle V\rangle$ as a function of $x$
axis noise intensity $Q_{x}$ with different load $f$. In this paper, we find
the average velocity $\langle V\rangle>0$, and $\langle V\rangle$ decreases
with increasing $Q_{x}$ when the load $f=-0.1$ and $f=-0.3$. Which means that
negative load $f$ induces directed transport in $+x$ direction, and large $x$
axis noise intensity $Q_{x}$ inhibits this transport. When the load
$f>0$($f=0.1$ and $f=0.3$), the average velocity $\langle V\rangle<0$, and
$\langle V\rangle$ increases with increasing $Q_{x}$. So positive $f$ leads to
directed transport in $-x$ direction, and large $Q_{x}$ is bad for this
directed transport. Of cause, we can also say that the directed transport
speed $|\langle V\rangle|$($|\langle V\rangle|$ is the absolute value of
$\langle V\rangle$) decreases with increasing $Q_{x}$, so large $x$ axis noise
intensity inhabits directed transport along $x$ axis.

Figure 4: The average velocity $\langle V\rangle$ as a function of $\tau_{x}$
for different values of $f$. The other parameters are $\Delta=0.8$,
$\varepsilon=0.5$, $\eta=2.0$, $v_{0}=0.5$, $Q_{x}=Q_{y}=Q_{\theta}=1.0$,
$\tau_{y}=\tau_{\theta}=1.0$.

Fig.4 displays $\langle V\rangle$ as a function of self-correlation time
$\tau_{x}$ with different load $f$. In this figure, comparing with the effect
of $Q_{x}$ in Fig.3, we find $\tau_{x}$ has exactly reverse effect on the
system. The directed transport speed $|\langle V\rangle|$ increases with
increasing $\tau_{x}$. Large self-correlation time $\tau_{x}$ is good for the
transport. In this figure, we can also find negative $f$ induces directed
transport in $+x$ direction, but positive $f$ induces directed transport in
$-x$ direction. From Figs. 3 and 4, we find the slopes of $\langle V\rangle-
Q_{x}$ and $\langle V\rangle-\tau_{x}$ curves almost changes to zero when
$Q_{x}$ and $\tau_{x}$ are large. So changes of $Q_{x}$ and $\tau_{x}$ have
weak impact on the transport when their values are large.

Figure 5: The average velocity $\langle V\rangle$ as a function of $Q_{y}$ for
different values of $f$. The other parameters are $\Delta=0.8$,
$\varepsilon=0.5$, $\eta=2.0$, $v_{0}=0.5$, $Q_{x}=Q_{\theta}=1.0$,
$\tau_{x}=\tau_{y}=\tau_{\theta}=1.0$.

Fig.5 displays $\langle V\rangle$ as a function of $y$ axis noise intensity
$Q_{y}$ with different $f$. In this figure, we find the directed transport
speed $|\langle V\rangle|$ has a maximum with increasing $Q_{y}$. So proper
$y$ axis noise intensity is good for the transport in $x$ and $-x$ direction,
but too large or too small $Q_{y}$ inhabits this phenomenon. From figures 3
and 5, we find an interesting phenomenon, large $x$ axis noise intensity
inhabits the directed transport in $+x$ and $-x$ direction, but proper $y$
axis noise intensity is good for this transport.

Figure 6: The average velocity $\langle V\rangle$ as a function of $\tau_{y}$
for different values of $f$. The other parameters are $\Delta=0.8$,
$\varepsilon=0.5$, $\eta=2.0$, $v_{0}=0.5$, $Q_{x}=Q_{y}=Q_{\theta}=1.0$,
$\tau_{x}=\tau_{\theta}=1.0$.

Fig.6 displays $\langle V\rangle$ as a function of $y$ axis noise self-
correlation time $\tau_{y}$ for different $f$. Comparing with the effect of
$\tau_{x}$ in Fig.4, we find the directed transport speed $|\langle V\rangle|$
decreases with increasing $\tau_{y}$. This means that large $\tau_{y}$ has
negative effect on the transport along $x$ axis.

Figure 7: The average velocity $\langle V\rangle$ as a function of
$Q_{\theta}$ for different values of $f$. The other parameters are
$\Delta=0.8$, $\varepsilon=0.5$, $\eta=2.0$, $v_{0}=0.5$, $Q_{x}=Q_{y}=1.0$,
$\tau_{x}=\tau_{y}=\tau_{\theta}=1.0$. Figure 8: The average velocity $\langle
V\rangle$ as a function of $\tau_{\theta}$ for different values of $f$. The
other parameters are $\Delta=0.8$, $\varepsilon=0.5$, $\eta=2.0$, $v_{0}=0.5$,
$Q_{x}=Q_{y}=Q_{\theta}=1.0$, $\tau_{x}=\tau_{y}=1.0$.

Figs.7 and 8 display $\langle V\rangle$ as functions of angle noise intensity
$Q_{\theta}$ and self-correlation time $\tau_{\theta}$ for different $f$,
respectively. In these two figures, we find there exits almost no change of
$\langle V\rangle$ with increasing $Q_{\theta}$ and $\tau_{\theta}$. So the
effect of the angle noise is very weak for the transport.

Figure 9: The average velocity $\langle V\rangle$ as a function of the size of
bottleneck $\Delta$ for different values of $f$. The other parameters are
$\varepsilon=0.5$, $\eta=2.0$, $v_{0}=0.5$, $Q_{x}=Q_{y}=Q_{\theta}=1.0$,
$\tau_{x}=\tau_{y}=\tau_{\theta}=1.0$.

The average velocity $\langle V\rangle$ as a function of the bottleneck(the
minimal channel width) $\Delta$ is reported in Fig.9. We find $\langle
V\rangle\rightarrow 0$ when $\Delta\rightarrow 0$. This is because the channel
becomes many closed cavities when $\Delta\rightarrow 0$, and the particle is
confined in these cavities. The directed transport speed $|\langle V\rangle|$
increases with increasing $\Delta$, and reaches a maximum when $\Delta=1$, and
then decreases with increasing $\Delta$. So an interesting phenomena appears,
that is, large and small size of the bottleneck both restrains the directed
transport.

Figure 10: The average velocity $\langle V\rangle$ as a function of
$\Delta\Gamma$ for different values of $f$. The other parameters are
$\Delta=0.8$, $\varepsilon=0.5$, $\eta=2.0$, $v_{0}=0.5$,
$Q_{x}=Q_{y}=Q_{\theta}=1.0$, $\tau_{x}=\tau_{y}=\tau_{\theta}=1.0$.

The average velocity $\langle V\rangle$ as a function of the asymmetry of the
body $\Delta\Gamma$ for different $f$ is reported in Fig.10. We know
$\Delta\Gamma$ characterizes the asymmetry of the particle, and the particle
is a perfect sphere when $\Delta\Gamma=0$, and the particle is a very
needlelike ellipsoid when $\Delta\Gamma\rightarrow\bar{\Gamma}$. In this
figure, we find the average directed transport speed $|\langle V\rangle|$
decreases with increasing $\Delta\Gamma$. So perfect sphere particle is more
easier for directed transport than needlelike ellipsoid particle. This result
coincides with the common sense.

Figure 11: The average velocity $\langle V\rangle$ as a function of
$\varepsilon$ for different values of $f$. The other parameters are
$\Delta=0.8$, $\eta=2.0$, $v_{0}=0.5$, $Q_{x}=Q_{y}=Q_{\theta}=1.0$,
$\tau_{x}=\tau_{y}=\tau_{\theta}=1.0$.

The average velocity $\langle V\rangle$ as a function of the asymmetric
parameter $\varepsilon$ for different $f$ is reported in Fig.11. We find the
$\langle V\rangle-\varepsilon$ curve is almost horizontal, this means that the
effect of $\varepsilon$ is very weak on the directed transport phenomenon.

Figure 12: The average velocity $\langle V\rangle$ as a function of self-
propelled speed $v_{0}$ for different values of $f$. The other parameters are
$\Delta=0.8$, $\varepsilon=0.5$, $\eta=2.0$, $Q_{x}=Q_{y}=Q_{\theta}=1.0$,
$\tau_{x}=\tau_{y}=\tau_{\theta}=1.0$.

The average velocity $\langle V\rangle$ as a function of self-propelled speed
$v_{0}$ with different $f$ is reported in Fig.12. When the load is
negative($f=-0.3$ and $f=-0.1$), inert particle(self-propelled speed
$v_{0}=0$) moves in $+x$ direction($\langle V\rangle>0$), and $\langle
V\rangle$ decreases with increasing $v_{0}$, then the particles changes to
moving in $-x$ direction when $2.8<v_{0}<6.0$, and $\langle
V\rangle\rightarrow 0$ when $v_{0}=6.0$. So the transport reverse phenomenon
appears with increasing $v_{0}$. When the load is positive($f=0.1$ and
$f=0.3$), inert particle($v_{0}=0$) moves in $-x$ direction($\langle
V\rangle<0$), and the transport reverse phenomenon appears too with increasing
$v_{0}$, and $\langle V\rangle\rightarrow 0$ when $v_{0}=6.0$. In this figure,
we can also find negative load leads to directed transport in $+x$ direction
when $v_{0}<3$, but positive load leads to directed transport in $-x$
direction when $v_{0}<3$. So self-propelled speed $v_{0}$ can also influence
the moving direction of the particles.

Figure 13: The average velocity $\langle V\rangle$ as a function of load $f$
for different $\eta$. The other parameters are $\Delta=0.8$,
$\varepsilon=0.5$, $v_{0}=0.5$, $Q_{x}=Q_{y}=Q_{\theta}=1.0$,
$\tau_{x}=\tau_{y}=\tau_{\theta}=1.0$.

The average velocity $\langle V\rangle$ as a function of the load $f$ for
different $\eta$ is reported in Fig.13. We find $\langle V\rangle$ decreases
monotonically with increasing load $f$. $\langle V\rangle>0$ when $f<0$, but
$\langle V\rangle<0$ when $f>0$. This means negative load leads to positive
transport(directed transport in $-x$ direction), but positive load leads to
negative transport. Directed transport speed $|\langle V\rangle|$ increases
with increasing $|f|$, so large load $|f|$ is good for directed transport(in
$x$ direction or in $-x$ direction). We know the potential $U$ is inversely
proportional to the load $f$(Fig.8), so the particles move to the place where
potential is lower. In this figure, we can also find the smaller $\eta$, the
larger $|\langle V\rangle|$ is.

##  4 Conclusions

In this paper, we numerically investigated the directed transport of self-
propelled ellipsoidal particles confined in a smooth channel with potential
and colored noise. We find the moving direction is closely linked to the
direction of the load when the self-propelled speed is small($v_{0}<3$).
Negative load leads to directed transport in $x$ direction, but positive load
leads to directed transport in $-x$ direction. Small and large size of
bottleneck restrains the directed transport of the ellipsoidal particle. Large
$x$ axis noise intensity inhibits the directed transport. But proper value of
$y$ axis noise intensity is good for this phenomenon. The transport reverse
phenomenon appears with increasing self-propelled speed $v_{0}$. The effects
of angle noise on the system is negligible.

## Acknowledgments

Project supported by Natural Science Foundation of Anhui Province(Grant
No:1408085QA11).

## References

  * [1] P. Hänggi, F. Marchesoni, Rev. Mod. Phys. 81 387 (2009).
  * [2] P. S. Burada , P. Hänggi, F. Marchesoni, G. Schmid, P. Talkner, Chem. Phys. Chem. 10 45 (2009).
  * [3] H. X. Zhou, G. N. Rivas, A. P. Minton, Annu. Rev. Biophys. 37 375 (2008).
  * [4] Y. Wu, Q. Ding, T. Li, D. Yu, Y. Jia, Nonlinear Dynamics 111 2693 (2023).
  * [5] J. Liu, J. D. Bao, X. Chen, Phys. Rev. E 102 062122 (2020).
  * [6] R. F. Cui, Q. H. Chen, J. X Chen, Nanoscale 12 12275 (2020).
  * [7] F. J. Keil, R. Krishna, M. O. Coppens, Rev. Chem. Eng. 16 71 (2000).
  * [8] M. Firnkes, D. Pedone, J. Knezevic, M. Döblinger, U. Rant, Nano. Lett.  10 2162 (2010).
  * [9] D. Pedone, M. Langecker, G. Abstreiter, U. Rant, Nano. Lett.  11 1561 (2011).
  * [10] Z. Siwy, A. Fulinski, Am. J.Phys. 72 567 (2004).
  * [11] Z. Siwy, I. D. Kosinska, A. Fulinski, C. R. Martin, Phys. Rev. Lett. 94 048102 (2005).
  * [12] L. Bosi, P. K. Ghosh, F. Marchesoni, J. Chem. Phys. 137 174110 (2012).
  * [13] P. K. Ghosh, V. R. Misko, F. Marchesoni, F. Nori, Phys. Rev. Lett.  110 268301 (2013).
  * [14] S. Matthias, F. Müller, Nature  424 53 (2003).
  * [15] T. M. Squires, S. R. Quake, Rev. Mod. Phys.  77 977 (2005).
  * [16] R. M. Bradley, Phys. Rev. E  80 061142 (2009).
  * [17] L. Dagdug, I. Pineda, J. Chem. Phys.  137 024107 (2012).
  * [18] Y. Jia, S. N. Yu, J. R. Li, Phys. Rev. E  63 052101 (2001).
  * [19] C. Hu, Y. Ou, J. Wu, Q. Chen, B. Ai, J. Stat. Mech. 2015 05025 (2015).
  * [20] Z. Liu, L. Du, W. Guo, D. C. Mei, Eur. Phys. J. B  89 222 (2016).
  * [21] Y. Xu, Y. Jia, M. Ge, L. Lu, L. Yang, X Zhan, Neurocomputing  283 196 (2018).
  * [22] H. W. Hu, L. Du, L. H. Qu, Z. L. Cao, Z. C. Deng , Y. C. Lai, Phys. Rev. Research 3 033162 (2021).
  * [23] J. Richardi, M. P. Pileni, J. J. Weis, J. Chem. Phys.  130 124515 (2009).
  * [24] Z. Yoshida, H. Saitoh, J. Morikawa, Y. Yano, S. Watanabe, Y. Ogawa, Phys. Rev. Lett. 104 235004 (2010).
  * [25] P. K. Ghosh, F. Marchesoni, S. E. Savelev and F. Nori, Phys. Rev. Lett. 104 020601 (2010).
  * [26] P. K. Ghosh, R. Glavey, F. Marchesoni, S. E. Savelev, F. Nori, Phys. Rev. E 84 011109 (2011).
  * [27] P. Hänggi, F. Marchesoni, S. Savelev, G. Schmid, Phys. Rev. E  82 041121 (2010).
  * [28] P. K. Ghosh, P. Hänggi, F. Marchesoni, F. Nori, G. Schmid, Phys. Rev. E  86 021112 (2012).
  * [29] J. X. Chen,Y. G. Chen, R. Kapral, Advanced Science 1800028 (2018).
  * [30] M. Pu, H. Jiang , Z. Hou, Soft Matter  13 4112 (2017).
  * [31] Y. Li, F. Marchesoni, D. Debnath, P. K. Ghosh, Phys. Rev. Res. 1 033003 (2019).
  * [32] X. Yang, Q. Zhu, C. Liu, W. Wang, Y. Li, F. Marchesoni, P. Hänggi, H. P. Zhang, Phys. Rev. E  99 020601(R) (2019).
  * [33] P. G. Saffman, M. Delbruck, Proc. Natl. Acad. Sci. U.S.A. 72 3111 (1975).
  * [34] F. Lugli, E. Brini, F. Zerbetto, J. Chem. Phys. C  116 592 (2012).
  * [35] Y. Han, A. M. Alsayed, M. Nobili, J. Zhang, T. C. Lubensky, A. G. Yodh, Science 314 626 (2006).
  * [36] T. Ohta, T. Ohkuma, Phys. Rev. Lett. 102 154101 (2009).
  * [37] B. Ai, J. Wu, J. Chem. Phys.  140 094103 (2014).
  * [38] P. K. Ghosh, P. Hänggi, F. Marchesoni, F. Nori, Phys. Rev. E  89 062115 (2014).
  * [39] S. Zhu, A. W. Yu, R. Roy, Phys. Rev. A 34 4333 (1986).
  * [40] X. Zhou, Phys. Rev. A 80 023818 (2009).
  * [41] K. Y. R. Billah, M. Shinozuka, Phys. Rev. A 42 7492 (1990).
  * [42] R. Wittmann, J. M. Brader, A. Sharma, U. Marini Bettolo Marconi, Phys. Rev. E 97 012601 (2018).
  * [43] S. Mondal, B. C. Bag, Phys. Rev. E 91 042145 (2015).
  * [44] R. Grima, S. N. Yaliraki, and M. Barahona,J. Phys. Chem. B 114 5380 (2010).
  * [45] P. K. Ghosh, J. Chem. Phys. 141 061102 (2014).