% A LaTeX2e file for a 32 page document
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}
\def\A{{\cal A}}
\def\aut{\mathop{\rm Aut}\nolimits}
\def\C{{\mathbb C}}
\def\CC{{\cal C}}
\def\cel{\mathop{\rm Cel}\nolimits}
\def\D{{\cal D}}
\def\dim{\mathop{\rm dim}\nolimits}
\def\E{{\cal E}}
\def\Emb{\mathop{\rm Emb}\nolimits}
\def\F{\mathbb F}
\def\G{\Gamma}
\def\H{{\cal H}}
\def\id{\mathop{\rm id}\nolimits}
\def\isow{\mathop{\rm Isow}\nolimits}
\def\J{{\cal J}}
\def\K{{\cal K}}
\def\KG{{\cal K}}
\def\L{{\widehat L}}
\def\LG{{\cal L}}
\def\M{{\cal M}}
\def\Mat{\mathop{\rm Mat}\nolimits}
\def\m{{(m)}}
\def\orb{\mathop{\rm Orb}\nolimits}
\def\ov{\overline}
\def\P{{\cal P }}
\def\pr{\mathop{\rm pr}\nolimits}
\def\R{{\cal R}}
\def\RR{{\widehat\R}}
\def\S{{\cal S}}
\def\sym{\mathop{\rm Sym}\nolimits}
\def\WP{\widehat{W'}}
\def\W{{\widehat W}}
\def\wh{\widehat}
\def\wt{\widetilde}
\def\Z{{\cal Z}}
\def\ZZ{{\mathbb Z}}
\def\proof{{\bf Proof}.\ }
\def\bull{\vrule height .9ex width .8ex depth -.1ex }
\def\SuSS{\stepcounter{subsection}{\bf\thesubsection{.}}
\addtocounter{subsection}{-1}\refstepcounter{subsection}}
\def\eSuSS{\vspace{2mm}\SuSS}
\newtheorem{formula}{}[section]
\newtheorem{proposition}[formula]{Proposition}
\newtheorem{definition}[formula]{Definition}
\newtheorem{corollary}[formula]{Corollary}
\newtheorem{remark}[formula]{Remark}
\newtheorem{lemma}[formula]{Lemma}
\newtheorem{theorem}[formula]{Theorem}
\newtheorem{problem}[formula]{Problem}
\newtheorem{hypothesis}[formula]{Hypothesis}
\def\thrm{\begin{theorem}}
\def\thrml#1{\begin{theorem}\label{#1}}
\def\ethrm{\end{theorem}}
\def\prpstn{\begin{proposition}}
\def\prpstnl#1{\begin{proposition}\label{#1}}
\def\eprpstn{\end{proposition}}
\def\rmrk{\begin{remark}}
\def\rmrkl#1{\begin{remark}\label{#1}}
\def\ermrk{\end{remark}}
\def\dfntn{\begin{definition}}
\def\dfntnl#1{\begin{definition}\label{#1}}
\def\edfntn{\end{definition}}
\def\nmrt{\begin{enumerate}}
\def\enmrt{\end{enumerate}}
\def\tm#1{\item[{\rm (#1)}]}
\def\qtn{\begin{equation}}
\def\qtnl#1{\begin{equation}\label{#1}}
\def\eqtn{\end{equation}}
\def\lmm{\begin{lemma}}
\def\lmml#1{\begin{lemma}\label{#1}}
\def\elmm{\end{lemma}}
\def\crllr{\begin{corollary}}
\def\crllrl#1{\begin{corollary}\label{#1}}
\def\ecrllr{\end{corollary}}
\textwidth=6.5in %176mm
%\textwidth=6in
\textheight=8.5in
\evensidemargin=0in
\oddsidemargin=\evensidemargin
\sloppy
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7}
(2000),
\#R31\hfill}
\thispagestyle{empty}
\begin{document}
\title{Separability Number and Schurity Number\\ of Coherent
Configurations}
\author{
Sergei Evdokimov\\
St. Petersburg Institute for Informatics and Automation \\
{\small\texttt{evdokim@pdmi.ras.ru}}
\thanks{Partially supported by RFFI, grant 96-15-96060}
\and
Ilia Ponomarenko\\
Steklov Institute of Mathematics at St. Petersburg \\
{\small\texttt{inp@pdmi.ras.ru}}
\thanks{Partially supported by RFFI, grants 96-15-96060, 99-01-00098}
\and
Submitted: January 26, 2000; Accepted: May 17, 2000
}
\date{}
\maketitle
\begin{abstract}
To each coherent configuration (scheme) $\CC$ and positive
integer~$m$
we associate a natural scheme~$\wh\CC^\m$ on the $m$-fold Cartesian
product of the point set of~$\CC$ having the same automorphism
group as~$\CC$. Using this construction we define and study two
positive integers: the separability number~$s(\CC)$ and the Schurity
number~$t(\CC)$ of~$\CC$. It turns out that
$s(\CC)\le m$ iff $\CC$ is uniquely determined up to isomorphism
by the intersection numbers of the scheme~$\wh\CC^\m$. Similarly,
$t(\CC)\le m$ iff the diagonal subscheme of~$\wh\CC^\m$ is an orbital
one.
In particular, if $\CC$ is the scheme of a distance-regular
graph~$\G$,
then $s(\CC)=1$ iff $\G$ is uniquely determined by its parameters
whereas $t(\CC)=1$ iff $\G$ is distance-transitive. We show that
if~$\CC$ is a Johnson, Hamming or Grassmann scheme, then $s(\CC)\le
2$
and $t(\CC)=1$. Moreover, we find the exact values of $s(\CC)$ and
$t(\CC)$ for the scheme~$\CC$ associated with any distance-regular
graph
having the same parameters as some Johnson or Hamming graph. In
particular, $s(\CC)=t(\CC)=2$ if~$\CC$ is the scheme of a Doob graph.
In addition, we prove that $s(\CC)\le 2$ and $t(\CC)\le 2$ for any
imprimitive 3/2-homogeneous scheme. Finally, we show that $s(\CC)\le
4$,
whenever~$\CC$ is a cyclotomic scheme on a prime number of points.
\end{abstract}
\section{Introduction}
The purpose of this paper is to continue the investigations of
distance-regular graphs~\cite{BCN} and more generally association
schemes~\cite{BI} from the point of view of their isomorphisms and
symmetries, started by the authors in~\cite{EKP}, \cite{EP},
\cite{EPL}. We have tried to make this paper self-contained but
nevertheless
some knowledge of basic algebraic combinatorics in the spirit of the
books by Brouwer-Cohen-Neumaier and Bannai-Ito cited above will be
helpful.
The starting point of the paper is the following
two interconnected questions
arising in different fields of combinatorial mathematics
such as association scheme theory, graph theory and so forth.
The first of them is the problem of finding parameters of
an association scheme or a graph determining it up to isomorphism.
The second one reflects the desire to reveal a canonical
group-like object in a class of schemes or graphs with the
same automorphism group or, in other words, to reconstruct such an
object
without finding the last groups explicitly. We will return to these
questions a
bit later after choosing a suitable language. In this connection
we remark that the language of association schemes
is not sufficiently general because it weakly reflects the fact
that the automorphism group of a scheme can have several orbits
whereas the language of graphs is too amorphic because almost nothing
can be said on invariants and symmetries of general graphs.
On the other hand, the language of permutation groups is too
restrictive
in the sense that there is a variety of interesting combinatorial
objects
which are not explicitly connected with any group. We choose
the language of coherent configurations (or schemes) introduced by
D.~G.~Higman in~\cite{H70} and under a different name
independently by B.~Yu.~Weisfeiler and A.~A.~Leman
in~\cite{WL}. The exact definition will be given in
Subsection~\ref{ccaca}
and here we say only that all mentioned above objects can be
considered as special cases of coherent configurations.
Nowadays, the general theory of coherent configurations is far from
being completed (see, however, \cite[Chapter 3]{Ca} and \cite{FKM}).
The present paper continues the investigations of the authors in
this direction (see \cite{EKP}-\cite{EPT}).
Probably one of the first results on the characterization of a scheme
by
its parameters was the paper \cite{S59} where it was proved that
any strongly regular graph with parameters of some Hamming graph
of diameter 2 and different from it is the Shrikhande graph. This
result
in particular shows that the parameters of a strongly regular graph
do not necessarily determine it up to isomorphism. One more example
of such a situation arises in \cite{Hi70} where some families
of rank 3 graphs were characterized by means of the valency and the
so
called $t$-vertex condition (see Subsection~\ref{tvetc}).
Further investigations in this
direction led to characterizing some classical families
of distance-regular graphs (see \cite[Chapter 9]{BCN}). However only
a few
of these characterizations are formulated in terms of the
intersection
numbers of the corresponding schemes. For example, in the case of
Grassmann graphs some additional information concerning the local
structure of a graph is needed. This and similar examples indicate
the absence of a unified approach to characterizing schemes. (In
\cite{BI} it was suggested in a nonformal way to differ
characterizations
by spectrum, parameters and local structure.) One of the purposes
of this paper is to present a new invariant of an arbitrary scheme,
its separability number, on which depends how many parameters are
sufficient to characterize it. In addition, we compute this number
for classical and some other schemes.
The above discussion reveals a close relationship between the problem
of characterizing schemes and the graph isomorphism problem
which is one of the most famous unsolved problems in computational
complexity theory. This problem consists in finding an efficient
algorithm to test the isomorphism of two graphs (see~\cite{B}). As
it was found in \cite{WL} it is polynomial-time equivalent to the
problem
of finding the scheme consisting of 2-orbits of the automorphism
group
of a given scheme. Just the last scheme can be chosen as a canonical
group-like object in the class of all schemes having the same
automorphism group.
In particular, if any scheme was obtained in such a way from its
automorphism group, then the graph isomorphism problem would become
trivial.
However this is not the case and one of the counterexamples is
the scheme of the Shrikhande graph which is a strongly regular but
not
rank 3 graph. To resolve this collision several ways based on higher
dimensional constructions were suggested.
Here we mention only the algorithms of deep stabilization
from \cite{W}, the so called $m$-dim Weisfeiler-Leman method
associated with
them (see \cite{B}) and a general concept of such procedures
from~\cite{EKP}.
The analysis of these ideas enabled us to introduce in this paper a
new
invariant of a scheme, its Schurity number, which is responsible
for the minimal dimension of the construction for which the
corresponding
2-orbit scheme arises as the diagonal subscheme of it.
Before presenting the main results of the paper we pass from
the combinatorial language of schemes to a more algebraic (but
equivalent) language of cellular algebras introduced in~\cite{WL}
(as to exact definitions see Subsection~\ref{ccaca}).
They are by definition matrix algebras over~$\C$ closed
under the Hadamard (componentwise) multiplication and
the Hermitian conjugation and
containing the identity matrix and the all-one matrix. The closedness
under the Hadamard multiplication enables us to associate to any
cellular algebra the scheme consisting of the binary relations
corresponding to the elements of its uniquely determined
linear base consisting of \{0,1\}-matrices. Conversely, any scheme
produces a cellular algebra (its Bose-Mesner algebra) spanned by the
adjacency matrices of its basis relations. This 1-1 correspondence
transforms isomorphisms of schemes to
strong isomorphisms of cellular algebras, schemes with the same
intersection numbers to weakly isomorphic cellular algebras (which
means
the existence of a matrix algebra
isomorphism preserving the Hadamard multiplication) and 2-orbit
(orbital)
schemes
to the centralizer algebras of permutation groups. We also mention
that
the automorphism group of any scheme coincides with
the automorphism group of its Bose-Mesner algebra.
Our technique is based on the following notion of the extended
algebra
introduced in~\cite{EKP} and studied in~\cite{EPL} (as to exact
definitions see Section~\ref{eaaawi}).
For each positive integer $m$ we define the $m$-extended algebra
$\W^\m$ of a cellular algebra~$W\le\Mat_V$ as the smallest cellular
algebra
on the set $V^m$ containing the $m$-fold tensor product of~$W$ and
the
adjacency
matrix of the reflexive relation corresponding to the diagonal of
$V^m$.
The algebra~$\W^\m$ plays the same role with respect to~$W$ as the
induced
coordinatewise action of the group~$G$ on~$V^m$ with respect to a
given action of~$G$ on~$V$.
Using the natural bijection between this diagonal and~$V$ we define
a cellular algebra $\ov W^\m$ on~$V$ called the $m$-closure of~$W$.
This produces the following series of inclusions:
\qtnl{mlab1}
W=\ov W^{(1)}\leq\ldots\leq \ov W^{(n)}=\ldots=\ov W^{(\infty)}
\eqtn
where $\ov W^{(\infty)}$ is the Schurian closure of~$W$,
i.e. the centralizer algebra of $\aut(W)$ in $\Mat_V$,
and $n$ is the number of elements of~$V$. Similarly we refine the
concept
of a weak isomorphism by saying that a weak isomorphism of cellular
algebras is an $m$-isomorphism if it can be extended to a weak
isomorphism of
their $m$-extended algebras. Then given two cellular algebras $W$ and
$W'$
we have
\qtnl{mlab2}
\isow(W,W')=\isow_1(W,W')\supset\ldots\supset\isow_n(W,W')=
\ldots=\isow_\infty(W,W')
\eqtn
where $\isow_m(W,W')$ is the set of all $m$-isomorphisms from $W$ to
$W'$
and $\isow_\infty(W,W')$ is the set of all weak isomorphisms from $W$
to $W'$
induced by strong isomorphisms. According to (\ref{mlab2}) and
(\ref{mlab1})
we say that the algebra $W$ is $m$-separable if
$\isow_m(W,W')=\isow_\infty(W,W')$ for all cellular algebras $W'$,
and $m$-Schurian if $\ov W^\m=\ov W^{(\infty)}$. Now we define
the separability number $s(W)$ and the Schurity number $t(W)$ of~$W$
by
$$s(W)=\min\{m:\ W\ \textstyle{\rm is}\ m-\textstyle{\rm
separable}\},\quad
t(W)=\min\{m:\ W\ \textstyle{\rm is}\ m-\textstyle{\rm
Schurian}\}.$$
It follows from Theorem \ref{tequ1} that there exist cellular
algebras with
arbitrary large separability and Schurity numbers. However their
values
for an algebra on $n$ points do not exceed $\lceil n/3\rceil$
(Theorem~\ref{ndivtr}) and equal 1 for a simplex and a
semiregular algebra (Theorem~\ref{simsem}).
In the general case we estimate these numbers for~$W$ by those for
pointwise
stabilizers and extended algebras of it (Theorem~\ref{estst}). In
particular,
we show that $s(W)$ and $t(W)$ do not exceed $b(W)+1$ where $b(W)$ is
the
base number of~$W$ (Theorem~\ref{th47}). All of these results are
used in
Sections~\ref{threetw} and~\ref{applic}.
Let us turn to schemes. We define the separability number and the
Schurity
number of a scheme as the corresponding numbers of its Bose-Mesner
algebra.
A scheme $\CC$ is called $m$-separable if $s(\CC)\le m$
and $m$-Schurian if $t(\CC)\le m$. In particular, any $m$-separable
scheme
is uniquely determined by the structure constants of its $m$-extended
algebra. Similarly, the scheme
corresponding to the $m$-closure of the Bose-Mesner algebra
of an $m$-Schurian scheme is an orbital one.
The class of 1-separable and 1-Schurian schemes is of special
interest. As
it follows from the results of the paper a number of schemes
associated with
classical distance-regular graphs are in it. It also contains
the class of schemes arising from algebraic forests. This class of
graphs was introduced and studied in~\cite{EPT} and contains trees,
cographs
and interval graphs.
In this paper we estimate the separability and Schurity numbers for
several classes of schemes. In Section~\ref{threetw} by analogy with
3/2-transitive permutation groups (i.e. transitive ones whose
all subdegrees are equal) we introduce the class of
3/2-homogeneous schemes containing in particular all cyclotomic
schemes. We
show that any imprimitive 3/2-homogeneous scheme is 2-separable and
2-Schurian (Theorem~\ref{tvhh}). The primitive case seems to be more
complicated and all we can prove here is that any cyclotomic scheme
on
a prime number of points is 4-separable (Theorem~\ref{oneth}). (It
should be remarked that such schemes are not necessarily
1-separable.)
This result can be used for constructing a simple polynomial-time
algorithm
to recognize circulant graphs of prime order (an efficient algorithm
for this problem was originally presented in~\cite{MT}).
The concepts of $m$-separability and $m$-Schurity take especially
simple
form in the case of the schemes of distance-regular graphs. Indeed,
such a scheme is 1-separable iff the graph is uniquely determined by
its parameters and 1-Schurian iff the graph is distance-transitive
(Proposition~\ref{estar}). Using known characterizations of Johnson
and Hamming schemes we compute the separability and Schurity
numbers of all schemes with the corresponding parameters (Theorems
\ref{stjsc} and \ref{hsst}). In particular we prove that the scheme
of any
Doob graph is exactly 2-separable and 2-Schurian and also that
the Doob graphs are pairwise non-isomorphic. In the case of
Grassmann schemes we cannot give the exact values of the separability
and
Schurity numbers for all schemes with the same parameters. However
we show (Theorem~\ref{grasch}) that any Grassmann scheme is
2-separable (its
1-Schurity follows from the distance-transitivity). In some cases,
one can
estimate the separability and Schurity numbers of a scheme by
indirect
reasoning. For example, in Subsection~\ref{ivasec} we prove the
2-Schurity
of the schemes arising from some strongly regular graphs with the
automorphism group
of rank~4. One of them is the graph on 256 vertices (found by
A.~V.~Ivanov in~\cite{I}) which is the only known to the authors
strongly
regular non rank 3 graph satisfying the 5-vertex condition. Our last
example
is the distance-regular graph of diameter~4 corresponding to a finite
projective
plane. In the general case, the separability and Schurity numbers of
its scheme do not exceed $O(\log\log q)$ where $q$ is the order
of the plane (Theorem~\ref{projplane}).
In the case of a Galois plane we prove that the corresponding scheme
is 6-separable.
The most part of the above results is based on the notion of
the $(\KG,\LG)$-regularity of an edge colored graph~$\G$ introduced
and
studied in Section~\ref{klreg} (here $\KG$ and $\LG$ are edge colored
graphs,
$\LG$ being a subgraph of~$\KG$). If $\KG$ and $\LG$ have
at most $t$ and 2 vertices
respectively, then the $(\KG,\LG)$-regularity of~$\G$
for all such $\KG,\LG$ exactly means that~$\G$
satisfies the $t$-vertex condition. In the general
case the $(\K,\LG)$-regularity of~$\G$ means that any embedding of
$\LG$
to~$\G$ can be extended in the same number of ways to an embedding
of~$\K$ to it. Many classical
distance-regular graphs are $(\K,\LG)$-regular for several choices of
$\K$ and $\LG$ and, moreover, they can be characterized in such a
way.
We use this observation in Section~\ref{applic} for computing the
separability and Schurity numbers of some classical schemes.
We show that the colored graphs of the schemes corresponding to
$m$-isomorphic algebras are simultaneously $(\KG,\LG)$-regular or not
for all colored graphs $\KG,\LG$ with at most $3m$ and $2m$ vertices
respectively (Corollary~\ref{crl73}).
In addition we prove that the colored graph of the scheme
corresponding to
an $m$-closed algebra satisfies
the $3m$-vertex condition (Theorem~\ref{mcondth}).
The paper consists of eight sections. Section~\ref{secccca}
contains the main definitions and notation concerning schemes
and cellular algebras. In Section~\ref{eaaawi} we give a brief
exposition
of the theory of $m$-extended algebras and $m$-isomorphisms. Here we
illustrate the first concept by considering the $m$-equivalence of
cellular
algebras which is similar in a sense to the $m$-equivalence of
permutation groups (see~\cite{W2}). In Section~\ref{ssnum} we
introduce
the separability and Schurity numbers of cellular algebras and
schemes
and study general properties of them. Sections~\ref{threetw}
and~\ref{applic}
are devoted to computing the separability and Schurity numbers for
3/2-homogeneous schemes and the schemes of some distance-regular
graphs.
In Section~\ref{klreg} we study the $(\K,\LG)$-regularity
of colored graphs. Finally, Section~\ref{appnd} (Appendix) contains a
number of technical results
concerning the structure of extended algebras and their weak
isomorphisms.
These results are used
in Subsection~\ref{meqsus} and Section~\ref{ssnum}.
{\bf Notation.} As usual by $\C$ and $\ZZ$ we denote the complex
field and
the ring of integers.
Throughout the paper $V$ denotes a finite set with $n = |V|$
elements.
A subset of $V\times V$ is called a relation on $V$. For a relation
$R$ on
$V$ we define its support $V_R$ to be the smallest set $U\subset V$
such that $R \subset U \times U$.
By an equivalence $E$ on $V$ we always mean an ordinary equivalence
relation
on a subset of~$V$ (coinciding with~$V_E$). The set of equivalence
classes of $E$ will be denoted by $V/E.$
The algebra of all
complex matrices whose rows and columns are indexed by the elements
of~$V$
is denoted
by $\Mat_V,$ its unit element (the identity matrix) by $I_V$ and the
all-one
matrix by~$J_V.$ Given $A\in\Mat_V$ and $u,v\in V$, we denote by
$A_{u,v}$
the element of $A$ in the row indexed by $u$ and the column indexed
by $v$.
For $U \subset V$ the algebra $\Mat_U$ can be treated in a natural
way as
a subalgebra of $\Mat_V.$ If $A\in\Mat_V$, then $A_U$ will denote
the submatrix of~$A$ corresponding to~$U$, i.e.
the matrix in $\Mat_U$ such that $(A_U)_{u,v}=A_{u,v}$ for all
$u,v\in U$.
The adjacency matrix of a relation $R$ is denoted by $A(R)$
(this is a \{0,1\}-matrix of $\Mat_V$ such that $A(R)_{u,v}=1$ iff
$(u,v)\in R$). For $U, U' \subset V$ let $J_{U,U'}$ denote the
adjacency matrix of the relation $U \times U'.$
The transpose of a matrix $A$ is denoted by $A^T$, its Hermitian
conjugate
by $A^*.$ If $R$ is a relation on~$V$, then $R^T$ denotes the
relation
with adjacency matrix~$A(R)^T$.
Each bijection $g:V \to V'$ ($v\mapsto v^g$)
defines a natural algebra isomorphism from
$\Mat_V$ onto $\Mat_{V'}.$ The image of a matrix $A$ under it
will be denoted by $A^g$, thus $(A^g)_{u^g,v^g}=A_{u,v}$
for all $u,v\in V$. If $R$ is a relation on~$V$, then we set $R^g$
to be the relation on~$V'$ with adjacency matrix~$A(R)^g$.
The group of all permutations of $V$ is denoted by $\sym(V).$
For integers $l,m$ the set $\{l,l+1,\ldots,m\}$ is denoted by
$[l,m]$.
We write $[m]$, $\sym(m)$ and $V^m$ instead of $[1,m]$,
$\sym([m])$ and $V^{[m]}$ respectively. Finally,
$\Delta^\m(V)=\{(v,\ldots,v)\in V^m:\ v\in V\}$.
\section{Coherent configurations and cellular algebras}
\label{secccca}
\SuSS\label{ccaca}
Let $V$ be a finite set and $\R$ a set of
binary relations on $V$.
A pair $\CC=(V,\R)$ is called a {\it coherent configuration} or a
{\it scheme} on $V$ if the following conditions are satisfied:
\nmrt
\tm{C1} $\R$ forms a partition of the set $V^2$,
\tm{C2} $\Delta^{(2)}(V)$ is a union of elements of $\R$,
\tm{C3} if $R\in\R$, then $R^T\in\R$,
\tm{C4} if $R,S,T\in\R$, then the number
$|\{v\in V:\ (u,v)\in R,\ (v,w)\in S\}|$ does not depend on the
choice of $(u,w)\in T$.
\enmrt
The numbers from (C4) are called the {\it intersection numbers} of
$\CC$
and denoted by~$p_{R,S}^T$. The elements of~$\R=\R(\CC)$ are called
the
{\it basis
relations} of~$\CC$.
We say that schemes $\CC=(V,\R)$ and $\CC'=(V',\R')$ are {\it
isomorphic},
if $\R^g=\R'$ for some bijection $g:V\to V'$ called an {\it
isomorphism}
from~$\CC$ to~$\CC'$. The group of all isomorphisms from~$\CC$ to
itself
contains a normal subgroup
$$\aut(\CC)=\{g\in\sym(V):\ R^g=R,\ R\in\R\}$$
called the {\it automorphism group} of~$\CC$. Conversely, to each
permutation
group $G\le\sym(V)$ we associate a scheme $(V,\orb_2(G))$ where
$\orb_2(G)$
is the set of all 2-orbits of~$G$. The above mappings between schemes
and permutation groups on~$V$ are not inverse to each other but
define a Galois
correspondence with respect to the natural partial orders on these
sets
(cf.~\cite[p.16]{FKM}). A scheme~$\CC$
is called {\it Schurian} if it is a closed object under this
correspondence,
i.e. if the set of its basis relations coincides
with~$\orb_2(\aut(\CC))$.
If $\CC=(V,\R)$ is a scheme, then the set $\M=\{A(R):\ R\in\R\}$ is a
linearly
independent subset of $\Mat_V$ by~(C1). Its linear span is closed
with
respect to the matrix multiplication by~(C4) and so defines a
subalgebra
of~$\Mat_V$.
It is called the {\it Bose-Mesner} (or {\it adjacency}) algebra
of~$\CC$
and will be denoted by~$\A(\CC)$. Obviously, it is a {\it cellular}
algebra on~$V$, i.e. a subalgebra~$\A$ of~$\Mat_V$ satisfying the
following
conditions:
\nmrt
\tm{A1} $I_V,J_V\in\A$,
\tm{A2} $\forall A\in\A:\quad A^*\in\A$,
\tm{A3} $\forall A,B\in\A:\quad A\circ B\in\A$,
\enmrt
where $A\circ B$ is the Hadamard (componentwise) product of the
matrices
$A$ and~$B$.
The elements of $V$ are called the {\it points} and the set~$V$
is called the {\it point set} of~$\A$.
Each cellular algebra $\A$ on $V$ has a uniquely determined linear
base $\M=\M(\A)$ consisting of \{0,1\}-matrices such that
\qtnl{laststar}
\sum_{A\in\M}A=J_V\quad\textstyle{and}\quad A\in\M\ \Leftrightarrow\
A^T\in\M.
\eqtn
The linear base $\M$ is called the {\it standard basis} of~$\A$ and
its elements the {\it basis matrices}. The nonnegative integers
$p^C_{A,B}$ defined for $A,B,C\in\M$ by
$AB=\sum_{C\in\M}p^C_{A,B}\cdot C$
are called the {\it structure constants} of~$\A$.
We say that cellular algebras $\A$ on~$V$ and~$\A'$ on~$V'$ are
{\it strongly isomorphic}, if $\A^g=\A'$ for some bijection
$g:V\to V'$ called a {\it strong isomorphism} from~$\A$ to~$\A'$.
The group of all strong isomorphisms from~$\A$ to itself contains a
normal subgroup
$$\aut(\A)=\{g\in\sym(V):\ A^g=A,\ A\in\A\}$$
called the {\it automorphism group} of~$\A$. Conversely, for any
permutation group $G\le\sym(V)$ its {\it centralizer algebra}
$$\Z(G)=\{A\in\Mat_V:\ A^g=A,\ g\in G\}$$
is a cellular algebra on~$V$. A cellular algebra $\A$ is called
{\it Schurian} if $\A=\Z(\aut(\A))$.
Comparing the definitions of schemes and cellular algebras one can
see
that the mappings
\qtnl{ldom}
\CC\mapsto\A(\CC),\quad \A\mapsto\CC(\A)
\eqtn
where $\CC(\A)=(V,\R(\A))$ with $\R(\A)=\{R\subset V^2:\
A(R)\in\M(\A)\}$,
are reciprocal bijections between the sets of schemes and cellular
algebras on~$V$. Here the intersection numbers of a scheme coincide
with the structure constants of the corresponding cellular algebra.
Moreover, the set of all isomorphisms of two schemes
coincides with the set of all strong isomorphisms of the
corresponding
cellular algebras and the automorphism group of a scheme coincides
with the automorphism group of the corresponding cellular algebra.
Finally,
the correspondence~(\ref{ldom}) takes Schurian schemes to Schurian
cellular algebras and vice versa.
The properties of the correspondence (\ref{ldom}) show that schemes
and
cellular
algebras are in fact the same thing up to language. So the name of
any class of
cellular algebras used below (homogeneous, primitive, $\ldots$) is
inherited by the corresponding class of schemes. Similarly, we use
all
notions and notations introduced for basis matrices of a cellular
algebra
(degree, $d(A)$, $\ldots$) also for basis relation of a scheme.
We prefer to deal with
cellular algebras because this enables us to use standard algebraic
techniques. Below we will traditionally denote a cellular algebra
by~$W$.
The set of all cellular algebras on $V$ is partially ordered by
inclusion.
The largest and the smallest elements of the set are respectively the
full matrix algebra $\Mat_V$ and the simplex on~$V$, i.e.
the algebra $\Z(\sym(V))$ with the linear base $\{I_V,J_V\}$. We
write
$W\le W'$
if~$W\subset W'$. Given subsets $X_1,\ldots,X_s$ of $\Mat_V$, their
{\it
cellular
closure}, i.e. the smallest cellular algebra on~$V$ containing all of
them
is denoted by $[X_1,\ldots,X_s]$. If $X_i=\{A_i\}$, we omit the
braces. For
a cellular algebra $W\le\Mat_V$ and a point $v\in V$ we set
$W_v=[W,I_v]$
where $I_v=I_{\{v\}}$.
\eSuSS
Let $W\le\Mat_V$ be a cellular algebra and $\M=\M(W)$. Set
$$\cel(W)=\{U\subset V:\ I_U\in\M\},\quad
\cel^*(W)=\{\bigcup_{U\in X}U:\ X\subset\cel(W)\}.$$
Each element of $\cel(W)$ (resp. $\cel^*(W)$) is called a {\it cell}
of~$W$
(resp. a {\it cellular set} of~$W$). Obviously,
$$V=\bigcup_{U\in\cel(W)}U\qquad \textstyle{\rm (disjoint\
union).}$$
The algebra $W$ is called {\it homogeneous} if $|\cel(W)|=1$.
For $U_1,U_2\in\cel^*(W)$ set $\M_{U_1,U_2}=\{A\in\M:\ A\circ
J_{U_1,U_2}=A\}$.
Then
$$\M=\bigcup_{U_1,U_2\in\cel(W)}\M_{U_1,U_2}\qquad\textstyle{\rm
(disjoint\
union).}$$
Also, since for any cells $U_1,U_2$ and any $A\in\M_{U_1,U_2}$ the
$u$th
diagonal
element of the matrix $AA^T$ equals the number of 1's in the $u$th
row
of~$A$, it follows that the number of 1's in the $u$th row (resp.
$v$th
column) of $A$ does not depend on the choice of $u\in U_1$ (resp.
$v\in U_2$).
This number is denoted by $d_{out}(A)$ (resp. $d_{in}(A)$). If $W$ is
homogeneous, then $d_{out}(A)=d_{in}(A)$ for all $A\in\M$ and we use
the
notation $d(A)$ for this number and call it the {\it degree} of~$A$.
A
cellular algebra $W$ is called {\it semiregular}
if $d_{in}(A)=d_{out}(A)=1$ for all $A\in\M$. A homogeneous
semiregular algebra is called {\it regular}.
For each $U\in\cel^*(W)$ we view the subalgebra $I_UWI_U$ of~$W$
as a cellular algebra on~$U$, denote it by $W_U$ and call the
{\it restriction} of~$W$ to~$U$. The basis matrices of $W_U$ are in
a natural
1-1 correspondence to the matrices of~$\M_{U,U}$. If $U\in\cel(W)$,
we call
$W_U$ the {\it homogeneous component} of~$W$ corresponding to~$U$.
A relation $R$ on $V$ is called a relation of the algebra~$W$ if
$A(R)\in W$. If in addition $A(R)\in\M$, we say that~$R$ is a
basis one. We observe that the set of all basis relations of~$W$
coincides with $\R(W)=\R(\CC(W))$. For $U_1,U_2\in\cel(W)$ we set
$$\R_{U_1,U_2}=\R_{U_1,U_2}(W)=\{R\in\R(W):\ A(R)\in\M_{U_1,U_2}\}.$$
\eSuSS
Let $W$ be a cellular algebra on~$V$ and $E$ be an equivalence
on~$V$.
We say that $E$ is an {\it equivalence} of~$W$ if it is the union of
basis
relations of~$W$. In this case its support $V_E$ is a cellular
set of~$W$. The set of all equivalences of $W$ is denoted by~$\E(W)$.
The equivalences of~$W$ with the adjacency matrices $I_V$
and $J_V$ are called {\it trivial}. Suppose now that~$W$ is
homogeneous. We
call~$W$ {\it imprimitive} if it has a nontrivial equivalence. If~$W$
has
exactly two equivalences, then it is called {\it primitive}. We
stress that
a cellular algebra on a one-point set is neither imprimitive nor
primitive
according to this definition.
Let $E\in\E(W)$. For each $U\in V/E$ we view the
subalgebra $I_UWI_U$ of~$\Mat_V$ satisfying obviously conditions~(A2)
and~(A3) as a cellular algebra on~$U$ and denote it by $W_{E,U}$. Its
standard basis is of the form
\qtnl{equbas}
\M(W_{E,U})=\{A_U\,:\ A\in\M,\ I_UAI_U\not=0\}.
\eqtn
It follows from~(\ref{equbas}) and the first part of~(\ref{laststar})
that
each basis matrix of $W_{E,U}$ can be uniquely represented in the
form $A_U$ for some $A\in\M(W)$. Set
$$W_E=\{A(E)\circ B:\ B\in W\}.$$
Then $W_E$ is a subalgebra of~$W$ satisfying conditions~(A2)
and~(A3).
A nonempty equivalence $E$ of $W$ is called {\it indecomposable} (in
$W$)
if $E$ is not a disjoint union of two nonempty equivalences
of~$W$. We observe that any equivalence of a
homogeneous algebra is obviously indecomposable whereas it is not the
case
for a non-homogeneous one (the simplest example is the equivalence
the
classes of which are cells). The equivalence $E$ is called {\it
decomposable}
if it is not indecomposable. In this case $E=E_1\cup E_2$ for some
nonempty
equivalences $E_1$ and $E_2$ of~$W$ with disjoint supports. It is
easy to
see that each equivalence of~$W$ can be uniquely represented as a
disjoint
union of indecomposable ones called {\it indecomposable components}
of it.
It follows from \cite[Lemma 2.6]{EKP} that given an indecomposable
equivalence~$E\in\E(W)$ we have
$$|U_1\cap X|=|U_2\cap X|>0\quad\textstyle{\rm for\ all\ cells}\
X\subset V_E
\ \textstyle{\rm and}\ U_1,U_2\in V/E.$$
In particular, all classes of~$E$ are of the same cardinality.
Besides,
given an equivalence of~$W$, the support of an indecomposable
component of
it coincides with the smallest cellular set of~$W$ containing any
given
class of this component. Another consequence of \cite[Lemma 2.6]{EKP}
is that if $E$ is indecomposable, then given $U\in V/E$ the mapping
\qtnl{btri}
\pi^{}_U:W_E\to W_{E,U},\quad A\mapsto A_U
\eqtn
is a matrix algebra isomorphism preserving the Hadamard
multiplication.
We complete the subsection by a technical lemma which
will be used later.
\lmml{lzero}
Let $W\le\Mat_V$ be a cellular algebra, $R\in\R(W)$ and
$E_1,E_2\in\E(W)$.
Then the number $|(U_1\times U_2)\cap R|$ does not depend on the
choice
of $U_1\in V/E_1$ and $U_2\in V/E_2$, such that
$(U_1\times U_2)\cap R\ne\emptyset$.
\elmm
\proof Suppose that $(U_1\times U_2)\cap R\ne\emptyset$.
Then the number $|(U_1\times U_2)\cap R|$ equals the
$(v_1,v_2)$-entry
of the matrix $A(E_1)A(R)A(E_2)$ where $(v_1,v_2)\in (U_1\times
U_2)\cap R$.
Since this number coincides with the coefficient at $A(R)$
in the decomposition of the last matrix with respect to the standard
basis of~$W$, we are done.\bull
\eSuSS
Along with the notion of a strong isomorphism we
consider for cellular algebras
also weak isomorphisms (see~\cite{W,EPL,EKP})\footnote{In
\cite[p.33]{W} they were called weak equivalences.}. Cellular
algebras
$W$ on $V$ and $W'$ on $V'$ are called {\it weakly isomorphic}
if there exists a matrix algebra isomorphism $\varphi:W\to W'$ such
that
\qtnl{prhad}
\varphi(A\circ B)=\varphi(A)\circ \varphi(B)\quad\textstyle{\rm for\
all}\ \,
A,B\in W.
\eqtn
Any such~$\varphi$ is called a {\it weak isomorphism} from $W$
to~$W'$.
It immediately follows from the definition that $\varphi$ takes
\{0,1\}-matrices to \{0,1\}-matrices and also $\varphi(I_V)=I_{V'}$,
$\varphi(J_V)=J_{V'}$. It was proved in \cite[Lemma 4.1]{EP} that
$\varphi(A^T)=\varphi(A)^T$ for all $A\in\M(W)$. Besides, $\varphi$
induces
a natural bijection $U\mapsto U^\varphi$ from $\cel^*(W)$ onto
$\cel^*(W')$
preserving cells such that $\varphi(I_U)=I_{U^\varphi}$ and
$|U|=|U^\varphi|$.
In particular, $|V|=|V'|$. Finally, $\varphi(\M)=\M'$ and moreover
\qtnl{p1wpr}
\varphi(\M_{U_1,U_2})=\M'_{U^\varphi_1,U^\varphi_2}\quad\textstyle{\rm
for\ all}\ \, U_1,U_2\in\cel^*(W)
\eqtn
where $\M=\M(W)$ and $\M'=\M(W')$.
Thus the corresponding structure constants of weakly isomorphic
algebras
coincide. More exactly,
$p_{A,B}^C=p_{\varphi(A),\varphi(B)}^{\varphi(C)}$
for all $A,B,C\in\M$.
The following lemma describes the behavior of the relations of a
cellular
algebra under weak isomorphisms.
\lmml{aisowpr}
Let $W\leq\Mat_V$ and $W'\leq\Mat_{V'}$ be cellular algebras and
$\varphi\in\isow(W,W')$. Then $\varphi$ induces a bijection
$R\mapsto R^\varphi$ from the set of all relations of~$W$ to
the set of all relations of~$W'$ such that
$\varphi(A(R))=A(R^\varphi)$.
Moreover,
\nmrt
\tm{1} $d_{in}(R)=d_{in}(R^\varphi)$,
$d_{out}(R)=d_{out}(R^\varphi)$,
$|R|=|R^\varphi|$ for all $R\in\R(W)$,
\tm{2} $E$ is an (indecomposable) equivalence of~$W$ iff $E^\varphi$
is an (indecomposable) equivalence of~$W'$. In addition,
$|V_E|=|V'_{E^\varphi}|$ and $|V/E|=|V'/E^\varphi|$.
\enmrt
\elmm
\proof Since statement~(2) coincides with Lemma~3.3 of~\cite{EPT}, we
prove only statement~(1). Let $R\in\R_{U_1,U_2}(W)$ where
$U_1,U_2\in\cel(W)$. Then obviously $d_{out}(R)=p_{R,R^T}^{\Delta_1}$
and
$d_{in}(R)=p_{R^T,R}^{\Delta_2}$ where $\Delta_i=\Delta^{(2)}(U_i)$,
$i=1,2$.
Since $R^\varphi\in\R_{U'_1,U'_2}(W')$ where $U'_i=(U_i)^\varphi$,
$i=1,2$,
(see~(\ref{p1wpr})) and $(R^T)^\varphi=(R^\varphi)^T$,
the equalities for degree follow. Now the third equality is the
consequence of the formulas $|R|=|U_1|d_{out}(R)$ and
$|U_1|=|U'_1|$.\bull
We observe that the composition of weak isomorphisms
and the inverse of a weak isomorphism are also weak isomorphisms.
Evidently each strong isomorphism from~$W$ to~$W'$ induces a weak
isomorphism between these algebras.
The set of all weak isomorphisms from $W$ to $W'$ is denoted by
$\isow(W,W')$.
If $W=W'$ we write $\isow(W)$ instead of $\isow(W,W)$. Clearly,
$\isow(W)$
forms a group isomorphic to a subgroup of~$\sym(\M(W))$.
\section{Extended algebras and their weak isomorphisms}
\label{eaaawi}
\SuSS\label{defexal}
Let $W$ be a cellular algebra on $V$. For each positive integer~$m$
we set
\qtnl{defmext}
\W=\W^\m=[W^m,\ \Z_m(V)]
\eqtn
where $W^m=W\otimes\cdots\otimes W$ is the $m$-fold tensor product
of~$W$
and $\Z_m(V)$ is the centralizer algebra of the coordinatewise action
of
$\sym(V)$ on $V^m$.
We call the cellular algebra $\W\le\Mat_{V^m}$ the {\it $m$-extended
algebra}
of~$W$. The group $\aut(\W)$ acts faithfully on the set
$\Delta=\Delta^\m(V)$.
Moreover, the mapping $\delta:v\mapsto (v,\ldots,v)$ induces a
permutation
group isomorphism between $\aut(W)$ and the constituent of $\aut(\W)$
on~$\Delta$. It was proved in~\cite{EPL} that
\qtnl{thdiag}
\W=[W^m,I_\Delta].
\eqtn
The cellular algebra on~$V$ defined by
$$\ov W=\ov W^\m=((\W^\m)_\Delta)^{\delta^{-1}}$$
is called the {\it $m$-closure} of~$W$. We say that~$W$ is
{\it $m$-closed} if~$W=\ov W^\m$.
It was proved in \cite[Proposition 3.3]{EKP} that $\aut(\ov
W^\m)=\aut(W)$,
\qtnl{mpath}
W=\ov W^{(1)}\leq\ldots\leq \ov W^{(n)}=\ldots=W^{(\infty)}
\eqtn
and the algebra $\ov W^\m$ is $l$-closed for all $l\in[m]$. In
addition,
it is easy to see that if $l\ge m$, then the $l$-closure of~$\ov
W^\m$
equals~$\ov W^{(l)}$.
We complete the subsection with two statements to be used later.
Below we identify the sets $(V^m)^l$ and $V^{lm}$ using the bijection
from $[m]\times[l]$ onto~$[lm]$ defined by $(i,j)\mapsto i+(j-1)m$.
\lmml{prschup}
Let~$W$ be a cellular algebra and~$l,m$ positive integers. Then
$(\wh{\W^\m})^{(l)}=\W^{(lm)}$.
\elmm
\proof Obviously, the algebra $W^{lm}$ and the matrix
$I_{\Delta^{(lm)}(V)}=(\otimes_{j=1}^l I_{\Delta^{(m)}(V)})\circ
I_{\Delta^{(l)}(V^m)}$ are contained in $(\wh{W^\m})^{(l)}$. So
by~(\ref{thdiag}) the right side
of the equality in question is contained in the left one. Conversely,
$I_{\Delta^{(l)}(V^m)}$ belongs to $\Z_{lm}(V)$ and hence belongs
also to
$\W^{(lm)}$. Besides, $(\W^\m)^l\subset\W^{(lm)}$ due to
statement~(4)
of Lemma~7.2 of~\cite{EPL} with $I_k=J_k=[1+(k-1)m,km]$, $k\in[l]$,
and $lm$ instead of~$m$. Thus we are done by~(\ref{thdiag}).\bull
The following technical statement was in fact proved in~\cite{EKP}.
\lmml{lstar}
Let $W'$ be a cellular algebra on~$V^m$ containing $\Z_m(V)$
and $W=(W'_\Delta)^{\delta^{-1}}$. Then $W'\ge\W^\m$
and also $W$ is $m$-closed. In particular, the $m$-extended algebras
of
an algebra and its $m$-closure coincide.
\elmm
\proof It follows from the proof of statement~(5) of Lemma~5.2
of~\cite{EKP}
that $W'\ge W^m$. Thus the required inclusion is the consequence of
equality~(\ref{thdiag}).\bull
\eSuSS
Let $\varphi:W\to W'$ be a weak isomorphism from a cellular algebra
$W\leq\Mat_V$ to a cellular algebra $W'\leq\Mat_{V'}$.
According to \cite{EPL} we say that a weak isomorphism
$\psi:\W\to\WP$ is an {\it $m$-extension} of $\varphi$ if
$\psi(I_\Delta)=
I_{\Delta'}$ and $\psi(A)=\varphi^m(A)$ for all $A\in W^m$,
where $\Delta=\Delta^{(m)}(V)$, $\Delta'=\Delta^{(m)}(V')$
and $\varphi^m$ is the weak isomorphism from $W^m$ to $(W')^m$
induced by $\varphi$.
It was proved in~\cite{EPL} that~$\psi$ is uniquely determined
by~$\varphi$
and the restriction of it to~$\W_\Delta$ induces a uniquely
determined weak
isomorphism from $\ov W$ to $\ov{W'}$ extending~$\varphi$. We denote
these weak isomorphisms by~$\wh\varphi=\wh\varphi^\m$ and
$\ov\varphi=\ov\varphi^\m$ respectively. As it was observed
in~\cite{EPL},
$\wh\varphi$ takes a basis matrix of~$\Z_m(V)$ to the corresponing
basis
matrix of~$\Z_m(V')$.
A weak isomorphism $\varphi$ is called an {\it $m$-isomorphism} if
there
exists an $m$-extension of~$\varphi$.
The set of all $m$-isomorphisms from $W$ to $W'$ will be denoted by
$\isow_m(W,W')$. It was proved in~\cite[Theorem~4.5 and
formula~(7)]{EPL}
that
\qtnl{twostar}
\isow(W,W')=\isow_1(W,W')\supset\ldots\supset\isow_n(W,W')=
\ldots=\isow_\infty(W,W')
\eqtn
where $\isow_\infty(W,W')$ is the set of all weak isomorphisms
from~$W$
to~$W'$ induced by strong isomorphisms.
The following lemma will be of use later.
\lmml{isowpr}
Let $W,W'$ be cellular algebras and~$l,m$ positive integers. Then
$\varphi\in\isow_{lm}(W,W')$ iff $\varphi\in\isow_m(W,W')$ and
$\wh\varphi^\m\in\isow_l(\W{\mathstrut}^\m,{\WP}{\mathstrut}^\m)$.
In this case, $\wh\varphi^{(lm)}=(\wh{\wh\varphi^\m})^{(l)}$.
\elmm
\proof Let $\varphi\in\isow_{lm}(W,W')$. Then
$\varphi\in\isow_m(W,W')$
by~(\ref{twostar}). Besides,
$\wh\varphi^{(lm)}(I_{\Delta^{(l)}(V^m)})=I_{\Delta^{(l)}({V'}^m)}$
as far as~$\wh\varphi^{(lm)}$ takes basis matrices of~$\Z_{lm}(V)$ to
the
corresponding basis matrices of~$\Z_{lm}(V')$. On the other hand,
since $(\Z_m(V))^l\subset\Z_{lm}(V)$, we have
\qtnl{onestr}
\wh\varphi^{(lm)}(A)=(\wh\varphi^\m)^l(A)
\eqtn
for all $A\in(\Z_m(V))^l$. Further, equality~(\ref{onestr}) obviously
holds also for all $A\in(W^m)^l$. So it holds for all
$A\in(\W^\m)^l$ by the definition of~$\W^\m$ and Lemma~\ref{prschup}.
Thus
$\wh\varphi^{(lm)}$ is the $l$-extension of~$\wh\varphi^\m$.
Conversely, let $\varphi\in\isow_m(W,W')$ and
$\wh\varphi^\m\in\isow_l(\W{\mathstrut}^\m,\WP{\mathstrut}^\m)$.
We show that
$\psi=(\wh{\wh\varphi^\m})^{(l)}$ is the $lm$-extension of~$\varphi$.
Indeed, $\psi(A)=(\wh\varphi^\m)^l(A)=\varphi^{lm}(A)$ for all
$A\in W^{lm}$ by the definition of~$\wh\varphi^\m$. On the other
hand, since
$\Delta^{(lm)}(V)=(\otimes_{j=1}^l I_{\Delta^\m(V)})\circ
I_{\Delta^{(l)}(V^m)}$,
we have
$$\psi(I_{\Delta^{(lm)}(V)})=
(\otimes_{j=1}^l\wh\varphi^\m(I_{\Delta^\m(V)}))\circ
\psi(I_{\Delta^{(l)}(V^m)})=
(\otimes_{j=1}^l I_{\Delta^\m(V')})\circ
I_{\Delta^{(l)}({V'}^m)}=
I_{\Delta^{(lm)}(V')},
$$
which completes the proof.\bull
\eSuSS\label{meqsus}
In this subsection we illustrate the $m$-extended algebra technique
by using the following notion which is similar to the notion of the
$m$-equivalence of permutation groups introduced in~\cite{W2}.
\dfntn
Two cellular algebras on the same set of points are called
{\it $m$-equivalent}, if their $m$-extended algebras equal.
\edfntn
It immediately follows from the definition that the automorphism
groups
and hence the Schurian closures of $m$-equivalent algebras coincide.
\lmml{meqmcl}
Two cellular algebras are $m$-equivalent iff their $m$-closures are
equal.
\elmm
\proof The necessity follows from the definition of $m$-closure,
whereas
the sufficiency is the consequence of Lemma~\ref{lstar}.\bull
Lemma~\ref{meqmcl} implies that each class of $m$-equivalent
cellular algebras has the
largest element coinciding with the $m$-closure of any algebra of the
class. Below we write $W_1\approx_m W_2$, if
$W_1$ and $W_2$ are $m$-equivalent. The statements of the next lemma
are similar to the properties of the $m$-equivalence of permutation
groups proved in~\cite[pp.8-12]{W2}.
\lmm
Let $W_1,\, W_2$ be cellular algebras on an $n$-point set~$V$. Then
\nmrt
\tm{1} $W_1\approx_1 W_2$ iff $W_1=W_2$,
\tm{2} if $W_1\approx_m W_2$, then $W_1\approx_{m+1} W_2$,
\tm{3} if $m\ge n$, then $W_1\approx_m W_2$ iff
$\aut(W_1)=\aut(W_2)$,
\tm{4} if $W_1\approx_m W_2$, then $(W_1)_v\approx_m (W_2)_v$ for all
$v\in V$.
\enmrt
\elmm
\proof Statement (1) is trivial. Set $\ov{W_i}=\ov{W_i}^\m$, $i=1,2$.
If $W_1\approx_m W_2$, then $\ov{W_1}=\ov{W_2}$ by
Lemma~\ref{meqmcl}.
So the $(m+1)$-closures of~$W_1$ and $W_2$ coincide. Thus
statement~(2)
follows from the same lemma. The necessity of
statement~(3) is clear. Conversely, if $\aut(W_1)=\aut(W_2)$, then by
formula~(\ref{mpath}) we conclude that
$$\ov{W_1}=\ov{W_1}^{(\infty)}=\ov{W_2}^{(\infty)}=\ov{W_2}.$$
Thus the sufficiency follows from Lemma~\ref{meqmcl}. Let us prove
statement~(4). Since $\wh{W_1}=\wh{W_2}$, we have $r_v(W_1)=r_v(W_2)$
(as to the definition of the algebra $r_v(W)$, see Appendix). On the
other
hand, applying the $m$-closure operator to inequality~(\ref{omineq})
with $W=W_i$ we see that $\ov{(W_i)_v}=\ov{r_v(W_i)}$, $i=1,2$.
Thus $\ov{(W_1)_v}=\ov{(W_2)_v}$, and we are done by
Lemma~\ref{meqmcl}.\bull
\section{The separability and Schurity numbers}
\label{ssnum}
\SuSS
Throughout the section we assume $m$ to be a positive integer.
\dfntn
A cellular algebra $W$ is called $m$-separable if
$\isow_m(W,W')=\isow_\infty(W,W')$ for all cellular algebras~$W'$;
it is called $m$-Schurian if $\ov W^\m=\ov W^{(\infty)}$.
A scheme is called $m$-separable (resp. $m$-Schurian) if so is its
Bose-Mesner algebra.
\edfntn
The $m$-separability of~$W$ means that any $m$-isomorphism from~$W$
to another cellular algebra is induced by a strong isomorphism,
whereas the $m$-Schurity of it means that the $m$-closure of~$W$ is a
Schurian algebra. Obviously, $W$ is 1-Schurian iff it is Schurian,
i.e. the corresponding scheme is orbital.
On the other hand, $W$ is 1-separable (briefly, separable) iff the
last scheme is uniquely determined by its intersection number array
(cf. Subsection~\ref{appli1}).
The following statement is an immediate consequence of the
definition of $m$-equivalence and Lemma~\ref{meqmcl}.
\thrml{tequ}
Two $m$-equivalent cellular algebras are $m$-separable (resp.
$m$-Schurian)
or not si\-mul\-ta\-ne\-o\-us\-ly.\bull
\ethrm
It follows from formula~(\ref{twostar}) (resp. formula~(\ref{mpath}))
that an $m$-separable (resp. $m$-Schurian) algebra is also
$l$-separable
(resp. $l$-Schurian) for all $l\ge m$ and that any cellular
algebra~$W$
on~$n$ points is always $n$-separable and $n$-Schurian. We set
$$s(W)=\min\{m:\ W\ \textstyle{\rm is}\ m-\textstyle{\rm
separable}\},\quad
t(W)=\min\{m:\ W\ \textstyle{\rm is}\ m-\textstyle{\rm
Schurian}\}.$$
These positive integers are called the {\it separability number} and
the
{\it Schurity number} of~$W$ respectively. The separability number
$s(\CC)$ and the Schurity number $t(\CC)$ of a scheme~$\CC$ are
defined
as the corresponding numbers of its Bose-Mesner algebra.
The following statement the proof of which is in the end of
Section~\ref{klreg}
shows that the inequalities $s(W)\le n$ and $t(W)\le n$ can be
slightly
improved.
\thrml{ndivtr}
For any cellular algebra~$W$ on $n$ points we have
$s(W)\le\lceil n/3\rceil$ and $t(W)\le\lceil n/3\rceil$.
\ethrm
In some cases the separability and Schurity numbers can easily be
computed.
\thrml{simsem}
If $W$ is a simplex or a semiregular algebra, then $s(W)=t(W)=1$.
In particular, $s(\Mat_V)=t(\Mat_V)=1$.
\ethrm
\proof The case of a simplex is trivial. Let~$W$ be a regular algebra
(the case of a semiregular algebra is easily reduced to this one).
Then
the set of basis matrices of~$W$ forms a finite group, say~$G$. So
$W$ is strongly isomorphic to the enveloping algebra
$\C[G_{right}]\le\Mat_G$
where $G_{right}$ is the permutation group on~$G$ defined by right
multiplications. However, $\C[G_{right}]=\Z(G_{left})$
where $G_{left}\le\sym(G)$ is defined by left multiplications.
Thus $\C[G_{right}]$ and hence~$W$ are Schurian. Let now
$\varphi:W\to W'$ be a weak isomorphism from a regular algebra~$W$ to
a cellular algebra~$W'$. By statement~(1) of Lemma~\ref{aisowpr} the
algebra~$W'$ is also regular. So without loss of generality we assume
that
$W=\C[G_{right}]$, $W'=\C[G'_{right}]$ where~$G$ and~$G'$ are finite
groups.
Then $\varphi$ is induced by the group isomorphism $G\to G'$
associated with the isomorphism of the groups of basis matrices.
Thus $\varphi\in\isow_\infty(W,W')$.\bull
It was proved in Theorem~1.1 (resp. in Theorem~1.3) of~\cite{EPL}
that
there exists $\varepsilon>0$ such
that for all sufficiently large positive integer $n$ one can find
a non-Schurian cellular algebra on~$n$ points which is $m$-closed for
some $m\geq\lfloor\varepsilon n\rfloor$ (resp. a Schurian algebra
with
simple spectrum on~$n$ points admitting an $m$-isomorphism with
$m\geq\lfloor\varepsilon n\rfloor$ which is not induced by a strong
isomorphism). This gives the following statement.
\thrml{tequ1}
There exist cellular algebras with arbitrary large separability
and Schurity numbers. Moreover
$$
\liminf_{n(W)\rightarrow\infty}{s(W)\over{n(W)}}>0,\quad\
\liminf_{n(W)\rightarrow\infty}{t(W)\over{n(W)}}>0
$$
where $W$ runs over all cellular algebras (even Schurian ones with
simple
spectrum in the first inequality) and $n(W)$ is the number of points
of~$W$.\bull
\ethrm
The interrelation between the separability and Schurity numbers seems
to be
rather complicated. For instance, Theorem~\ref{tequ1}
shows that there exist cellular algebras~$W$ with
$t(W)=1$ and arbitrary large~$s(W)$. On the other hand,
one can find cellular algebras with both separability and Schurity
numbers arbitrary large (e.g. ones from \cite[Subsection 5.5]{EPL}).
\eSuSS
The following theorem gives some upper bounds for the numbers
$s(W)$ and $t(W)$ via the corresponding numbers of some algebras
associated with~$W$.
\thrml{estst}
Let $W\le\Mat_V$ be a cellular algebra. Then
\nmrt
\tm{1} $s(W)\le s(W_v)+1$ for all $v\in V$,
\tm{2} if $W_v$ is $t(W_v)$-separable for some point $v\in V$,
then $t(W)\le t(W_v)+1$,
\tm{3} $s(W)\le m\,s(\W^\m)$, $t(W)\le m\,t(\W^\m)$ for all~$m\ge 1$.
\enmrt
\ethrm
\proof Let $\varphi:W\to W'$ be an $m$-isomorphism where
$m=s(W_v)+1$.
Choose $v'\in V'$ as in Subsection~\ref{subs82}. Then by
statement~(2)
of Lemma~\ref{isowfix} the weak isomorphism $\varphi_{v,v'}$ belongs
to $\isow_{m-1}(W{\mathstrut}_v,W'{\mathstrut}_{v'})$ and
extends~$\varphi$. Since $W_v$ is $(m-1)$-separable, $\varphi_{v,v'}$
and hence $\varphi$ are induced by a permutation from~$V$ to~$V'$.
Thus $s(W)\le m$.
Set $m=t(W_v)+1$. Then the algebra $(\ov{W_v})^{(m-1)}$
is Schurian and hence by Corollary~\ref{twopol} coincides
with~$r_v^\m(W)$.
So by Lemma~\ref{isowfix} we have
$r_{v,v'}^\m(\varphi)=\ov{\varphi_{v,v'}}^{(m-1)}$
where~$\varphi$ and~$v'$ are as in Theorem~\ref{addschur}. Therefore
by the
assumption of statement~(2) and Theorem~\ref{tequ} the weak
isomorhism~$r_{v,v'}^\m(\varphi)$ is induced by a bijection
$g_{v,v'}:V\to V'$. Thus Theorem~\ref{addschur} implies that the
basis
relations of the algebra~$\ov W^\m$ are 2-orbits of the group
generated by the sets $\aut(W_v)g_{v,v'}$, $v\in X$. This
proves the Schurity of~$W$.
To prove statement~(3) let~$\varphi:W\to W'$ be an
$ms(\W)$-isomorphism
where $\W=\W^\m$. By Lemma~\ref{isowpr} with $l=s(\W)$
we see that $\wh\varphi:\W\to\WP$ is an $s(\W)$-isomorphism.
So $\wh\varphi$ and also~$\varphi$ are induced by strong
isomorphisms.
Thus $s(W)\le ms(\W)$. To prove the second inequality we observe that
the $l$-closure of $\W$ with $l=t(\W)$ is Schurian.
This implies by Lemma~\ref{prschup} that so is the restriction of the
algebra $\W^{(lm)}$ to $\Delta^{(l)}(V^m)$. Since the
algebra~$\W^{(lm)}$
is strongly isomorphic to the restriction of the last algebra to the
set $\Delta^{(lm)}(V)$, we are done.\bull
Statements (1) and (2) of Theorem~\ref{estst} imply by induction
the following proposition where we set $W_{[U]}$ to be the cellular
closure of the algebras $W_v$, $v\in U$.
\crllr
Let $U\subset V$. Then
$$s(W)\le s(W_{[U]})+l,\quad t(W)\le\max(s(W_{[U]},t(W_{[U]})+l$$
where $l=|U|$. In particular, $s(W)\le l+1$ and $t(W)\le l+1$
whenever $s(W_{[U]})=t(W_{[U]})=1$.\bull
\ecrllr
Since the separability and Schurity numbers of a full matrix algebra
equal 1 we come to the following statement the second part of which
was proved in a different way in~\cite{EKP}. We recall that the
{\it base number} $b(W)$
of a cellular algebra~$W$ is by definition
the minimum cardinality of a base of~$W$, i.e. of a set $U\subset V$
such that $W_{[U]}=\Mat_V$.
\thrml{th47}
For any cellular algebra~$W$ we have $s(W)\le b(W)+1$ and
$t(W)\le b(W)+1$.\bull
\ethrm
It follows from \cite{B81}
that $b(W)<4\sqrt{n}\log n$ for any primitive cellular algebra
on $n$ points different from a simplex. Thus we have the following
statement.
\crllr
If $W$ is a primitive cellular algebra on $n$ points, then
$s(W)<\lceil 4\sqrt{n}\log n\rceil$ and $t(W)<\lceil
4\sqrt{n}\log n\rceil$.\bull
\ecrllr
The example of a simplex shows that $s(W)$ and $t(W)$ can be rather
far
from~$b(W)$. On the other hand, there are nontrivial examples for
which the
equalities are attained. Indeed, let~$W$ be the Bose-Mesner algebra
of
the strongly regular graph on~26 points of valency~10 marked as~$\#4$
in~\cite[p.176]{W}. Then a straightforward check shows that $b(W)=1$.
Since the group $\aut(W)$ is not transitive, the algebra~$W$ is not
Schurian
and hence $t(W)\ge 2$. In addition, $s(W)\ge 2$, because there exist
several
strongly regular graphs with the same parameters.
\section{3/2-homogeneous schemes}
\label{threetw}
\SuSS
We say that a homogeneous scheme is
{\it 3/2-homogeneous} if any two nonreflexive
basis relations of it have the same degree (called the degree of the
scheme).
There is a number of 3/2-homogeneous schemes, e.g. pseudocyclic
schemes
(see~\cite[p.42]{BCN}) and the schemes of Frobenius groups
(see~\cite{Wi}).
\thrml{tvhh}
If $\CC$ is an imprimitive 3/2-homogeneous scheme, then $s(\CC)\le 2$
and
$t(\CC)\le 2$.
\ethrm
\proof Let $W$ be the Bose-Mesner algebra of~$\CC$ and
$W'=(W_v)_{V\setminus\{v\}}$ where~$V$ is the point set of~$W$. It
follows
from \cite[Lemma~5.13]{EP} that $W'$ is a semiregular algebra. By
Theorem~\ref{simsem} we
conclude that $s(W')=t(W')=1$. So, obviously, $s(W_v)=t(W_v)=1$. Thus
the
theorem follows from statements~(1) and~(2) of
Theorem~\ref{estst}.\bull
The schemes satisfying the hypothesis of the theorem arise
for instance from Frobenius groups with non-Abelian kernel
and from cyclotomic schemes defined by a multiplicative subgroup
of the corresponding finite field contained in a proper subfield.
The case of primitive 3/2-homogeneous schemes seems to be rather
difficult. In general we can only prove that any such scheme $\CC$ is
$(d+1)$-separable and $(d+1)$-Schurian where $d$ is the degree
of~$\CC$.
Indeed, it follows from \cite[Corollary~4.8]{EP} that $b(W)\le d$
where
$W$ is the Bose-Mesner algebra of~$\CC$. Thus the above claim is the
consequence of Theorem~\ref{th47}. In the rest of this section we
confine
ourselves to Schurian schemes on a prime number of points. According
to
Burnside's theorem (see~\cite[Theorem~7.3]{Wi}) any such scheme is
isomorphic
to a cyclotomic scheme and so is primitive.
\eSuSS
Let $p$ be a prime, $d$ a divisor of~$p-1$, and~$H_d$ the
subgroup of the group $\F^*_p$ of order~$d$ where $\F_p$ is a field
with~$p$ elements. Set
\qtnl{csche}
W_{p,d}=\Z(G_{p,d})
\eqtn
where $G_{p,d}$ is the group of all affine transformations $x\mapsto
ax+b$
of~$\F_p$ such that $a\in H_d$ and $b\in \F_p$. The cellular algebra
$W_{p,d}$ is the adjacency algebra of the cyclotomic scheme
considered in~\cite{BCN}. It is a primitive one of dimension
$1+(p-1)/d$
and each of its basis relations is of the form
\qtnl{basrelcy}
R=\{(x,y):\ y-x\in cH_d,\ x,y\in \F_p\}
\eqtn
for some $c\in \F_p$. It is well-known (see~\cite[p.389]{BCN}) that
$\aut(W_{p,d})$ coincides with~$G_{p,d}$ if $d\not=p-1$. We observe
that
\qtnl{algcy}
W_{p,d}=[A(R)],\quad R\in\R\setminus\{\Delta\}
\end{equation}
where $\R=\R(W_{p,d})$ and $\Delta=\Delta^{(2)}(\F_p)$. Indeed, since
$[A(R)]\subset W_{p,d}$, the group~$\aut([A(R)])$ contains a regular
subgroup $x\mapsto x+b$, $b\in\F_p$. So by Corollary~2.10.2
of~\cite{BCN}
the algebra~$[A(R)]$ is of the form~(\ref{csche}),
whence~(\ref{algcy})
follows.
\thrml{th48}
Let $W=W_{p,d}$, $d\not=p-1$, $\W=\W^{(2)}$ and $V=\F_p$.
Then $\W_{(u,v)}=\Mat_{V^2}$ for all $(u,v)\in V^2\setminus\Delta$.
\ethrm
\proof We need the following statement.
\lmml{lemcyc}
If $d\ne 1$, then there exists an equivalence $E'\in\E(\W)$
such that $V^2/E'=\R(W')$ where $W'=W_{p,d'}$ for some
$d'$ dividing~$d$, $d'\ne d$.
\elmm
\proof We observe that $p\ne 2$ and consider two cases. If $d$
is a composite number, then it follows from
\cite[Proposition~4.1]{MT}
that there exists $d'$ dividing $d$, $d'\ne d$, such that
given $u\in V$ the set $R_u=\bigcup_{U\in\cel(W'_u)}U^2$
is a union of basis relations of the algebra $W_u$. Besides,
for all $v\in V$ we have
$(R_u)^{g_{u,v}}=R_v$ where $g_{u,v}$ is the automorphism of~$W'$ of
the form
$x\mapsto x+(v-u)$, $x\in V$. Since the 2-fold Cartesian product
of $g_{u,v}$ belongs to $\aut(\W)$ and $W_v\le r_v^{(2)}(W)$ for all
$v\in V$
(see statement~(2) of Lemma~\ref{isowfix}),
we conclude that the matrices $\sum_{v\in V}I_v\otimes A_v$
and $\sum_{v\in V}A_v\otimes I_v$ belong to $\W$ where
$A_v=A(R_v)-I_v$.
By~\cite[Lemma~4.2]{MT} the transitive closure
of the union of the relations with these adjacency matrices
is the equivalence relation on $V^2\setminus\Delta$ whose set of
classes
equals $\R(W')\setminus\{\Delta\}$. Obviously this equivalence
belongs
to~$\E(\W)$. Thus, the required equivalence $E'$ on $V^2$ can be
obtained
from it by adding a new class~$\Delta$.
If $d$ is a prime, then set $A_v$ to be the matrix of the permutation
$g_v:x\mapsto 2v-x$, $x\in V$. Then $A_v\in W_v$ for all
$v\in V$ (this follows from \cite[Theorem~4.1]{MT} for odd $d$
and is straightforward for $d=2$). So the matrices
$\sum_{v\in V}I_v\otimes A_v$ and $\sum_{v\in V}A_v\otimes I_v$
belong as
above to~$\W$. We have
$$(\sum_{u\in V}I_u\otimes A_u)(\sum_{v\in V}A_v\otimes I_v)=
\sum_{u,v\in V}I_uA_v\otimes A_uI_v=
\sum_{u,v\in V}I_{u,u^{g_v}}\otimes I_{v^{g_u},v}=$$
$$ \sum_{u,v\in V}I_{u,2v-u}\otimes I_{2u-v,v}=
\sum_{b\in V}\sum_{u,v\in V,u-v=b/2}I_{u,u+b}\otimes I_{v,v+b}$$
where $I_{x,y}$, $x,y\in V$, is a matrix unit.
Set $E'$ to be the transitive closure of the union of the set
$\Delta\times\Delta$ and the relation the adjacency matrix of which
equals the last matrix. Then it is easy to see that $E'$
is the equivalence relation on $V^2$
whose set of classes equals $\R(W_{p,1})$. Since $E'$ is obviously
an equivalence of $\W$, we are done.\bull
Let us complete the proof of the theorem. If $d=1$, then $W_{p,d}$ is
a
regular algebra and we are done. Otherwise the theorem can be deduced
from
Lemma~\ref{lemcyc} as follows. Let $U$ be the class of~$E'$
containing~$(u,v)$. Then $U\in\cel^*(\W_{(u,v)})$ and hence the
matrix
$(A_1I_UA_2)\circ J_\Delta$ equals $A(U)^\delta$ where $A(U)$
is the adjacency matrix of the relation $U\subset V^2$
and $A_1=I_V\otimes J_V$, $A_2=J_V\otimes I_V$.
So $A(U)^\delta\in\W_{(u,v)}$ and by~(\ref{algcy}) we have
$$(\W_{(u,v)})_\Delta\geq[A(U)^\delta]=[A(U)]^\delta=(W_{p,d'})^\delta.$$
Thus $\W_{(u,v)}\geq\wh{W_{p,d'}}$ according to Lemma~\ref{lstar}
and we complete the proof by induction.\bull
\thrml{oneth}
A cyclotomic scheme on a prime number of points is 4-separable.
\ethrm
\proof Let~$W$ be the adjacency algebra of such a scheme
and $\W=\W^{(2)}$.. Then~$b(\W)=1$ by Theorem~\ref{th48}.
According to Theorem~\ref{th47} we have $s(\W)\le 2$, which implies
by
statement~(3) of Theorem~\ref{estst} that~$s(W)\le 4$.\bull
\section{Extended algebras and $(\K,\LG)$-regularity of graphs}
\label{klreg}
\SuSS\label{tvercon}
By a {\it colored graph} $\G$ we mean a triple~$(V,E,c)$
where~$V=V(\G)$ is a finite set (the vertex set of~$\G$),
$E=E(\G)$ is a subset of $V^2$ (the edge set of~$\G$) and
$c=c_\G$ is a mapping from~$E$ to~$\ZZ$ (the coloring
of~$\G$). The image of an edge with respect to~$c$ is called the~{\it
color}
of this edge, the set of all edges of the same color is called
a {\it color class} of~$\G$. Two colored graphs are called {\it
isomorphic}
if there exists a bijection of their vertex sets preserving
the colors of edges. Any such bijection is called an {\it
isomorphism}
of these graphs. The group of all isomorphisms of $\G$ to itself is
denoted
by $\aut(\G)$ and called the {\it automorphism group} of~$\G$.
A colored graph $\G'$ is called a {\it subgraph} of $\G$ if
$V(\G')\subset V(\G)$, $E(\G')\subset E(\G)$ and $c_{\G'}$ is the
restriction
of~$c_\G$. If $V(\G')=U$ and $E(\G')=E(\G)\cap U^2$ for some
$U\subset V(\G)$, we say that $\G'$ is a subgraph of~$\G$ induced
by~$U$.
A mapping $g:V(\KG)\to V(\G)$ is called an {\it embedding} of a
colored
graph~$\KG$ into a colored graph~$\G$ if $E(\KG)^g\subset E(\G)$ and
$c_\G(u^g,v^g)=c_\KG(u,v)$ for all $(u,v)\in E(\KG)$. (The
mapping~$g$
is not necessarily an injection.) The set of all embeddings from
$\KG$
into~$\G$ is denoted by $\Emb(\KG,\G)$. Let $g:U\to V(\G)$ be a
mapping
from a subset~$U$ of $V(\KG)$ to~$V(\G)$. Set
\qtnl{laststaro}
q_\G(\KG,g)=|\{h\in\Emb(\KG,\G):\ h|_U=g\}|.
\eqtn
Let $\LG$ be a subgraph of~$\KG$ and $d\ge 0$ an integer.
We say that $\G$ is {\it $(\KG,\LG)$-regular} of degree $d$
if $q_\Gamma(\KG,g)=d$ for all $g\in\Emb(\LG,\G)$; we
do not refer to~$d$ if its exact value is of no interest for us.
For example, an ordinary graph is regular iff the
corresponding one-color graph~$\G$ with symmetric edge set is
$(\KG,\LG)$-regular
of the same degree where $V(\KG)=\{1,2\}$, $E(\KG)=\{(1,2)\}$,
$V(\LG)=\{1\}$, $E(\LG)=\emptyset$ and $c_{\KG}(1,2)$ equals the
color
of an edge of~$\G$.
To each cellular algebra $W$ on~$V$ we associate a colored graph
$\G=\G(W)$ with $V(\G)=V$, $E(\G)=V^2$ and colored classes
coinciding with basis relations of~$W$. We observe that this graph is
uniquely determined up to the choice of colors. Obviously, $\G$
satisfies
the 3-vertex condition. If $\CC$ is a scheme, we
set $\G(\CC)=\G(\A(\CC))$. Conversely, given a colored graph
$\G=(V,E,c)$ we set
$$W(\G)=[\{A(c^{-1}(i)):\ i\in\ZZ\}],\quad \CC(\G)=\CC(W(\G)).$$
It is easy to see that $W(\G)\le\Mat_V$, colored classes of~$\G$ are
relations of~$W(\G)$
and $\aut(W(\G))=\aut(\G)$. If $\varphi$ is a weak isomorphism
from $W(\G)$ to another cellular algebra $W'$, then we set
$\G^\varphi=(V',E',c')$ where $V'=V^\varphi$, $E'=E^\varphi$ and $c'$
is defined by $c^{-1}(i)^\varphi=(c')^{-1}(i)$, $i\in\ZZ$.
\eSuSS
Let $\G$ be a colored graph on the set $V=V(\G)$ and
$m$ be a positive integer. Given a colored graph $\KG$ with
$V(\KG)\subset[3m]$,
a subgraph $\LG$ of $\KG$ with $V(\LG)\subset[2m]$ and an integer
$d\ge 0$
we set
\qtnl{plus}
R_\G(\KG,\LG,d)=\{(\ov u,\ov v)\in (V^m)^2:\
\exists g\in\Emb(\LG,\G):\ (q_\G(\KG,g)=d\ \land\
(\ov u\cdot\ov v)_i=i^g,\ i\in V(\LG))\}
\eqtn
where $\ov u\cdot\ov v\in V^{2m}$ is the composition of~$\ov u$
and~$\ov v$.
If $m=1$ and $\G=\G(W)$ is a colored graph of a
cellular algebra~$W$, then the binary relation~(\ref{plus}) is
obviously
a union (possibly empty) of colored classes of~$\G$. (Indeed,
in this case the numbers $q_\G(\,,\,)$ equal sums
of the structure constants of~$W$). The following statement
generalizes this
observation to an arbitrary~$m$.
\thrml{mathr}
Let $\G$ be a colored graph, $W=W(\G)$ its cellular algebra
and $m$ a positive integer. Then for all admissible
$\KG,\LG,d$ the following
two statements hold:
\nmrt
\tm{1} the set $R_\G(\KG,\LG,d)$ is a relation of the algebra
$\W=\W^\m$,
\tm{2} if $\varphi$ is an $m$-isomorphism from $W$ to another
cellular algebra, then
$$R_\G(\KG,\LG,d)^{\wh\varphi}=R_{\G^\varphi}(\KG,\LG,d)$$
where $\wh\varphi=\wh\varphi^\m$ is the $m$-extension of~$\varphi$.
\enmrt
\ethrm
\proof Suppose first that $\KG=\LG$ (and so $V(\KG)\subset[2m]$) and
$d=1$.
In this case we have
$$R_\G(\KG,\LG,d)=\bigcap_{(i,j)\in E(\KG)}\wh R_{i,j}$$
where $\wh R_{i,j}=\{(\ov u,\ov v)\in (V^m)^2:\
((\ov u\cdot\ov v)_i,(\ov u\cdot\ov v)_j)\in R_{i,j}\}$
with $R_{i,j}=c_\G^{-1}(c_{\KG}(i,j))$ and $V=V(\G)$.
Thus the required statements follow from the lemma below.
\lmml{linci}
Let $W$ be a cellular algebra on~$V$ and $R\in\R(\W)$ where
$\W=\W^\m$.
Then for all $i,j\in[2m]$ the following two statements hold:
\nmrt
\tm{1} the set $\pr_{i,j}(R)=\{((\ov u\cdot\ov v)_i,(\ov u\cdot\ov
v)_j)):\
(\ov u,\ov v)\in R\}$ belongs to $\R(\ov W)$ where $\ov W=\ov W^\m$,
\tm{2} if $\varphi$ is an $m$-isomorphism from $W$ to another
cellular algebra, then
$$\pr_{i,j}(R^{\wh\varphi})=\pr_{i,j}(R)^{\ov\varphi}$$
where $\wh\varphi=\wh\varphi^\m$ and $\ov\varphi=\ov\varphi^\m$.
\enmrt
\elmm
\proof Without loss of generality we assume that $i\in[m]$,
$j\in[m+1,2m]$. (The case $i\in[m+1,2m]$, $j\in[m]$
can be treated in a similar way; the other two cases are reduced to
the case in question with $R$ replaced by $\Delta(X)$ or $\Delta(Y)$
where $X$, $Y$ are cells of $\W$ such that $R\subset X\times Y$.)
Apply Lemma~\ref{lzero} to $\W$, $R$ and the equivalences $E_1$ and
$E_2$ of $\W$ defined by the equality of the $i$th and $(j-m)$th
coordinates respectively. Then the number of the pairs
$(\ov u,\ov v)\in R$ such that $\ov u_i=u$, $\ov v_{j-m}=v$
does not depend on the choice of $(u,v)\in R_{i,j}$ where
$R_{i,j}=\pr_{i,j}(R)$. So
\qtnl{bltr}
A(R_{i,j})^\delta=cJ_\Delta\circ(A(E_1)A(R)A(E_2))
\eqtn
where $c$ is the above number. This implies that $R_{i,j}$ is a
relation of $\ov W$. In fact $R_{i,j}$ is even a basis relation.
Indeed, if $S\in\R(\ov W)$ is a proper subset of $R_{i,j}$, then
obviously the matrix $A(R)\circ(A(E_1)A(S)^\delta A(E_2))$ is not
a multiple of $A(R)$, which contradicts the assumption that
$R\in\R(\W)$. This proves statement (1). Statement (2)
is an immediate consequence of~(\ref{bltr}).\bull
Let now $\KG,\LG$ and $d$ be arbitrary. Set
$$Q=\{(\ov x,\ov y,\ov z)\in (V^m)^3:\ c_\G((\ov x\cdot\ov
y\cdot\ov z)_i,
(\ov x\cdot\ov y\cdot\ov z)_j)=c_{\KG}(i,j),\ i,j\in V(\KG)\}$$
and
\qtn
R=\pr_{1,2}(Q),\quad S=\pr_{2,3}(Q),\quad T=\pr_{1,3}(Q).
\eqtn
where $\pr_{\alpha,\beta}(Q)\subset (V^m)^2$ is the
$(\alpha,\beta)$-projection
of~$Q$, $\alpha,\beta\in[3]$. Then the set $R_\G(\KG,\LG,d)$ consists
exactly of the pairs $(\ov u,\ov v)\in (V^m)^2$ such that
\qtnl{domik}
|\{(\ov x,\ov y,\ov z): (\ov u,\ov x)\in E_1, (\ov x,\ov y)\in R,
(\ov y,\ov z)\in S,(\ov z,\ov v)\in E_2,(\ov x,\ov z)\in T\}|=
dn^{3m-|V(\KG)|}
\eqtn
where
$$E_l=\{(\ov a,\ov b)\in (V^m)^2:\ \ov a_i=\ov b_i,\ i+(l-1)m\in
V(\LG)
\},\ \ l=1,2.$$
On the other hand, it is easy to see that the integer in the left
side
of~(\ref{domik}) equals the $(\ov u,\ov v)$-entry
of the matrix $A=(A(E_1)A(R)A(S)A(E_2))\circ A(T)$. Besides, it
follows
from the definitions that each of the relations $R,S,T$ is of the
form
$R_\G(\KG',\KG',1)$ with $V(\KG')\subset[2m]$ and hence both
statements
of the theorem hold for it due to the first part of the proof. Thus,
$A\in\W$ and $R_\G(\KG,\LG,d)$ coincides with the union of those
basis relations of~$\W$ for which the coefficient at the
corresponding
basis matrix in the decomposition of~$A$ equals the integer in the
right side of~(\ref{domik}). This proves the both statements.\bull
It is convenient to weaken the property of a graph to be
$(\KG,\LG)$-regular
(see Subsection~\ref{tvercon}) as follows. Let $\KG$ be a colored
graph
with $V(\KG)\subset[3m]$ and $\LG$ a subgraph of $\KG$ with
$V(\LG)\subset[2m]$.
A colored graph $\G$ on $V$ is called $(\KG,\LG)$-regular of
degree~$d\ge 0$ with respect to a binary relation $R$ on $V^m$ if
$$R\cap R_\G(\LG)\subset R_\G(\KG,\LG,d)$$
where $R_\G(\LG)=\bigcup_{d\ge 0}R_\G(\KG,\LG,d)$. Thus, $\G$
is $(\KG,\LG)$-regular of degree~$d$ iff $\G$ is $(\KG,\LG)$-regular
of degree~$d$ with respect to $(V^m)^2$. We observe that if
$R\cap R_\G(\LG)\ne\emptyset$, then~$d$ is uniquely determined
by~$\KG,\LG$
and~$R$. Otherwise, any nonnegative integer can be taken as~$d$.
Clearly,
if~$\G$ is $(\KG,\LG)$-regular of degree~$d$ with respect to~$R_1$
and~$R_2$,
then so is~$\G$ with respect to~$R_1\cup R_2$.
In this language Theorem~\ref{mathr} sounds as follows.
\crllrl{crl73}
Let $\G,W,m,\varphi$ and $\wh\varphi$ be as in Theorem~\ref{mathr}.
Then
\nmrt
\tm{1} $\G$ is $(\KG,\LG)$-regular with respect to any basis relation
of
$\W$ for all admissible $\KG,\LG$,
\tm{2} if $\G$ is $(\KG,\LG)$-regular with respect to some relation
$R$ of
$\W$, then $\G^\varphi$ is $(\KG,\LG)$-regular of the same degree
with
respect to $R^{\wh\varphi}$.\bull
\enmrt
\ecrllr
\eSuSS
\label{tvetc}
In this subsection we use the above technique to analyze the
$t$-vertex
condition of graphs. This notion was introduced for strongly regular
graphs in~\cite{Hi70} and generalized to colored graphs
in~\cite{FKM}.
In fact the latter deals with complete colored graphs~$\G$, i.e.
those with
$E(\G)=V(\G)^2$. Namely, let $t\ge 2$ be a positive integer. A
complete
colored graph~$\G$ satisfies the {\it $t$-vertex condition} if given
a
complete colored graph~$\KG$ with $V(\KG)=[k]$, $2\le k\le t$, the
number~$q^*_\G(\KG,g_{u,v})$ depends only on $c_\G(u,v)$ for all
$u,v\in V(\G)$
where $g_{u,v}:[l]\to\{u,v\}$ with $l=|\{u,v\}|$ is the bijection
taking~$1$ to~$u$ and $q^*_\G(\KG,g_{u,v})$ is defined similarly to
$q_\G(\KG,g_{u,v})$ with additional assumption in~(\ref{laststaro})
that~$h$ is an injection.
(In terms of~\cite{FKM} the integer $q^*_\G(\KG,g_{u,v})$ divided by
the
order of the subgroup of~$\aut(\KG)$ leaving fixed the points
of~$[l]$, equals the number
of the subgraphs of~$\G$ of the type~$\KG$ with respect to the
pair~$(u,v)$.) It is convenient to extend this definition to an
arbitrary colored graph~$\G$
allowing~$\KG$ to be an arbitrary colored graph on~$[k]$
and replacing
%~$g^*_{u,v}$ by the mapping
%$g_{u,v}:[2]\to\{u,v\}$ taking~$1$ to~$u$ and~$2$ to~$v$,
%and
$q^*_\G(\KG,g_{u,v})$ by $q_\G(\KG,g_{u,v})$.
This does not lead to confusion because it is easy to see that for a
complete
colored graph~$\G$ any number~$q_\G(\KG,g_{u,v})$
equals a linear combination of the numbers $q^*_\G(\KG',g_{u,v})$
for some complete colored graphs $\KG'$ with
$|V(\KG')|\le|V(\KG)|$. One can see that according to
the last definition a colored graph~$\G$ satisfies the $t$-vertex
condition
iff $\G$ is $(\KG,\LG)$-regular for all colored graphs~$\KG$
with at most $t$ vertices and all its subgraphs $\LG$ with
$V(\LG)=\{i,j\}$
and $E(\LG)=\{(i,j)\}$. Clearly, we can assume that $V(\KG)\subset
[t]$ and
$V(\LG)\subset [2]$.
\thrml{mcondth}
A colored graph associated with an $m$-closed cellular algebra
satisfies
the $3m$-vertex condition.
\ethrm
\proof Let $\G$ be a colored graph satisfying the hypothesis of the
theorem. Then it suffices to prove that $\G$ is $(\KG,\LG)$-regular
for
all $\KG,\LG$ with $V(\KG)\subset[3m]$, $V(\LG)=\{i,j\}\subset[2m]$
and $E(\LG)=\{(i,j)\}$. By statement~(1) of Corollary~\ref{crl73}
the graph~$\G$ is $(\KG,\LG)$-regular of some degree~$d_R$ with
respect to
any $R\in\R(\W^\m)$. It follows from statement~(1) of
Lemma~\ref{linci}
and the assumption on~$\LG$ that $d_R$ can be chosen not depending
on~$R$. Denoting this number by~$d$ we see that the graph~$\G$ is
$(\KG,\LG)$-regular of degree~$d$ with respect to $(V^m)^2$,
i.e. $(\KG,\LG)$-regular.\bull
{\bf Proof of Theorem~\ref{ndivtr}.}
Let $\G$ be a colored graph of~$W$
and $m=\lceil n/3\rceil$. Denote by~$\KG$ a colored graph on the
set~$[n]$
isomorphic to~$\G$. Then by statement~(1) of Corollary~\ref{crl73}
the
graph~$\G$ is $(\KG,\LG)$-regular of positive degree with respect to
some
basis relation~$R$ of~$\W^\m$ where~$\LG$ is the graph without
vertices.
Statement~(2) of Corollary~\ref{crl73} shows then that given
any weak isomorphism~$\varphi$ from~$W$ to another cellular algebra
the graph~$\G^\varphi$ is also $(\KG,\LG)$-regular of the same
positive
degree with respect to~$R^\varphi$. This means that~$\G^\varphi$ is
isomorphic to~$\KG$ and also that~$\varphi$ is induced by the
composition isomorphism from~$\G$ to~$\G^\varphi$ via~$\KG$.
Thus $s(W)\le m$. Further, according to Theorem~\ref{mcondth} a
colored graph associated with the $m$-closure of~$W$ satisfies the
$3m$-vertex condition and hence the $n$-vertex condition because
$n\le 3m$. So this graph is associated with a Schurian cellular
algebra by~\cite[Proposition~2.6.2]{FKM}. Thus $t(W)\le m$.\bull
\section{Distance-regular graphs}
\label{applic}
\SuSS\label{appli1}
Throughout the section we use notation
from Section~\ref{klreg}. A colored graph with symmetric one-color
edge set not meeting the diagonal is treated below as a graph in
sense of~\cite{BCN}.
Let $\G$ be a connected graph with vertex set $V$ and edge set $R$.
Let us denote by $R_i$, $i\in[0,d]$, the binary relation on~$V$
``to be at distance~$i$ in $\G$'', where $d$ is the diameter
of~$\G$. In particular, $R_0=\Delta^{(2)}(V)$, $R_1=R$. According to
\cite[Chapter 1]{BCN} the graph $\G$ is called {\it distance-regular}
if $\CC(\G)=(V,\{R_i\}_{i=0}^d)$ where $\CC(\G)$ is the
scheme of~$\G$. In this case the intersection
numbers of~$\CC(\G)$ are uniquely determined by a part of them,
namely by $c_{R,R_i}^{R_{i-1}}$ and $c_{R,R_{i-1}}^{R_i}$, $i\in[d]$,
called the {\it intersection numbers} or {\it parameters} of~$\G$.
The cellular algebra $W(\G)$ (coinciding
with the Bose-Mesner algebra of~$\CC(\G)$) equals
$\C[A_0,\ldots,A_d]=\C[A_1]$ where $A_i=A(R_i)$, $i\in[0,d]$.
In particular, $\M(W(\G))=\{A_i\}_{i=0}^d$.
If distance-regular graphs $\G$ and $\G'$ have the same
intersection numbers, then the mapping $A_1\mapsto A'_1$ yields
a weak isomorphism from $W(\G)$ to $W(\G')$ taking $A_i$
to $A'_i$, $i\in[0,d]$. Conversely, if $\varphi$ is a weak
isomorphism
from $W(\G)$ to another cellular algebra $W'\le\Mat_{V'}$, then
the corresponding structure constants of $W(\G)$ and $W'$ coincide
and so by \cite[Proposition 2.7.1]{BCN} the graph
$\G^\varphi=(V',R^\varphi)$ is distance-regular,
$(R^\varphi)_i=(R_i)^\varphi$, $i\in[0,d]$, the parameters of $\G$
and $\G^\varphi$ coincide and $W'=W(\G^\varphi)$.
Following \cite{BCN} we say that a distance-regular graph $\G$ is
{\it uniquely determined by parameters} if its intersection numbers
determine $\G$ up to isomorphism. Also $\G$ is called
{\it distance-transitive}, if the group $\aut(\G)$ acts transitively
on any of the sets $R_i$, $i\in[0,d]$. Thus the following statement
trivially holds.
\prpstnl{estar}
Let $\G$ be a distance-regular graph and $\CC=\CC(\G)$. Then
\nmrt
\tm{1} $\G$ is uniquely determined by parameters iff $s(\CC)=1$,
\tm{2} $\G$ is distance-transitive iff $t(\CC)=1$.\bull
\enmrt
\eprpstn
Below we assume that the relation $R_i$ of the scheme
$\CC$ associated with a distance-regular graph $\G$ has color $i$
in the colored graph~$\G(\CC)$.
\eSuSS
Let $n,k$ be nonnegative integers, $k\le n$. The graph $\G=J(n,k)$
the vertices of which are $k$-subsets of $[n]$ and the edges are
pairs $(u,v)$ with $|u\cap v|=k-1$ is called a {\it Johnson graph}.
It is known that $\G$ is a distance-transitive graph of
diameter $d=\min(k,n-k)$. According to \cite[Section 9.1.B]{BCN} this
graph is uniquely determined by parameters unless $(n,k)=(8,2)$.
In the last case any distance-regular graph with the same parameters
as~$\G$ is isomorphic either to~$\G$ or to one of the three
Chang graphs which are not distance-transitive (see
\cite[p.105]{BCN}).
Below by $\J(n,k)$ we denote the scheme of the graph $\G$ and
call it a Johnson scheme. Similarly, the scheme of a Chang graph will
be called a Chang scheme.
\thrml{stjsc}
Let $\CC$ be the scheme of a distance-regular graph with parameters
of
some Johnson graph. Then $s(\CC)\le 2$ and $t(\CC)\le 2$. More
exactly,
\nmrt
\tm{1} if $\CC=\J(n,k)$, then
$$s(\CC)=\cases{1,&if $(n,k)\ne(8,2)$;\cr 2,&otherwise\cr}$$
and $t(\CC)=1$ for all $n,k$,
\tm{2} if $\CC$ is a Chang scheme, then $s(\CC)=t(\CC)=2$.
\enmrt
\ethrm
\proof It follows from the above discussion and
Proposition~\ref{estar}
that statement~(1) holds for $(n,k)\ne(8,2)$ and also that $s(\CC)\ge
2$,
$t(\CC)=1$ if $\CC=\J(8,2)$ and $s(\CC)\ge 2$, $t(\CC)\ge 2$ if $\CC$
is
a Chang scheme. Using a computer it can be shown that the 2-closures
of
the cellular algebras associated with the Chang graphs are Schurian
and their
dimensions are 11, 12 and 14. The first part means that $t(\CC)=2$ if
$\CC$ is a Chang scheme. The second part implies that these
algebras are not 2-isomorphic to each other and
to the cellular algebra associated with~$J(8,2)$.
Thus, $s(\CC)=2$ if $\CC=\J(8,2)$ or $\CC$ is a Chang scheme.\bull
\eSuSS
Let $d\ge 0$ and $q\ge 2$ be integers. Let us define the {\it Hamming
graph}
$\G=H(d,q)$ to be the product of $d$ copies of the complete graph on
the
set $X=[q]$. This means that $\G$ has vertex set $X^d$
and two vertices of $\G$
are adjacent iff they differ in precisely one coordinate. It is
known that $\G$ is a distance-transitive graph of diameter~$d$.
According to \cite[Section 9.2.B]{BCN} it is uniquely determined by
parameters unless $q=4$, $d\ge 2$. If $q=4$, then any
distance-regular
graph having the same parameters as $\G$ is isomorphic to the
graph~$D_{a,b}$
which is the direct product of $a$ copies of the Shrikhande graph
(see \cite[p.104]{BCN}) and $b$ copies of the complete graph on 4
vertices,
where $a\ge 0, b\ge 0$ are some integers with $2a+b=d$. Obviously,
$\G=D_{0,d}$. If $a\ge 1$, then the graph $D_{a,b}$ is not
distance-transitive. It is called a Doob graph.
Below the scheme of the Hamming graph $H(d,q)$ will be denoted by
$\H(d,q)$
and the scheme of the graph $D_{a,b}$ by $\D_{a,b}$. Thus
$\H(d,4)=\D_{0,d}$. The following theorem is an immediate consequence
of the above discussion, Proposition~\ref{estar} and Lemma~\ref{dgrl}
below.
\thrml{hsst}
Let $\CC$ be the scheme of a distance-regular graph with parameters
of some Hamming graph. Then $s(\CC)\le 2$ and $t(\CC)\le 2$. More
exactly,
\nmrt
\tm{1} if $\CC=\H(d,q)$, then
$$s(\CC)=\cases{1,&if $q\ne 4$ or $d\le 1$;\cr
2,&otherwise\cr}$$
and $t(\CC)=1$ for all $d,q$,
\tm{2} if $\CC$ is a scheme of a Doob graph, then
$s(\CC)=t(\CC)=2$.\bull
\enmrt
\ethrm
Let $V_{a,b}$ and $R_{a,b}$ be the vertex set and the edge set of the
graph $D_{a,b}$. Set $\Delta_{a,b}=\Delta^{(2)}(V_{a,b})$,
$G_{a,b}=\aut(D_{a,b})$ and $W_{a,b}=W(D_{a,b})$.
\lmml{dgrl}
The following two statements hold:
\nmrt
\tm{1} the sets $R_{a,0}\times\Delta_{0,b}$ and $\Delta_{a,0}\times
R_{0,b}$
are relations of the algebra $\ov W_{a,b}=\ov{W_{a,b}}^{(2)}$.
Moreover,
\qtnl{ldcon}
\ov W_{a,b}=\Z(G_{a,0})\otimes\Z(G_{0,b}).
\eqtn
\tm{2} If $\varphi$ is a 2-isomorphism from $W_{a,b}$ to $W_{a',b'}$
and $(R_{a,b})^\varphi=R_{a',b'}$, then
$$(R_{a,0}\times\Delta_{0,b})^{\ov\varphi}=R_{a',0}\times\Delta_{0,b'},\quad
(\Delta_{a,0}\times R_{0,b})^{\ov\varphi}=\Delta_{a',0}\times
R_{0,b'}$$
where $\ov\varphi=\ov\varphi^{(2)}$. Moreover, $a=a'$ and $b=b'$.
\enmrt
\elmm
\proof Let $\G=\G_{a,b}$ be a colored graph associated with $W_{a,b}$
and $\KG$ be the complete graph
with $V(\KG)=[4]$ all edges of which have the color of the relation
$R_{a,b}$. It is easy to see that given $g\in\Emb(\KG,\G)$ the
vertices
of the image of~$g$ differ in one fixed coordinate. So the number
$q_\G(\KG,g)$ equals the corresponding number for the Shrikhande
graph
($\G=\G_{1,0}$) or the complete graph on 4 vertices ($\G=\G_{0,1}$)
depending on whether the pair $(1^g,2^g)$ belongs to
$R_{a,0}\times\Delta_{0,b}$ or $\Delta_{a,0}\times R_{0,b}$. Since
the last numbers equal 0 and 2 respectively, we see that
\qtnl{istar}
R_{a,0}\times\Delta_{0,b}=\pr_{1,2}(R(\KG,\LG,0))\cap R_{a,b},\quad
\Delta_{a,0}\times R_{0,b}=\pr_{1,2}(R(\KG,\LG,2))\cap R_{a,b}
\eqtn
where $\LG$ is the subgraph of $\KG$ induced by the set $[2]$, the
relation $R(\KG,\LG,d)$, $d=0,2$, is defined according
to~(\ref{plus})
and $\pr_{i,j}(R)$ is as in statement~(1) of Lemma~\ref{linci}.
Thus the first part of
statement~(1) follows from the first statements of
Theorem~\ref{mathr}
and Lemma~\ref{linci}. Equalities~(\ref{istar})
due to the second statements of Theorem~\ref{mathr} and
Lemma~\ref{linci}
also imply the first part of statement~(2).
The second part follows from the
first one, the obvious equalities $d(R_{a,0}\times\Delta_{0,b})=6a$,
$d(\Delta_{a,0}\times R_{0,b})=3b$ and statement (1) of
Lemma~\ref{aisowpr}.
Let us prove formula (\ref{ldcon}). Without loss of generality we
assume
that $a>0$. It is well-known that the Shrikhande graph $D_{1,0}$ is
edge-transitive and the edge set of its complement is split into
two 2-orbits of the group $\aut(D_{1,0})$ of degrees~$6$ and~$3$.
Denote them
by~$S_{1,0}$ and~$T_{1,0}$ respectively. Let $S_{a,0}$ (resp.
$T_{a,0}$)
be the edge set of the direct product of $a$ copies of the graph
with the edge set $S_{1,0}$ (resp. $T_{1,0}$). We will show first
that the sets
$S_{a,b}=S_{a,0}\times\Delta_{0,b}$ and
$T_{a,b}=T_{a,0}\times\Delta_{0,b}$
are relations of the algebra~$\ov W_{a,b}$.
Denote by $\KG'$ the graph obtained from $\KG$ by recoloring the
pairs
$(1,2)$ and $(2,1)$ in the color of the relation $R'_{a,b}$
``to be at distance 2 in the graph~$D_{a,b}$''. As above it is easy
to
see that given $g\in\Emb(\KG',\G)$ the number $q_\G(\KG',g)$ equals 2
or 0
depending on whether the pair $(1^g,2^g)$ belongs to
$S_{a,b}$ or $R'_{a,b}\setminus S_{a,b}$. So
$$S_{a,b}=\pr_{1,2}(R(\KG',\LG',2))\cap R'_{a,b}$$
where $\LG'$ is the subgraph of $\KG'$ induced by the set $[2]$. Thus
$S_{a,b}$ is a relation of~$\ov W_{a,b}$. A straightforward
computation shows that
$$A(R'_{a,b})\circ(A(R_{a,0}\times\Delta_{0,b})\cdot A(S_{a,b}))=
2aA(S_{a,b})+4aA(T_{a,b})+A(T')$$
where $T'=R'_{a,b}\setminus (S_{a,b}\cup T_{a,b})$. Since the left
side belongs to~$\ov W_{a,b}$, we conclude that $A(T_{a,b})\in\ov
W_{a,b}$,
which proves the claim.
Now it follows from above that the algebra $\ov W_{a,0}$ contains
the adjacency matrices of the relations $R_{a,0}$, $S_{a,0}$
and $T_{a,0}$ and hence the smallest cellular algebra containing
them.
However the last algebra coincides with the exponentiation
$\ov W_{1,0}\uparrow \sym(a)$ of $\ov W_{1,0}$ by $\sym(a)$
as defined in~\cite{EP}. By \cite[Theorem 3.4 and formula (5)]{EP}
we have $\ov W_{a,0}=\Z(G_{a,0})$. This implies that $\ov W_{a,b}$
contains $\Z(G_{a,0})\otimes\{I_{V_{0,b}}\}$. On the other hand,
by the second of the equalities~(\ref{istar}) and the
distance-transitivity
of $D_{0,b}$ we see that it also contains
$\{I_{V_{a,0}}\}\otimes\Z(G_{0,b})$.
Thus $\ov W_{a,b}\ge \Z(G_{a,0})\otimes\Z(G_{0,b})$. Since
the converse inclusion is obvious, we are done.\bull
The following assertion immediately follows from statement~(2) of
Lemma~\ref{dgrl}.
\crllr
The Doob graphs are pairwise nonisomorphic and nonisomorphic to
the corresponding Hamming graph.\bull
\ecrllr
\rmrk
It follows from the proof of Lemma~\ref{dgrl} that the
graphs~$D_{a,b}$
can be distinguished by means of the 4-vertex condition.
\ermrk
\eSuSS
Let $\F$ be a finite field with $q$ elements, $n,k$ be nonnegative
integers, $k\le n$. The graph $\G=J_q(n,k)$ the vertices of which
are $k$-subspaces of the $n$-dimensional linear space over $\F$ and
the edges are pairs $(u,v)$ with $\dim(u\cap v)=k-1$, is called
a {\it Grassmann graph}. It is known that $\Gamma$ is a
distance-transitive
graph of diameter $d=\min(k,n-k)$. According to \cite[p.272]{BCN}
this
graph is uniquely determined by parameters for ${2\over{3}}n\le k\le
n-3$,
$(q,k)\not=(2,{2\over{3}}n)$.
\thrml{grasch}
Let $\CC$ be the scheme of the Grassmann graph $J_q(n,k)$. Then
$s(\CC)\le 2$ and $t(\CC)=1$ for all $q,n,k$. Moreover, $s(\CC)=1$
whenever ${2\over{3}}n\le k\le n-3$, $(q,k)\not=(2,{2\over{3}}n)$.
\ethrm
\proof By Proposition \ref{estar} it suffices to prove that
$s(\CC)\le 2$. One can easily find (see also \cite[Section 9.3]{BCN})
that the graph $\G=J_q(n,k)$ satisfies the following two conditions:
\nmrt
\tm{1} given two vertices $u,v$ of $\G$ at distance 2, the subgraph
of~$\G$ induced by the set of vertices adjacent simultaneously to~$u$
and~$v$ is isomorphic to the Hamming graph $H(2,q+1)$,
\tm{2} given three pairwise nonadjacent vertices $u,v,w$ of $\G$,
the subgraph of~$\G$ induced by the set of vertices adjacent
simultaneously to $u,v$ and~$w$ has no edges.
\enmrt
This means that the colored graph of the scheme $\CC(\G)$ is
$(\KG_i,\LG_i)$-regular of degree $d_i$, $i\in[6]$, where
$$(\KG_i,\LG_i,d_i)=\cases{
(K_{2,1},K_2,(q+1)^2), &if $i=1$;\cr
(K_{2,1,1},K_{2,1},2q), &if $i=2$;\cr
(K_{2,1,1,1},K_{2,1,1},q-1), &if $i=3$;\cr
(K_{2,2,1},K_{2,2},2), &if $i=4$;\cr
(K_{2,2,1,1},K_{2,2},0), &if $i=5$;\cr
(K_{3,1,1},K_{3,1},0), &if $i=6$\cr
}$$
and $K_{n_1,\ldots,n_s}$ is the complete multipartite graph with
parts
$[N_{i-1}+1,N_{i-1}+n_i]$, $i\in[s]$, where $N_i=\sum_{j=1}^in_j$.
\footnote{Thus $K_n$ denotes the graph on the set $[n]$ with no
edges, i.e. $\ov K_n$ in notation of~\cite{BCN}.}
(Here each pair of distinct vertices of the graph $\KG_i$ has the
color
of the adjacency relation of~$\G$ if these vertices are adjacent
in~$\KG_i$,
and the color of the relation ``to be at distance 2 in $\G$'' if they
are
not.) Indeed, the $(\KG_i,\LG_i)$-regularity of degree $d_i$,
$i\in[4]$,
means that the subgraph from condition~(1) is a strongly regular
graph
with parameters $((q+1)^2,2q,q-1,2)$. It is well-known that this
graph
is isomorphic to $H(2,q+1)$ for $q\ne 3$ (see~\cite[p.92]{BL}).
In addition, if $q=3$, then it is isomorphic
to $H(2,4)$ or to the Shrikhande graph. However, the last graph is
not $(K_{2,1,1},K_2)$-regular of degree~0. So the
$(\KG_i,\LG_i)$-regularity
of degree $d_i$, $i\in[5]$, is equivalent to condition~(1). Finally,
the $(\KG_6,\LG_6)$-regularity of degree~0 is obviously equivalent
to condition~(2).
Let $\varphi$ be a 2-isomorphism of the algebra $W=W(\G)$ to another
cellular algebra~$W'$. Then $W'=W(\G')$ where $\G'=\G^\varphi$ is
a distance-regular graph with the same parameters as~$\G$. It follows
from statement~(2) of Corollary~\ref{crl73} that $\G'$ is
$(\KG_i,\LG_i)$-regular of degree $d_i$ for all $i\in[6]$. So $\G'$
satisfies conditions~(1) and~(2). This implies by \cite[Corollary
9.3.8]{BCN}
that it is isomorphic either to a complete graph, or a Johnson graph,
or the quotient of the Johnson graph $J(2k,k)$ obtained by
identifying a
$k$-set with the image of its complement under the identity mapping
or an involution
in $\sym(2k)$ with at least 10 fixed points or a Grassman graph over
a
finite field. Since $q+1>2$, we see that $\G'$ is isomorphic to
$J_q(n,k)$. Thus $\varphi\in\isow_\infty(W,W')$.\bull
It should be remarked that there is a number of distance-regular
graphs
with parameters of Grassmann graphs and nonisomorphic to them. For
example, given an arbitrary finite group~$G$ there exists a strongly
regular graph with the same parameters as $J_2(n,2)$ for some~$n$
and the automorphism group isomorphic to~$G$ (see~\cite{M}).
Finally, we notice that the 2-separability of the scheme $\J_q(n,2)$
for $n\ge 6$ follows also from \cite[Lemma~5]{Hi70} and
Theorem~\ref{mcondth}.
\eSuSS\label{ivasec}
In this subsection we find the Schurity numbers of the coherent
configurations associated with some strongly regular graphs. The
computation is based on the following lemma.
\lmml{ieeq}
Let $W$ be a cellular algebra and $m$ a positive integer.
Assume that any cellular algebra lying between $W$ and $\ov
W^{(\infty)}$
the colored graph of which satisfies the $3m$-vertex condition,
coincides
with~$\ov W^{(\infty)}$. Then $t(W)\le m$.
\elmm
\proof According to Theorem \ref{mcondth} the colored graph
associated with
the algebra $\ov W^{(m)}$ satisfies the $3m$-vertex condition. By the
lemma's hypothesis this implies that $\ov W^{(m)}=\ov
W^{(\infty)}$.\bull
Let $\G$ be a strongly regular graph with the automorphism group of
rank~4. Then there are exactly two cellular algebras between $W$
and $\ov W^{(\infty)}$ where $W=W(\G)$. So the hypothesis of
Lemma~\ref{ieeq}
is satisfied for $m=2$ unless $\G$ satisfies the 6-vertex condition.
In this case it follows that $t(W)\le 2$. Since obviously $t(W)>1$,
we conclude that $t(W)=2$. Such a situation arises, for instance, if
$\G$ is the Shrikhande graph, one of the graphs from~\cite[Theorem
1]{BIK}
for $m\ge 3$, $q>2$, or the graph on 256 vertices found by
A.~V.~Ivanov
(see~\cite{I}). The last graph is especially interesting, since
it is the only known to the authors strongly regular non rank 3 graph
satisfying the 5-vertex condition. As it was remarked in
\cite[p.74]{FKM} this graph does not satisfy the 6-vertex condition.
\eSuSS
Let $\P$ be a finite projective plane of order $q$ with the point set
$P$
and the line set $L$ (see~\cite{D}). Denote by $\G=\G(\P)$ the
bipartite
graph with parts $P$ and $L$ and edge set defined by the incidence
relation of~$\P$.
It is easy to see that~$\G$ is a distance-regular graph of diameter~3
and valency~$q+1$. Moreover, any distance-regular graph with the
same parameters as~$\G$ is of the form $\G(\P')$ for some projective
plane~$\P'$ of order~$q$.
\thrml{projplane}
Let $\P$ be a projective plane of order $q$ and $\CC$ be the scheme
associated with the graph $\G=\G(\P)$. Then
\nmrt
\tm{1} $s(\CC)\le O(\log\log q)$ and $t(\CC)\le O(\log\log q)$,
\tm{2} $t(\CC)=1$ iff $\P$ is a Galois plane,
\tm{3} $s(\CC)\le 6$ whenever $\P$ is a Galois plane.
\enmrt
\ethrm
\proof A subset of $P\cup L$ is called a closed set of $\P$ if it
contains each line (resp. each point) incident to two different
points (resp. lines) of it. If $P\cup L$ is the minimal closed
set of $\P$ containing a set $X\subset P\cup L$, we say that
$X$ is a generating set for $\P$. It is easy to see that
any generating set of $\P$ is a base of the cellular algebra
$W=W(\G)$.
Now it follows from \cite[Theorem 3.2.17]{D} that a Galois plane is
generated
by a quadrangle and a suitable point on one of its sides. So if $\P$
is a
Galois plane, then $b(W)\le 5$ and statement (3) is the consequence
of
Theorem~\ref{th47}. It follows from \cite[Theorem 3.2.18]{D} that
given a projective plane $\P$ of order~$q$ any proper closed set
of~$\P$
containing a quadrangle is a subplane of~$\P$ of order at most
$\sqrt{q}$.
Thus we conclude by induction that $b(W)\le O(\log\log q)$ and so
statement~(1) follows from Theorem \ref{th47}. Finally,
the Ostrom-Wagner Theorem implies that $\P$ is a Galois plane
iff the subgroup of $\aut(W)$ leaving fixed $P$ (as a set) acts
2-transitively on $P$ (see \cite[Theorems 4.4.20, 1.4.5]{D}). Since
the
latter is a necessary condition for the Schurity of~$W$,
statement~(2)
follows.\bull
\section{Appendix}
\label{appnd}
\SuSS
Throughout the section let $m$ be a positive integer, $W\le\Mat_V$
be a cellular algebra, $\W=\W^\m$, $\ov W=\ov W^\m$ and
$\Delta^{(i)}=\Delta^{(i)}(V)$ for all~$i$.
Let $\wh E=\wh E^\m=\wh E^\m(W)$ and $E=E^\m=E^\m(W)$ be the
equivalences
with supports~$V^m$ and~$\Delta^{(m-1)}\times V$ defined by the
equality
of the $m$th coordinates. Since $\W\ge\Z_m(V)$, we see that $\wh
E,E\in\E(\W)$.
It is easy to see that $\wh E\supset E$ and their classes are of
the form
\qtnl{loc11f}
\wh U_v=V^{m-1}\times\{v\},\quad U_v=\Delta^{(m-1)}\times\{v\}
\eqtn
respectively where $v\in V$. Besides, it follows from the definitions
that
$\W_{\wh E}\subset\sum_{v\in V}\Mat_{V^{m-1}}\otimes\{I_v\}$
and $\W_E\subset\sum_{v\in V}\Mat_{\Delta^{(m-1)}}\otimes\{I_v\}$.
For $X\subset V$ set
\qtnl{blbox}
\wh E_X=\bigcup_{v\in X}(\wh U_v)^2,\quad E_X=\bigcup_{v\in
X}(U_v)^2.
\eqtn
\lmml{clone}
The mapping $X\mapsto\wh E_X$ (resp. $X\mapsto E_X$) defines a
bijection
between the cells of~$\ov W$ and the indecomposable components of the
equivalence~$\wh E$ (resp.~$E$).
\elmm
\proof It suffices to verify that if $X\in\cel(\ov W)$, then $\wh
E_X$
and $E_X$ are indecomposable equivalences of~$\W$. It follows from
Lemma~\ref{lstar} that the set $R=(V^{m-1}\times X)^2$ is a relation
of~$\W$. Since $\wh E_X=\wh E\cap R$ and $E_X=E\cap R$, we conclude
that
$\wh E_X$ and $E_X$ are equivalences of~$\W$. Further, if
$\wh E_Y$ (resp. $E_Y$) is an indecomposable component of $\wh E_X$
(resp. $E_X$), then $Y$ is a cellular set of~$\ov W$ by statement~(1)
of
Lemma~\ref{linci} with $R=\wh E_Y$ (resp. $R=E_Y$) and $i=j=m$. Thus
$Y=X$
and we are done.\bull
For $v\in V$ and $m\ge 2$ set
$$\wh r_v(W)=\wh r_v^\m(W)=(\W_{\wh E,\wh
U_v})^{\wh\zeta^{-1}_v},\quad\
r_v(W)=r_v^\m(W)=(\W_{E,U_v})^{\zeta^{-1}_v}
$$
where $\wh\zeta_v:V^{m-1}\to\wh U_v$ and $\zeta_v:V\to U_v$ are
natural
bijections.
\lmml{schteo}
In the above notation the following statements hold:
\nmrt
\tm{1} the algebra $r_v(W)$ is $(m-1)$-closed and also the algebra
$\wh r_v(W)$ contains the $(m-1)$-extended algebra of $r_v(W)$,
\tm{2} $r_v(W)\ge \ov{W_v}\mathstrut{}^{(m-1)}$ and\
$\wh r_v(W)\ge \wh{W_v}\mathstrut{}^{(m-1)}$.
\enmrt
\elmm
\proof It is easy to see that
\qtnl{trequ}
\wh r_v(W)\ge(\Z_m(V)_{\wh E,\wh U_v})^{\wh\zeta_v^{-1}}=
\Z(\sym(V)_v,V^{m-1})\ge\Z_{m-1}(V)
\eqtn
where $\sym(V)_v$ is the subgroup of $\sym(V)$ fixing~$v$ and its
action
on~$V^{m-1}$ is given coordinatewise.
So statement~(1) follows from Lemma~\ref{lstar} with $W'=\wh r_v(W)$
and~$m-1$ instead of~$m$. Further, by statement~(1) it suffices to
prove
only the
first inequality of statement~(2). It follows from (\ref{defmext})
that the algebra~$W^{m-1}\otimes\{I_V\}$ is contained
in~$\W$ and hence in $\W_{\wh E}$. So by (\ref{trequ}) we have
$\W^{(m-1)}\le\wh r_v(W)$ and hence
$W\le r_v(W)$. Besides, $I_{(v,\ldots,v)}=(I_{\wh U_v}I_\Delta I_{\wh
U_v})^{\wh\zeta_v^{-1}}$
whence $I_v\in r_v(W)$. Thus
$$r_v(W)=(\wh r_v(W)_{\Delta^{(m-1)}})^{\delta^{-1}}\ge [W,
I_v]=W_v$$
where $\delta:V\to\Delta^{(m-1)}$ is a natural bijection.\bull
\eSuSS\label{subs82}
Let $\varphi\in\isow_m(W,W')$. Then $\wh E^{\wh\varphi}=\wh E'$ and
$E^{\wh\varphi}=E'$ where $\wh E'=\wh E^\m(W')$ and $E'=E^\m(W')$
(see Lemma~\ref{aisowpr}). Let $(v,v')\in X\times X'$ where
$X\in\cel(\ov W)$, $X'\in\cel(\ov{W'})$ with $X^{\ov\varphi}=X'$.
Then by statement~(2) of Lemma~\ref{linci} we have
$\wh F^{\wh\varphi}=\wh F'$ and $F^{\wh\varphi}=F'$ where $\wh F=\wh
E_X$,
$\wh F'=\wh E'_{X'}$ and $F=E_X$, $F'=E'_{X'}$ (see~(\ref{blbox})).
By
Lemma~\ref{clone} these equivalences are indecomposable: $\wh F$
and $F$ in~$\W$, whereas $\wh F'$ and $F'$ in~$\WP$. Set
$$
\wh\varphi_{\wh U\mathstrut{}_v,\wh U'\mathstrut{}_{v'}}=
\pi_{\wh F',\wh U'\mathstrut{}_{v'}}\circ
\wh\varphi_{\wh F}\circ\pi^{-1}_{\wh F,\wh U_{v}},\quad
\varphi_{U_v,U'\mathstrut{}_{v'}}=\pi_{F',U'\mathstrut{}_{v'}}\circ
\wh\varphi_F\circ\pi^{-1}_{F,U_{v}}
$$
where $\wh\varphi_{\wh F}:\W_{\wh F}\to\WP_{\wh F'}$ and
$\wh\varphi_F:\W_F\to\WP_{F'}$ are the restriction isomorphisms
induced by
$\wh\varphi$, and $\wh U'\mathstrut{}_{v'}$ and $U'\mathstrut{}_{v'}$
are the
classes of the equivalences $\wh F'$ and~$F'$ corresponding to~$v'$.
Then
the mappings
\qtnl{defisow}
\wh r_{v,v'}(\varphi)=(\wh\chi\mathstrut{}_{v'})^{-1}\circ
{\wh\varphi}_{\wh U_v,\wh U'\mathstrut{}_{v'}}\circ
\wh\chi\mathstrut{}_v,
\quad
r_{v,v'}(\varphi)=(\chi\mathstrut{}_{v'})^{-1}\circ
{\varphi}_{U_v,U'\mathstrut{}_{v'}}\circ \chi\mathstrut{}_v
\eqtn
belong to $\isow(\wh r_v(W),\wh r\mathstrut{}_{v'}{W'})$ and
$\isow(r_v(W),r\mathstrut{}_{v'}(W'))$ respectively where
$\wh\chi_v:\wh r_v(W)\to\W_{\wh F,\wh U_v}$ and
$\chi_v:r_v(W)\to\W_{F,U_v}$ are the weak isomorphisms induced by
the bijections $\wh\zeta_v$ and $\zeta_v$, and
$\wh\chi\mathstrut{}_{v'}$, $\chi\mathstrut{}_{v'}$ are defined
similarly.
\lmml{isowfix}
In the above notation the following statements hold:
\nmrt
\tm{1}
$r\mathstrut{}_{v,v'}(\varphi)\in\isow_{m-1}(r_v(W),r\mathstrut{}_{v'}(W'))$
and also $\wh r\mathstrut{}_{v,v'}(\varphi)$ extends the
$(m-1)$-extension
of $r\mathstrut{}_{v,v'}(\varphi)$,
\tm{2} $\varphi$ can be extended to an $(m-1)$-isomorphism
$\varphi_{v,v'}:W_v\to W'\mathstrut{}_{v'}$ such that
$\varphi\mathstrut{}_{v,v'}(I_v)=I_{v'}$. In addition,
$r\mathstrut{}_{v,v'}(\varphi)$ (resp. $\wh
r\mathstrut{}_{v,v'}(\varphi)$)
extends the $(m-1)$-closure (resp. the $(m-1)$-extension)
of $\varphi\mathstrut{}_{v,v'}$.
\enmrt
\elmm
\proof To prove statement~(1) we observe that
$$
(I_{\Delta^{(m-1)}(V)})^{\zeta_v}=\pi_{\wh F,\wh U_v}(A\circ I_{\wh
X}),\quad
(I_{\Delta^{(m-1)}(V')})^{\zeta_{v'}}=\pi_{\wh F',\wh
U'\mathstrut{}_{v'}}
(A\circ I_{\wh X'})
$$
where $A=A(F)$, $A'=A(F')$ and $\wh X$, $\wh X'$ are the
supports of~$\wh F$ and~$\wh F'$. Since $A\in\Z_m(V)$, we have
$$
\wh\varphi_{\wh F}(A\circ I_{\wh X})=
\wh\varphi(A)\circ\wh\varphi(I_{\wh X})=
A'\circ I_{\wh X'}.
$$
Thus
\qtnl{ltpr}
\wh\psi\mathstrut{}_{v,v'}(I_{\Delta^{(m-1)}(V)})=I_{\Delta^{(m-1)}(V')}
\eqtn
where $\wh\psi\mathstrut{}_{v,v'}=\wh r\mathstrut{}_{v,v'}(\varphi)$.
Further,
$$
C^{\zeta_v}=\pi_{\wh F,\wh U_v}((C\otimes I_V)\circ\wh A),\quad
(C')^{\zeta_{v'}}=\pi_{\wh F',\wh U'\mathstrut{}_{v'}}((C'\otimes
I_{V'})
\circ\wh A')
$$
where $C\in r_v(W)^{m-1},\, C'\in r\mathstrut{}_{v'}(W')^{m-1}$ and
$\wh A=A(\wh E)$, $\wh A'=A(\wh E')$. Besides,
$$
\wh\varphi_{\wh F}((C\otimes I_V)\circ \wh A)=
\wh\varphi(C\otimes I_V)\circ\wh\varphi(\wh A)=
(\psi\mathstrut{}_{v,v'})^{m-1}(C)\otimes I_{V'})\circ\wh A',
$$
where $\psi\mathstrut{}_{v,v'}=r\mathstrut{}_{v,v'}(\varphi)$, whence
\qtnl{dsul}
\wh\psi\mathstrut{}_{v,v'}(C)=(\psi\mathstrut{}_{v,v'})^{m-1}(C),\quad
C\in r_v(W)^{m-1}.
\eqtn
The equalities~(\ref{ltpr}) and~(\ref{dsul}) show that the
restriction of
$\wh\psi\mathstrut{}_{v,v'}$ to~$\wh{r_v(W)}$ is the
$(m-1)$-extension
of~$\psi\mathstrut{}_{v,v'}$.
To prove statement (2) we note that
according to statement~(1) and Lemma~\ref{schteo} it suffices to
verify only
that $\psi\mathstrut{}_{v,v'}(A)=\varphi(A)$, $A\in W$, and
$\psi\mathstrut{}_{v,v'}(I_v)=I_{v'}$. Let us prove that
\qtnl{ptri}
\wh\varphi^\m(A\otimes I_V)=\wh\varphi^{(m-1)}(A)\otimes I_{V'},\quad
A\in\W^{(m-1)}.
\eqtn
Indeed, for $A\in W^{m-1}$ this follows from the second condition of
the
definition of $m$-extension whereas for $A=I_{\Delta^{(m-1)}(V)}$
from the
first one and the equality
$$\wh\varphi^\m(I_{\Delta^{(m-1)}(V)}\otimes I_V)=
I_{\Delta^{(m-1)}(V')}\otimes I_V'=
\wh\varphi^{(m-1)}(I_{\Delta^{(m-1)}(V)})\otimes I_{V'}.$$
It follows from the definition of $\wh\psi\mathstrut{}_{v,v'}$
and~(\ref{ptri}) that
$\wh\psi\mathstrut{}_{v,v'}(A)=\wh\varphi^{(m-1)}(A)$,
$A\in\wh W^{(m-1)}$, and
$\wh\psi\mathstrut{}_{v,v'}(I_{(v,\ldots,v)})=I_{(v',\ldots,v')}$,
which completes the proof.\bull
\eSuSS
The following theorem describes the basis relations of the
$m$-closure
of~$W$ in terms of the basis relations of the algebras $r_v(W)$,
$v\in V$.
\thrml{addschur}
Let $X\in\cel(\ov W)$ and $v\in X$. Then for any basis relation~$S$
of the algebra~$r_v(W)$ the set
$$R=\bigcup_{v'\in X}\psi\mathstrut{}_{v,v'}(S)$$
is a basis relation of the algebra~$\ov W$ where
$\psi\mathstrut{}_{v,v'}=r_{v,v'}(\id_W)$.
\ethrm
\proof Let $F=E_X$ and $C$ be the adjacency matrix of the binary
relation
on~$V^m$
consisting of all pairs
$(\ov u,\ov v)\in\Delta^\m\times(\Delta^{(m-1)}\times X)$ such that
$\ov u_1=\ov v_1$. Then $C\in\W$ and so
$$\rho:\W_F\to\W_\Delta,\quad A\mapsto CAC^T$$
is a linear mapping. A straightforward check shows that
$$\rho(A)=(\sum_{v'\in
X}\pi_{F,U_{v'}}(A)^{\zeta_{v'}^{-1}})^\delta.$$
Thus it suffices to prove that~$\rho(A)$ is a multiple of a basis
matrix
of~$\W_{\Delta}$ for any basis matrix $A$ of~$\W$ belonging
to~$\W_F$.
Let us consider another mapping
$$\tau:\W_\Delta\to \W_F,\quad B\mapsto C^TBC.$$
Since $CC^T=|X|I_\Delta$, $\tau$ is an
injective linear mapping preserving the Hadamard multiplication and
satisfying $\rho(\tau(B))=|X|^2B$ for all $B\in\W_\Delta$.
The last equality also implies that given $B\in\M(\W_\Delta)$ there
exists a matrix $A'\in\W_F$ with nonnegative entries such that
$\rho(A')=B$. So $\rho(A)$ is a multiple of~$B$ for any basis
matrix~$A$ with $A\circ A'=0$. Since obviously each basis matrix
of~$\W$ belonging to~$\W_F$ can be obtained as~$A$ in such a way
when~$B$
runs over~$\M(\W_{\Delta})$, we are done.\bull
\crllrl{twopol}
Let $W\le\Mat_V$. Then
\qtnl{omineq}
(\ov W)_v\le r_v(W)\le \ov{(W_v)}
\eqtn
for all $v\in V$.
\ecrllr
\proof To prove the first inclusion it suffices to prove that
$\ov W\le r_v(W)$, which is a straightforward consequence of
Theorem~\ref{addschur}. On the other hand, applying the same theorem
to $W=W_v$ and $X=\{v\}$ we obtain $r_v(W_v)=\ov{(W_v)}$.
Since obviously $r_v(W)\le r_v(W_v)$, the right inclusion
follows.\bull
\begin{thebibliography}{99}
\bibitem{B81}
L.~Babai, {\em On the order of uniprimitive permutation groups},
Annals of Math., {\bf 113} (1981), 553--568.
\bibitem{B}
L.~Babai, {\em Automorphism Groups, Isomorphism, reconstruction},
in: R.~L.~Graham, M.~Gr{\"o}t\-schel, L.~Lo\-v{\'a}sz (eds): Handbook
of combinatorics, vol. 2, Amsterdam (etc.), Elsevier (etc.), 1995,
1447--1540.
\bibitem{BI}
E.~Bannai, T.~Ito, {\em Algebraic Combinatorics I. Association
schemes}, Benjamin Cummings, London, 1984.
\bibitem{BCN}
A.~E.~Brouwer, A.~M.~Cohen, A.~Neumaier, {\em Distance-Regular
graphs}, Springer, Berlin, 1989.
\bibitem{BIK}
A.~E.~Brouwer, A.~V.~Ivanov, M.~H.~Klin, {\em Some new strongly
regular graphs}, Combinatorica, {\bf 9} (1989), 339--344.
\bibitem{BL}
A.~E.~Brouwer, J.~H.~van~Lint, {\em Strongly Regular Graphs and
Partial Geometries}. In: {\em ``Enumeration and Design -- Proc.
Silver Jubilee Conf. on Combinatorics. Waterloo, 1982''},
(ed. D.~M.~Jackson, S.~A.~Vanstone), Acad. Press Toronto, 1984,
85--122.
\bibitem{Ca}
P.~J.~Cameron, {\em Permutation groups}, Cambridge University Press,
1999.
\bibitem{D}
P.~Dembowski, {\em Finite Geometries}, Springer, Berlin, 1968.
\bibitem{EKP}
S.~Evdokimov, M.~Karpinski, I.~Ponomarenko, {\em On a New High
Dimensional
Weisfeiler-Leman Algorithm}, Journal of Algebraic Combinatorics, {\bf
10}
(1999), 29--45.
\bibitem{EPN}
S.~A.~Evdokimov, I.~N.~Ponomarenko, {\em Two Inequalities for the
Parameters of a Cellular Algebra}, Zapiski Nauchnykh
Seminarov POMI, {\bf 240} (1997), 82--95.
\bibitem{EP}
S.~A.~Evdokimov, I.~N.~Ponomarenko, {\em On Primitive Cellular
Algebras},
Zapiski Nauchnykh Seminarov POMI, {\bf 256} (1999), 38--68.
\bibitem{EPL}
S.~A.~Evdokimov, I.~N.~Ponomarenko, {\em On highly closed cellular
algebras
and highly closed isomorphisms}, Electronic J. of Combinatorics,
{\bf 6} (1999), \#R18.
\bibitem{EPT}
S.~A.~Evdokimov, I.~N.~Ponomarenko, G.~Tinhofer, {\em On a New Class
of Weakly
Compact Graphs}, Techn. Univ. M{\"u}nchen, Fak. f. Math., Report TUM
M9715,
(1997) (accepted for publication in Discrete Math.).
\bibitem{FKM}
I.~A.~Farad{\v z}ev, M.~H.~Klin, M.~E.~Muzichuk, {\em Cellular
rings and groups of automorphisms of graphs}, in: I.A. Farad{\v z}ev
et al. (eds): Investigations in algebraic theory of combinatorial
objects, Kluwer Acad. Publ., Dordrecht, 1994, 1--152.
\bibitem{Hi70}
D.~G.~Higman, {\em Characterization of families of rank 3 permutation
graphs by the subdegree I, II}, Arch. Math., {\bf 21} (1970),
151--156; 353--361.
\bibitem{H70}
D.~G.~Higman, {\em Coherent configurations 1.}, Rend. Mat. Sem.
Padova,
{\bf 44} (1970), 1--25.
%\bibitem{Hi}
%D.~G.~Higman, {\em Coherent algebras}, Linear Algebra Appl.,
%{\bf 93} (1987), 209--239.
\bibitem{I}
A.~V.~Ivanov, {\em Non rank 3 strongly regular graph with the
5-vertex condition}, Combinatorica, {\bf 9} (1989), 255--260.
\bibitem{M}
E.~Mendelsohn, {\em Every (finite) group is the group of
automorphisms of
a (finite) strongly regular graph}, Ars Combinatoria, {\bf 6} (1978),
75--86.
\bibitem{MT}
M.~E.~Muzichuk, G.~Tinhofer, {\em Recognizing circulant graphs of
prime
order in polynomial time}, Electronic J. of Combinatorics,
{\bf 5} (1998), \#R25.
\bibitem{S59}
S.~S.~Shrikhande, {\em The uniqueness of the $L_2$ association
scheme}, Ann. Math. Statist., {\bf 30} (1959), 781--798.
\bibitem{W}
B.~Ju.~Weisfeiler (editor), {\em On construction and
identification of graphs}, Springer Lecture Notes, 558, 1976.
\bibitem{WL}
B.~Ju.~Weisfeiler, A.~A.~Leman, {\em Reduction of a graph to a
canonical form and an algebra which appears in the process},
NTI, Ser.2, (1968), 9, 12--16.
\bibitem{Wi}
H.~Wielandt, {\em Finite permutation groups}, Academic press,
New York - London, 1964.
\bibitem{W2}
H.~Wielandt, {\em Permutation groups through invariant relations
and invariant fun\-cti\-ons}, Lect. Notes Dept. Math. Ohio St. Univ.,
Columbus, 1969.
\end{thebibliography}
\end{document}