Separability Number and Schurity Number of Coherent Configurations

Sergei Evdokimov St. Petersburg Institute for Informatics and Automation

                          evdokim@pdmi.ras.ru ∗

Ilia Ponomarenko Steklov Institute of Mathematics at St. Petersburg

                            inp@pdmi.ras.ru †

Submitted: January 26, 2000; Accepted: May 17, 2000

Abstract

To each coherent configuration (scheme) C and positive integer m we associate a natural scheme Ĉ^{(m)} on the m-fold Cartesian product of the point set of C having the same automorphism group as C. Using this construction we define and study two positive integers: the separability number s(C) and the Schurity number t(C) of C. It turns out that s(C) ≤ m iff C is uniquely determined up to isomorphism by the intersection numbers of the scheme Ĉ^{(m)}. Similarly, t(C) ≤ m iff the diagonal subscheme of Ĉ^{(m)} is an orbital one. In particular, if C is the scheme of a distance-regular graph Γ, then s(C) = 1 iff Γ is uniquely determined by its parameters whereas t(C) = 1 iff Γ is distance-transitive. We show that if C is a Johnson, Hamming or Grassmann scheme, then s(C) ≤ 2 and t(C) = 1. Moreover, we find the exact values of s(C) and t(C) for the scheme C associated with any distance-regular graph having the same parameters as some Johnson or Hamming graph. In particular, s(C) = t(C) = 2 if C is the scheme of a Doob graph. In addition, we prove that s(C) ≤ 2 and t(C) ≤ 2 for any imprimitive 3/2-homogeneous scheme. Finally, we show that s(C) ≤ 4, whenever C is a cyclotomic scheme on a prime number of points.

1 Introduction

The purpose of this paper is to continue the investigations of distance-regular graphs [4] and more generally association schemes [3] from the point of view of their isomorphisms and symmetries, started by the authors in [9], [11], [12]. 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.

∗Partially supported by RFFI, grant 96-15-96060 †Partially supported by RFFI, grants 96-15-96060, 99-01-00098

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 [16] and under a different name independently by B. Yu. Weisfeiler and A. A. Leman in [22]. The exact definition will be given in Subsection 2.1 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, [7, Chapter 3] and [14]). The present paper continues the investigations of the authors in this direction (see [9]-[13]).

Probably one of the first results on the characterization of a scheme by its parameters was the paper [20] 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 [15] where some families of rank 3 graphs were characterized by means of the valency and the so called t-vertex condition (see Subsection 6.3). Further investigations in this direction led to characterizing some classical families of distance-regular graphs (see [4, Chapter 9]). 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 [3] 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 [2]). As it was found in [22] 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 [21], the so called m-dim Weisfeiler-Leman method associated with them (see [2]) and a general concept of such procedures from [9]. 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 [22] (as to exact definitions see Subsection 2.1). They are by definition matrix algebras over ℂ 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 [9] and studied in [12] (as to exact definitions see Section 3). For each positive integer m we define the m-extended algebra Ŵ^{(m)} of a cellular algebra W ≤ 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 Ŵ^{(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 \overline{W}^{(m)} on V called the m-closure of W. This produces the following series of inclusions:

W = \overline{W}^{(1)} ≤ … ≤ \overline{W}^{(n)} = … = \overline{W}^{(∞)}  (1)

where \overline{W}^{(∞)} 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

Isow(W, W′) = Isow_{1}(W, W′) ⊃ … ⊃ Isow_{n}(W, W′) = … = Isow_{∞}(W, W′)  (2)

where Isow_{m}(W, W′) is the set of all m-isomorphisms from W to W′ and Isow_{∞}(W, W′) is the set of all weak isomorphisms from W to W′ induced by strong isomorphisms. According to (2) and (1) we say that the algebra W is m-separable if Isow_{m}(W, W′) = Isow_{∞}(W, W′) for all cellular algebras W′, and m-Schurian if \overline{W}^{(m)} = \overline{W}^{(∞)}. Now we define the separability number s(W) and the Schurity number t(W) of W by

s(W) = min{m : W is m − separable}, t(W) = min{m : W is m − Schurian}.

It follows from Theorem 4.5 that there exist cellular algebras with arbitrary large separability and Schurity numbers. However their values for an algebra on n points do not exceed ⌈n/3⌉ (Theorem 4.3) and equal 1 for a simplex and a semiregular algebra (Theorem 4.4). In the general case we estimate these numbers for W by those for pointwise stabilizers and extended algebras of it (Theorem 4.6). 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 4.8). All of these results are used in Sections 5 and 7.

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 C is called m-separable if s(C) ≤ m and m-Schurian if t(C) ≤ 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 [13] and contains trees, cographs and interval graphs.

In this paper we estimate the separability and Schurity numbers for several classes of schemes. In Section 5 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 5.1). 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 5.4). (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 [19]).

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 7.1). Using known characterizations of Johnson and Hamming schemes we compute the separability and Schurity numbers of all schemes with the corresponding parameters (Theorems 7.2 and 7.3). 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 7.7) 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 7.5 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 [17]) which is the only known to the authors strongly regular non rank 3 graph satisfying the 5vertex 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 7.9). 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 (K, L)-regularity of an edge colored graph Γ introduced and studied in Section 6 (here K and L are edge colored graphs, L being a subgraph of K). If K and L have at most t and 2 vertices respectively, then the (K, L)-regularity of Γ for all such K, L exactly means that Γ satisfies the t-vertex condition. In the general case the (K, L)-regularity of Γ means that any embedding of L to Γ can be extended in the same number of ways to an embedding of K to it. Many classical distance-regular graphs are (K, L)-regular for several choices of K and L and, moreover, they can be characterized in such a way. We use this observation in Section 7 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 (K, L)- regular or not for all colored graphs K, L with at most 3m and 2m vertices respectively (Corollary 6.3). In addition we prove that the colored graph of the scheme corresponding to an m-closed algebra satisfies the 3m-vertex condition (Theorem 6.4).

The paper consists of eight sections. Section 2 contains the main definitions and notation concerning schemes and cellular algebras. In Section 3 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 mequivalence of permutation groups (see [24]). In Section 4 we introduce the separability and Schurity numbers of cellular algebras and schemes and study general properties of them. Sections 5 and 7 are devoted to computing the separability and Schurity numbers for 3/2homogeneous schemes and the schemes of some distance-regular graphs. In Section 6 we study the (K, L)-regularity of colored graphs. Finally, Section 8 (Appendix) contains a number of technical results concerning the structure of extended algebras and their weak isomorphisms. These results are used in Subsection 3.3 and Section 4.

Notation. As usual by ℂ and ℤ 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 × 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 ⊂ V such that R ⊂ U × 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 ∈ Mat_{V} and u, v ∈ 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 ⊂ V the algebra Mat_{U} can be treated in a natural way as a subalgebra of Mat_{V} . If A ∈ 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 ∈ 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) ∈ R). For U, U′ ⊂ V let J_{U,U′} denote the adjacency matrix of the relation U × 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 → V′ (v ↦ 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 ∈ 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, …, 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, Δ^{(m)}(V) = {(v, …, v) ∈ V^{m} : v ∈ V }.

2 Coherent configurations and cellular algebras

2.1. Let V be a finite set and R a set of binary relations on V. A pair C = (V, R) is called a coherent configuration or a scheme on V if the following conditions are satisfied:

(C1) R forms a partition of the set V^{2},

(C2) Δ^{(2)}(V) is a union of elements of R,

(C3) if R ∈ R, then R^{T} ∈ R,

(C4) if R, S, T ∈ R, then the number |{v ∈ V : (u, v) ∈ R, (v, w) ∈ S}| does not depend on the choice of (u, w) ∈ T.

The numbers from (C4) are called the intersection numbers of C and denoted by p_{R,S}^{T}. The elements of R = R(C) are called the basis relations of C.

We say that schemes C = (V, R) and C′ = (V′, R′) are isomorphic, if R^{g} = R′ for some bijection g : V → V′ called an isomorphism from C to C′. The group of all isomorphisms from C to itself contains a normal subgroup

Aut(C) = {g ∈ Sym(V) : R^{g} = R, R ∈ R}

called the automorphism group of C. Conversely, to each permutation group G ≤ 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. [14, p.16]). A scheme C is called Schurian if it is a closed object under this correspondence, i.e. if the set of its basis relations coincides with Orb_{2}(Aut(C)).

If C = (V, R) is a scheme, then the set M = {A(R) : R ∈ 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 Bose-Mesner (or adjacency) algebra of C and will be denoted by A(C). Obviously, it is a cellular algebra on V, i.e. a subalgebra A of Mat_{V} satisfying the following conditions:

(A1) I_{V} , J_{V} ∈ A,

(A2) ∀A ∈ A : A^{∗} ∈ A,

(A3) ∀A, B ∈ A : A ∘ B ∈ A,

where A ∘ B is the Hadamard (componentwise) product of the matrices A and B. The elements of V are called the points and the set V is called the 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

∑_{A∈M} A = J_{V} and A ∈ M ⇔ A^{T} ∈ M.  (3)

The linear base M is called the standard basis of A and its elements the basis matrices. The nonnegative integers p_{A,B}^{C} defined for A, B, C ∈ M by AB = ∑_{C∈M} p_{A,B}^{C} · C are called the structure constants of A.

We say that cellular algebras A on V and A′ on V′ are strongly isomorphic, if A^{g} = A′ for some bijection g : V → V′ called a strong isomorphism from A to A′. The group of all strong isomorphisms from A to itself contains a normal subgroup

Aut(A) = {g ∈ Sym(V) : A^{g} = A, A ∈ A}

called the automorphism group of A. Conversely, for any permutation group G ≤ Sym(V) its centralizer algebra

Z(G) = {A ∈ Mat_{V} : A^{g} = A, g ∈ G}

is a cellular algebra on V. A cellular algebra A is called Schurian if A = Z(Aut(A)).

Comparing the definitions of schemes and cellular algebras one can see that the mappings

C ↦ A(C), A ↦ C(A)  (4)

where C(A) = (V, R(A)) with R(A) = {R ⊂ V^{2} : A(R) ∈ 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 (4) takes Schurian schemes to Schurian cellular algebras and vice versa.

The properties of the correspondence (4) 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, …) 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), …) 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 ≤ W′ if W ⊂ W′. Given subsets X_{1}, …, X_{s} of Mat_{V}, their cellular closure, i.e. the smallest cellular algebra on V containing all of them is denoted by [X_{1}, …, X_{s}]. If X_{i} = {A_{i}}, we omit the braces. For a cellular algebra W ≤ Mat_{V} and a point v ∈ V we set W_{v} = [W, I_{v}] where I_{v} = I_{{v}}.

2.2. Let W ≤ Mat_{V} be a cellular algebra and M = M(W). Set

Cel(W) = {U ⊂ V : I_{U} ∈ M}, Cel^{∗}(W) = { ⋃_{U∈X} U : X ⊂ Cel(W)}.

Each element of Cel(W) (resp. Cel^{∗}(W)) is called a cell of W (resp. a cellular set of W). Obviously,

V = ⋃_{U∈Cel(W)} U (disjoint union).

The algebra W is called homogeneous if | Cel(W)| = 1.

For U_{1}, U_{2} ∈ Cel^{∗}(W) set M_{U_{1},U_{2}} = {A ∈ M : A ∘ J_{U_{1},U_{2}} = A}. Then

M = ⋃_{U_{1},U_{2}∈Cel(W)} M_{U_{1},U_{2}}  (disjoint union).

Also, since for any cells U_{1}, U_{2} and any A ∈ M_{U_{1},U_{2}} the uth diagonal element of the matrix AA^{T} equals the number of 1’s in the uth row of A, it follows that the number of 1’s in the uth row (resp. vth column) of A does not depend on the choice of u ∈ U_{1} (resp. v ∈ 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 ∈ M and we use the notation d(A) for this number and call it the degree of A. A cellular algebra W is called semiregular if d_{in}(A) = d_{out}(A) = 1 for all A ∈ M. A homogeneous semiregular algebra is called regular.

For each U ∈ Cel^{∗}(W) we view the subalgebra I_{U}W I_{U} of W as a cellular algebra on U, denote it by W_{U} and call the 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 ∈ Cel(W), we call W_{U} the homogeneous component of W corresponding to U.

A relation R on V is called a relation of the algebra W if A(R) ∈ W. If in addition A(R) ∈ 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(C(W)). For U_{1}, U_{2} ∈ Cel(W) we set

R_{U_{1},U_{2}} = R_{U_{1},U_{2}}(W) = {R ∈ R(W) : A(R) ∈ M_{U_{1},U_{2}}}.

2.3. Let W be a cellular algebra on V and E be an equivalence on V. We say that E is an 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 trivial. Suppose now that W is homogeneous. We call W imprimitive if it has a nontrivial equivalence. If W has exactly two equivalences, then it is called primitive. We stress that a cellular algebra on a one-point set is neither imprimitive nor primitive according to this definition.

Let E ∈ E(W). For each U ∈ V/E we view the subalgebra I_{U}W I_{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

M(W_{E,U}) = {A_{U} : A ∈ M, I_{U}AI_{U} ≠ 0}.  (5)

It follows from (5) and the first part of (3) that each basis matrix of W_{E,U} can be uniquely represented in the form A_{U} for some A ∈ M(W). Set

W_{E} = {A(E) ∘ B : B ∈ W }.

Then W_{E} is a subalgebra of W satisfying conditions (A2) and (A3).

A nonempty equivalence E of W is called 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 decomposable if it is not indecomposable. In this case E = E_{1} ∪ 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 indecomposable components of it. It follows from [9, Lemma 2.6] that given an indecomposable equivalence E ∈ E(W) we have

|U_{1} ∩ X| = |U_{2} ∩ X| > 0 for all cells X ⊂ V_{E} and U_{1}, U_{2} ∈ 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 [9, Lemma 2.6] is that if E is indecomposable, then given U ∈ V/E the mapping

π_{U} : W_{E} → W_{E,U}, A ↦ A_{U}  (6)

is a matrix algebra isomorphism preserving the Hadamard multiplication.

We complete the subsection by a technical lemma which will be used later.

Lemma 2.1 Let W ≤ Mat_{V} be a cellular algebra, R ∈ R(W) and E_{1}, E_{2} ∈ E(W). Then the number |(U_{1} × U_{2}) ∩ R| does not depend on the choice of U_{1} ∈ V/E_{1} and U_{2} ∈ V/E_{2}, such that (U_{1} × U_{2}) ∩ R ≠ ∅.

Proof. Suppose that (U_{1} ×U_{2})∩R ≠ ∅. Then the number |(U_{1} ×U_{2})∩R| equals the (v_{1}, v_{2})- entry of the matrix A(E_{1})A(R)A(E_{2}) where (v_{1}, v_{2}) ∈ (U_{1} × U_{2}) ∩ 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.

2.4. Along with the notion of a strong isomorphism we consider for cellular algebras also weak isomorphisms (see [21, 12, 9])^{1}. Cellular algebras W on V and W′ on V′ are called weakly isomorphic if there exists a matrix algebra isomorphism φ : W → W′ such that

φ(A ∘ B) = φ(A) ∘ φ(B) for all A, B ∈ W.  (7)

Any such φ is called a weak isomorphism from W to W′. It immediately follows from the definition that φ takes {0,1}-matrices to {0,1}-matrices and also φ(I_{V}) = I_{V′}, φ(J_{V}) = J_{V′}. It was proved in [11, Lemma 4.1] that φ(A^{T}) = φ(A)^{T} for all A ∈ M(W). Besides, φ induces a natural bijection U ↦ U^{φ} from Cel^{∗}(W) onto Cel^{∗}(W′) preserving cells such that φ(I_{U}) = I_{U^{φ}} and |U| = |U^{φ}|. In particular, |V | = |V′|. Finally, φ(M) = M′ and moreover

φ(M_{U_{1},U_{2}}) = M′_{U_{1}^{φ},U_{2}^{φ}} for all U_{1}, U_{2} ∈ Cel^{∗}(W)  (8)

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_{φ(A),φ(B)}^{φ(C)} for all A, B, C ∈ M.

The following lemma describes the behavior of the relations of a cellular algebra under weak isomorphisms.

Lemma 2.2 Let W ≤ Mat_{V} and W′ ≤ Mat_{V′} be cellular algebras and φ ∈ Isow(W, W′). Then φ induces a bijection R ↦ R^{φ} from the set of all relations of W to the set of all relations of W′ such that φ(A(R)) = A(R^{φ}). Moreover,

(1) d_{in}(R) = d_{in}(R^{φ}), d_{out}(R) = d_{out}(R^{φ}), |R| = |R^{φ}| for all R ∈ R(W), (2) E is an (indecomposable) equivalence of W iff E^{φ} is an (indecomposable) equivalence

1In [21, p.33] they were called weak equivalences.

of W′. In addition, |V_{E}| = |V′_{E^{φ}}| and |V/E| = |V′/E^{φ}|.

Proof. Since statement (2) coincides with Lemma 3.3 of [13], we prove only statement (1). Let R ∈ R_{U_{1},U_{2}}(W) where U_{1}, U_{2} ∈ Cel(W). Then obviously d_{out}(R) = p_{R,R^{T}}^{Δ_{1}} and d_{in}(R) = p_{R^{T} ,R}^{Δ_{2}} where Δ_{i} = Δ^{(2)}(U_{i}), i = 1, 2. Since R^{φ} ∈ R_{U′_{1},U′_{2}}(W′) where U′_{i} = (U_{i})^{φ}, i = 1, 2, (see (8)) and (R^{T})^{φ} = (R^{φ})^{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}|.

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)).

3 Extended algebras and their weak isomorphisms

3.1. Let W be a cellular algebra on V. For each positive integer m we set

Ŵ = Ŵ^{(m)} = [W^{m}, Z_{m}(V)]  (9)

where W^{m} = W ⊗ ⋯ ⊗ 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 Ŵ ≤ Mat_{V^{m}} the m-extended algebra of W. The group Aut(Ŵ) acts faithfully on the set Δ = Δ^{(m)}(V). Moreover, the mapping δ : v ↦ (v, …, v) induces a permutation group isomorphism between Aut(W) and the constituent of Aut(Ŵ) on Δ. It was proved in [12] that

Ŵ = [W^{m}, I_{Δ}].  (10)

The cellular algebra on V defined by

\overline{W} = \overline{W}^{(m)} = ((Ŵ^{(m)})_{Δ})^{δ^{−1}}

is called the m-closure of W. We say that W is m-closed if W = \overline{W}^{(m)}. It was proved in [9, Proposition 3.3] that Aut(\overline{W}^{(m)}) = Aut(W),

W = \overline{W}^{(1)} ≤ … ≤ \overline{W}^{(n)} = … = W^{(∞)}  (11)

and the algebra \overline{W}^{(m)} is l-closed for all l ∈ [m]. In addition, it is easy to see that if l ≥ m, then the l-closure of \overline{W}^{(m)} equals \overline{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]×[l] onto [lm] defined by (i, j) ↦ i+(j−1)m.

Lemma 3.1 Let W be a cellular algebra and l, m positive integers. Then ( ; Ŵ^{(m)})^{(l)} = Ŵ^{(lm)}.

Proof. Obviously, the algebra W^{lm} and the matrix I_{Δ^{(lm)}(V)} = (⊗_{j=1}^{l}I_{Δ^{(m)}(V)}) ∘ I_{Δ^{(l)}(V^{m})} are

contained in ({ \atop W^{(m)}})^{(l)}. So by (10) the right side of the equality in question is contained in the left one. Conversely, I_{Δ^{(l)}(V^{m})} belongs to Z_{lm}(V) and hence belongs also to Ŵ^{(lm)}. Besides, (Ŵ^{(m)})^{l} ⊂ Ŵ^{(lm)} due to statement (4) of Lemma 7.2 of [12] with I_{k} = J_{k} = [1+(k−1)m, km], k ∈ [l], and lm instead of m. Thus we are done by (10).

The following technical statement was in fact proved in [9].

Lemma 3.2 Let W′ be a cellular algebra on V^{m} containing Z_{m}(V) and W = (W′_{Δ})^{δ^{−1}}. Then W′ ≥ Ŵ^{(m)} and also W is m-closed. In particular, the m-extended algebras of an algebra and its m-closure coincide.

Proof. It follows from the proof of statement (5) of Lemma 5.2 of [9] that W′ ≥ W^{m}. Thus the required inclusion is the consequence of equality (10).

3.2. Let φ : W → W′ be a weak isomorphism from a cellular algebra W ≤ Mat_{V} to a cellular algebra W′ ≤ Mat_{V′}. According to [12] we say that a weak isomorphism ψ : Ŵ → Ŵ′ is an m-extension of φ if ψ(I_{Δ}) = I_{Δ′} and ψ(A) = φ^{m}(A) for all A ∈ W^{m}, where Δ = Δ^{(m)}(V), Δ′ = Δ^{(m)}(V′) and φ^{m} is the weak isomorphism from W^{m} to (W′)^{m} induced by φ. It was proved in [12] that ψ is uniquely determined by φ and the restriction of it to Ŵ_{Δ} induces a uniquely determined weak isomorphism from \overline{W} to \overline{W′} extending φ. We denote these weak isomorphisms by φ̂ = φ̂^{(m)} and \overline{φ} = \overline{φ}^{(m)} respectively. As it was observed in [12], φ̂ takes a basis matrix of Z_{m}(V) to the corresponing basis matrix of Z_{m}(V′).

A weak isomorphism φ is called an m-isomorphism if there exists an m-extension of φ. The set of all m-isomorphisms from W to W′ will be denoted by Isow_{m}(W, W′). It was proved in [12, Theorem 4.5 and formula (7)] that

Isow(W, W′) = Isow_{1}(W, W′) ⊃ … ⊃ Isow_{n}(W, W′) = … = Isow_{∞}(W, W′) (12)

where Isow_{∞}(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.

Lemma 3.3 Let W, W′ be cellular algebras and l, m positive integers. Then φ ∈ Isow_{lm}(W, W′) iff φ ∈ Isow_{m}(W, W′) and φ̂^{(m)} ∈ Isow_{l}(Ŵ^{(m)}, Ŵ′^{(m)}). In this case, φ̂^{(lm)} = ( ˆφ̂^{(m)})^{(l)}.

Proof. Let φ ∈ Isow_{lm}(W, W′). Then φ ∈ Isow_{m}(W, W′) by (12). Besides, φ̂^{(lm)}(I_{Δ^{(l)}(V^{m})}) = I_{Δ^{(l)}(V′^{m})} as far as φ̂^{(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} ⊂ Z_{lm}(V), we have

φ̂^{(lm)}(A) = (φ̂^{(m)})^{l}(A)  (13)

for all A ∈ (Z_{m}(V))^{l}. Further, equality (13) obviously holds also for all A ∈ (W^{m})^{l}. So it holds for all A ∈ (Ŵ^{(m)})^{l} by the definition of Ŵ^{(m)} and Lemma 3.1. Thus φ̂^{(lm)} is the l-extension of φ̂^{(m)}.

Conversely, let φ ∈ Isow_{m}(W, W′) and φ̂^{(m)} ∈ Isow_{l}(Ŵ^{(m)}, Ŵ′^{(m)}). We show that ψ = ( ˆφ̂^{(m)})^{(l)} is the lm-extension of φ. Indeed, ψ(A) = (φ̂^{(m)})^{l}(A) = φ^{lm}(A) for all A ∈ W^{lm} by the definition of φ̂^{(m)}. On the other hand, since Δ^{(lm)}(V) = (⊗_{j=1}^{l}I_{Δ^{(m)}(V)}) ∘ I_{Δ^{(l)}(V^{m})}, we have

ψ(I_{Δ^{(lm)}(V)}) = (⊗_{j=1}^{l}φ̂^{(m)}(I_{Δ^{(m)}(V)})) ∘ ψ(I_{Δ^{(l)}(V^{m})}) = (⊗_{j=1}^{l}I_{Δ^{(m)}(V′)}) ∘ I_{Δ^{(l)}(V′^{m})} = I_{Δ^{(lm)}(V′)},

which completes the proof.

3.3. 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 [24].

Definition 3.4 Two cellular algebras on the same set of points are called m-equivalent, if their m-extended algebras equal.

It immediately follows from the definition that the automorphism groups and hence the Schurian closures of m-equivalent algebras coincide.

Lemma 3.5 Two cellular algebras are m-equivalent iff their m-closures are equal.

Proof. The necessity follows from the definition of m-closure, whereas the sufficiency is the consequence of Lemma 3.2.

Lemma 3.5 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} ≈_{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 [24, pp.8-12].

Lemma 3.6 Let W_{1}, W_{2} be cellular algebras on an n-point set V. Then

(1) W_{1} ≈_{1} W_{2} iff W_{1} = W_{2},

(2) if W_{1} ≈_{m} W_{2}, then W_{1} ≈_{m+1} W_{2},

(3) if m ≥ n, then W_{1} ≈_{m} W_{2} iff Aut(W_{1}) = Aut(W_{2}),

(4) if W_{1} ≈_{m} W_{2}, then (W_{1})_{v} ≈_{m} (W_{2})_{v} for all v ∈ V.

Proof. Statement (1) is trivial. Set \overline{W_{i}} = \overline{W_{i}}^{(m)}, i = 1, 2. If W_{1} ≈_{m} W_{2}, then \overline{W_{1}} = \overline{W_{2}} by Lemma 3.5. 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 (11) we conclude that

\overline{W_{1}} = \overline{W_{1}}^{(∞)} = \overline{W_{2}}^{(∞)} = \overline{W_{2}}.

Thus the sufficiency follows from Lemma 3.5. Let us prove statement (4). Since Ŵ_{1} = Ŵ_{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 (31) with W = W_{i} we see that \overline{(W_{i})_{v}} = \overline{r_{v}(W_{i})}, i = 1, 2. Thus \overline{(W_{1})_{v}} = \overline{(W_{2})_{v}}, and we are done by Lemma 3.5.

4 The separability and Schurity numbers

4.1. Throughout the section we assume m to be a positive integer.

Definition 4.1 A cellular algebra W is called m-separable if Isow_{m}(W, W′) = Isow_{∞}(W, W′) for all cellular algebras W′; it is called m-Schurian if \overline{W}^{(m)} = \overline{W}^{(∞)}. A scheme is called m-separable (resp. m-Schurian) if so is its Bose-Mesner algebra.

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 7.1). The following statement is an immediate consequence of the definition of m-equivalence and Lemma 3.5.

Theorem 4.2 Two m-equivalent cellular algebras are m-separable (resp. m-Schurian) or not simultaneously.

It follows from formula (12) (resp. formula (11)) that an m-separable (resp. m-Schurian) algebra is also l-separable (resp. l-Schurian) for all l ≥ m and that any cellular algebra W on n points is always n-separable and n-Schurian. We set

s(W) = min{m : W is m − separable}, t(W) = min{m : W is m − Schurian}.

These positive integers are called the separability number and the Schurity number of W respectively. The separability number s(C) and the Schurity number t(C) of a scheme C are defined as the corresponding numbers of its Bose-Mesner algebra.

The following statement the proof of which is in the end of Section 6 shows that the inequalities s(W) ≤ n and t(W) ≤ n can be slightly improved.

Theorem 4.3 For any cellular algebra W on n points we have s(W) ≤ ⌈n/3⌉ and t(W) ≤ ⌈n/3⌉.

In some cases the separability and Schurity numbers can easily be computed.

Theorem 4.4 If W is a simplex or a semiregular algebra, then s(W) = t(W) = 1. In particular, s(Mat_{V}) = t(Mat_{V}) = 1.

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 ℂ[G_{right}] ≤ Mat_{G} where G_{right} is the permutation group on G defined by right multiplications. However, ℂ[G_{right}] = Z(G_{left}) where G_{left} ≤ Sym(G) is defined by left multiplications. Thus ℂ[G_{right}] and hence W are Schurian. Let now φ : W → W′ be a weak isomorphism from a regular algebra W to a cellular algebra W′. By statement (1) of Lemma 2.2 the algebra W′ is also regular. So without loss of generality we assume that W = ℂ[G_{right}], W′ = ℂ[G′_{right}] where G and G′ are finite groups. Then φ is induced by the group isomorphism G → G′ associated with the isomorphism of the groups of basis matrices. Thus φ ∈ Isow_{∞}(W, W′).

It was proved in Theorem 1.1 (resp. in Theorem 1.3) of [12] that there exists ε > 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 ≥ ⌊εn⌋ (resp. a Schurian algebra with simple spectrum on n points admitting an m-isomorphism with m ≥ ⌊εn⌋ which is not induced by a strong isomorphism). This gives the following statement.

Theorem 4.5 There exist cellular algebras with arbitrary large separability and Schurity numbers. Moreover

lim inf_{n(W)→∞} \frac{s(W)}{n(W)} > 0, lim inf_{n(W)→∞} \frac{t(W)}{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.

The interrelation between the separability and Schurity numbers seems to be rather complicated. For instance, Theorem 4.5 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 [12, Subsection 5.5]).

4.2. 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.

Theorem 4.6 Let W ≤ Mat_{V} be a cellular algebra. Then

(1) s(W) ≤ s(W_{v}) + 1 for all v ∈ V,

(2) if W_{v} is t(W_{v})-separable for some point v ∈ V, then t(W) ≤ t(W_{v}) + 1,

(3) s(W) ≤ m s(Ŵ^{(m)}), t(W) ≤ m t(Ŵ^{(m)}) for all m ≥ 1.

Proof. Let φ : W → W′ be an m-isomorphism where m = s(W_{v}) + 1. Choose v′ ∈ V′ as in Subsection 8.2. Then by statement (2) of Lemma 8.3 the weak isomorphism φ_{v,v′} belongs to Isow_{m−1}(W_{v}, W′_{v′}) and extends φ. Since W_{v} is (m − 1)-separable, φ_{v,v′} and hence φ are induced by a permutation from V to V′. Thus s(W) ≤ m.

Set m = t(W_{v}) + 1. Then the algebra (\overline{W_{v}})^{(m−1)} is Schurian and hence by Corollary 8.5 coincides with r_{v}^{(m)}(W). So by Lemma 8.3 we have r_{v,v′}^{(m)}(φ) = \overline{φ_{v,v′}}^{(m−1)} where φ and v′ are as in Theorem 8.4. Therefore by the assumption of statement (2) and Theorem 4.2 the weak isomorhism r_{v,v′}^{(m)}(φ) is induced by a bijection g_{v,v′} : V → V′. Thus Theorem 8.4 implies

that the basis relations of the algebra \overline{W}^{(m)} are 2-orbits of the group generated by the sets Aut(W_{v})g_{v,v′}, v ∈ X. This proves the Schurity of W.

To prove statement (3) let φ : W → W′ be an ms(Ŵ)-isomorphism where Ŵ = Ŵ^{(m)}. By Lemma 3.3 with l = s(Ŵ) we see that φ̂ : Ŵ → Ŵ′ is an s(Ŵ)-isomorphism. So φ̂ and also φ are induced by strong isomorphisms. Thus s(W) ≤ ms(Ŵ). To prove the second inequality we observe that the l-closure of Ŵ with l = t(Ŵ) is Schurian. This implies by Lemma 3.1 that so is the restriction of the algebra Ŵ^{(lm)} to Δ^{(l)}(V^{m}). Since the algebra Ŵ^{(lm)} is strongly isomorphic to the restriction of the last algebra to the set Δ^{(lm)}(V), we are done.

Statements (1) and (2) of Theorem 4.6 imply by induction the following proposition where we set W_{[U]} to be the cellular closure of the algebras W_{v}, v ∈ U.

Corollary 4.7 Let U ⊂ V. Then

s(W) ≤ s(W_{[U]}) + l, t(W) ≤ max(s(W_{[U]}, t(W_{[U]}) + l

where l = |U|. In particular, s(W) ≤ l+1 and t(W) ≤ l+1 whenever s(W_{[U]}) = t(W_{[U]}) = 1.

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 [9]. We recall that the 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 ⊂ V such that W_{[U]} = Mat_{V}.

Theorem 4.8 For any cellular algebra W we have s(W) ≤ b(W)+1 and t(W) ≤ b(W)+1.

It follows from [1] 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.

Corollary 4.9 If W is a primitive cellular algebra on n points, then s(W) < ⌈4\sqrt{n} log n⌉ and t(W) < ⌈4\sqrt{n} log n⌉.

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 [21, p.176]. 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) ≥ 2. In addition, s(W) ≥ 2, because there exist several strongly regular graphs with the same parameters.

5 3/2-homogeneous schemes

5.1. We say that a homogeneous scheme is 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 [4, p.42]) and the schemes of Frobenius groups (see [23]).

Theorem 5.1 If C is an imprimitive 3/2-homogeneous scheme, then s(C) ≤ 2 and t(C) ≤ 2.

Proof. Let W be the Bose-Mesner algebra of C and W′ = (W_{v})_{V \{v}} where V is the point set of W. It follows from [11, Lemma 5.13] that W′ is a semiregular algebra. By Theorem 4.4 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 4.6.

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 C is (d + 1)-separable and (d + 1)-Schurian where d is the degree of C. Indeed, it follows from [11, Corollary 4.8] that b(W) ≤ d where W is the Bose-Mesner algebra of C. Thus the above claim is the consequence of Theorem 4.8. In the rest of this section we confine ourselves to Schurian schemes on a prime number of points. According to Burnside’s theorem (see [23, Theorem 7.3]) any such scheme is isomorphic to a cyclotomic scheme and so is primitive.

5.2. Let p be a prime, d a divisor of p − 1, and H_{d} the subgroup of the group 𝔽_{p}^{∗} of order d where 𝔽_{p} is a field with p elements. Set

W_{p,d} = Z(G_{p,d})  (14)

where G_{p,d} is the group of all affine transformations x ↦ ax + b of 𝔽_{p} such that a ∈ H_{d} and b ∈ 𝔽_{p}. The cellular algebra W_{p,d} is the adjacency algebra of the cyclotomic scheme considered in [4]. It is a primitive one of dimension 1+(p−1)/d and each of its basis relations is of the form

R = {(x, y) : y − x ∈ cH_{d}, x, y ∈ 𝔽_{p}}  (15)

for some c ∈ 𝔽_{p}. It is well-known (see [4, p.389]) that Aut(W_{p,d}) coincides with G_{p,d} if d ≠ p − 1. We observe that

W_{p,d} = [A(R)], R ∈ R \ {Δ}  (16)

where R = R(W_{p,d}) and Δ = Δ^{(2)}(𝔽_{p}). Indeed, since [A(R)] ⊂ W_{p,d}, the group Aut([A(R)]) contains a regular subgroup x ↦ x+b, b ∈ 𝔽_{p}. So by Corollary 2.10.2 of [4] the algebra [A(R)] is of the form (14), whence (16) follows.

Theorem 5.2 Let W = W_{p,d}, d ≠ p − 1, Ŵ = Ŵ^{(2)} and V = 𝔽_{p}. Then Ŵ_{(u,v)} = Mat_{V^{2}} for all (u, v) ∈ V^{2} \ Δ.

Proof. We need the following statement.

Lemma 5.3 If d ≠ 1, then there exists an equivalence E′ ∈ E(Ŵ) such that V^{2}/E′ = R(W′) where W′ = W_{p,d′} for some d′ dividing d, d′ ≠ d.

Proof. We observe that p ≠ 2 and consider two cases. If d is a composite number, then it follows from [19, Proposition 4.1] that there exists d′ dividing d, d′ ≠ d, such that given u ∈ V the set R_{u} = ⋃_{U∈Cel(W′_{u})} U^{2} is a union of basis relations of the algebra W_{u}. Besides, for all v ∈ V we have (R_{u})^{g_{u,v}} = R_{v} where g_{u,v} is the automorphism of W′ of the form x ↦ x + (v − u), x ∈ V. Since the 2-fold Cartesian product of g_{u,v} belongs to Aut(Ŵ) and W_{v} ≤ r_{v}^{(2)}(W) for all v ∈ V (see statement (2) of Lemma 8.3), we conclude that the matrices ∑_{v∈V} I_{v} ⊗ A_{v} and ∑_{v∈V} A_{v} ⊗ I_{v} belong to Ŵ where A_{v} = A(R_{v}) − I_{v}. By [19, Lemma 4.2] the transitive closure of the union of the relations with these adjacency matrices is the equivalence relation on V^{2} \ Δ whose set of classes equals R(W′) \ {Δ}. Obviously this equivalence belongs to E(Ŵ). Thus, the required equivalence E′ on V^{2} can be obtained from it by adding a new class Δ.

If d is a prime, then set A_{v} to be the matrix of the permutation g_{v} : x ↦ 2v − x, x ∈ V. Then A_{v} ∈ W_{v} for all v ∈ V (this follows from [19, Theorem 4.1] for odd d and is straightforward for d = 2). So the matrices ∑_{v∈V} I_{v} ⊗ A_{v} and ∑_{v∈V} A_{v} ⊗ I_{v} belong as above to Ŵ. We have

(∑_{u∈V} I_{u} ⊗ A_{u})(∑_{v∈V} A_{v} ⊗ I_{v}) = ∑_{u,v∈V} I_{u}A_{v} ⊗ A_{u}I_{v} = ∑_{u,v∈V} I_{u,u^{gv}} ⊗ I_{v^{gu},v} =

∑_{u,v∈V} I_{u,2v−u} ⊗ I_{2u−v,v} = ∑_{b∈V} ∑_{u,v∈V,u−v=b/2} I_{u,u+b} ⊗ I_{v,v+b}

where I_{x,y}, x, y ∈ V, is a matrix unit. Set E′ to be the transitive closure of the union of the set Δ × Δ 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 Ŵ, we are done.

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 5.3 as follows. Let U be the class of E′ containing (u, v). Then U ∈ Cel^{∗}(Ŵ_{(u,v)}) and hence the matrix (A_{1}I_{U}A_{2}) ∘ J_{Δ} equals A(U)^{δ} where A(U) is the adjacency matrix of the relation U ⊂ V^{2} and A_{1} = I_{V} ⊗ J_{V}, A_{2} = J_{V} ⊗ I_{V}. So A(U)^{δ} ∈ Ŵ_{(u,v)} and by (16) we have

(Ŵ_{(u,v)})_{Δ} ≥ [A(U)^{δ}] = [A(U)]^{δ} = (W_{p,d′})^{δ}.

Thus Ŵ_{(u,v)} ≥ { \atop W_{p,d′}} according to Lemma 3.2 and we complete the proof by induction.

Theorem 5.4 A cyclotomic scheme on a prime number of points is 4-separable.

Proof. Let W be the adjacency algebra of such a scheme and Ŵ = Ŵ^{(2)}.. Then b(Ŵ) = 1 by Theorem 5.2. According to Theorem 4.8 we have s(Ŵ) ≤ 2, which implies by statement (3) of Theorem 4.6 that s(W) ≤ 4.

6 Extended algebras and (K, L)-regularity of graphs

6.1. By a colored graph Γ we mean a triple (V, E, c) where V = V (Γ) is a finite set (the vertex set of Γ), E = E(Γ) is a subset of V^{2} (the edge set of Γ) and c = c_{Γ} is a mapping from E to ℤ (the coloring of Γ). The image of an edge with respect to c is called the color of this edge, the set of all edges of the same color is called a color class of Γ. Two colored graphs are called isomorphic if there exists a bijection of their vertex sets preserving the colors of edges. Any such bijection is called an isomorphism of these graphs. The group of all isomorphisms of Γ to itself is denoted by Aut(Γ) and called the automorphism group of Γ. A colored graph Γ′ is called a subgraph of Γ if V (Γ′) ⊂ V (Γ), E(Γ′) ⊂ E(Γ) and c_{Γ′} is the restriction of c_{Γ}. If V (Γ′) = U and E(Γ′) = E(Γ) ∩ U^{2} for some U ⊂ V (Γ), we say that Γ′ is a subgraph of Γ induced by U.

A mapping g : V (K) → V (Γ) is called an embedding of a colored graph K into a colored graph Γ if E(K)^{g} ⊂ E(Γ) and c_{Γ}(u^{g}, v^{g}) = c_{K}(u, v) for all (u, v) ∈ E(K). (The mapping g is not necessarily an injection.) The set of all embeddings from K into Γ is denoted by Emb(K, Γ). Let g : U → V (Γ) be a mapping from a subset U of V (K) to V (Γ). Set

q_{Γ}(K, g) = |{h ∈ Emb(K, Γ) : h|_{U} = g}|.  (17)

Let L be a subgraph of K and d ≥ 0 an integer. We say that Γ is (K, L)-regular of degree d if q_{Γ}(K, g) = d for all g ∈ Emb(L, Γ); 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 Γ with symmetric edge set is (K, L)-regular of the same degree where V (K) = {1, 2}, E(K) = {(1, 2)}, V (L) = {1}, E(L) = ∅ and c_{K}(1, 2) equals the color of an edge of Γ.

To each cellular algebra W on V we associate a colored graph Γ = Γ(W) with V (Γ) = V, E(Γ) = 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, Γ satisfies the 3-vertex condition. If C is a scheme, we set Γ(C) = Γ(A(C)). Conversely, given a colored graph Γ = (V, E, c) we set

W (Γ) = [{A(c^{−1}(i)) : i ∈ ℤ}], C(Γ) = C(W (Γ)).

It is easy to see that W (Γ) ≤ Mat_{V}, colored classes of Γ are relations of W (Γ) and Aut(W (Γ)) = Aut(Γ). If φ is a weak isomorphism from W (Γ) to another cellular algebra W′, then we set Γ^{φ} = (V′, E′, c′) where V′ = V^{φ}, E′ = E^{φ} and c′ is defined by c^{−1}(i)^{φ} = (c′)^{−1}(i), i ∈ ℤ.

6.2. Let Γ be a colored graph on the set V = V (Γ) and m be a positive integer. Given a colored graph K with V (K) ⊂ [3m], a subgraph L of K with V (L) ⊂ [2m] and an integer d ≥ 0 we set

R_{Γ}(K, L, d) = \{(\overline{u}, \overline{v}) ∈ (V^{m})^{2} : ∃g ∈ Emb(L, Γ) : (q_{Γ}(K, g) = d ∧ (\overline{u} · \overline{v})_{i} = i^{g}, i ∈ V (L))\}

(18)

where \overline{u} · \overline{v} ∈ V^{2m} is the composition of \overline{u} and \overline{v}. If m = 1 and Γ = Γ(W) is a colored graph of a cellular algebra W, then the binary relation (18) is obviously a union (possibly empty) of colored classes of Γ. (Indeed, in this case the numbers q_{Γ}( , ) equal sums of the structure constants of W). The following statement generalizes this observation to an arbitrary m.

Theorem 6.1 Let Γ be a colored graph, W = W (Γ) its cellular algebra and m a positive integer. Then for all admissible K, L, d the following two statements hold:

(1) the set R_{Γ}(K, L, d) is a relation of the algebra Ŵ = Ŵ^{(m)},

(2) if φ is an m-isomorphism from W to another cellular algebra, then

R_{Γ}(K, L, d)φ̂ = R_{Γ^{φ}}(K, L, d)

where φ̂ = φ̂^{(m)} is the m-extension of φ.

Proof. Suppose first that K = L (and so V (K) ⊂ [2m]) and d = 1. In this case we have

R_{Γ}(K, L, d) = ⋂_{(i,j)∈E(K)} R̂_{i,j}

where R̂_{i,j} = \{(\overline{u}, \overline{v}) ∈ (V^{m})^{2} : ((\overline{u} · \overline{v})_{i}, (\overline{u} · \overline{v})_{j}) ∈ R_{i,j}\} with R_{i,j} = c_{Γ}^{−1}(c_{K}(i, j)) and V = V (Γ). Thus the required statements follow from the lemma below.

Lemma 6.2 Let W be a cellular algebra on V and R ∈ R(Ŵ) where Ŵ = Ŵ^{(m)}. Then for all i, j ∈ [2m] the following two statements hold:

(1) the set pr_{i,j}(R) = \{((\overline{u} · \overline{v})_{i}, (\overline{u} · \overline{v})_{j})) : (\overline{u}, \overline{v}) ∈ R\} belongs to R(\overline{W}) where \overline{W} = \overline{W}^{(m)},

(2) if φ is an m-isomorphism from W to another cellular algebra, then

pr_{i,j}(Rφ̂) = pr_{i,j}(R)\overline{φ}

where φ̂ = φ̂^{(m)} and \overline{φ} = \overline{φ}^{(m)}.

Proof. Without loss of generality we assume that i ∈ [m], j ∈ [m + 1, 2m]. (The case i ∈ [m + 1, 2m], j ∈ [m] can be treated in a similar way; the other two cases are reduced to the case in question with R replaced by Δ(X) or Δ(Y) where X, Y are cells of Ŵ such that R ⊂ X × Y.) Apply Lemma 2.1 to Ŵ, R and the equivalences E_{1} and E_{2} of Ŵ defined by the equality of the ith and (j − m)th coordinates respectively. Then the number of the pairs (\overline{u}, \overline{v}) ∈ R such that \overline{u}_{i} = u, \overline{v}_{j−m} = v does not depend on the choice of (u, v) ∈ R_{i,j} where R_{i,j} = pr_{i,j}(R). So

A(R_{i,j})^{δ} = cJ_{Δ} ∘ (A(E_{1})A(R)A(E_{2}))  (19)

where c is the above number. This implies that R_{i,j} is a relation of \overline{W}. In fact R_{i,j} is even a basis relation. Indeed, if S ∈ R(\overline{W}) is a proper subset of R_{i,j}, then obviously the matrix A(R)∘(A(E_{1})A(S)^{δ}A(E_{2})) is not a multiple of A(R), which contradicts the assumption that R ∈ R(Ŵ). This proves statement (1). Statement (2) is an immediate consequence of (19).

Let now K, L and d be arbitrary. Set

Q = \{(\overline{x}, \overline{y}, \overline{z}) ∈ (V^{m})^{3} : c_{Γ}((\overline{x} · \overline{y} · \overline{z})_{i}, (\overline{x} · \overline{y} · \overline{z})_{j}) = c_{K}(i, j), i, j ∈ V (K)\}

and

R = pr_{1,2}(Q), S = pr_{2,3}(Q), T = pr_{1,3}(Q).  (20)

where pr_{α,β}(Q) ⊂ (V^{m})^{2} is the (α, β)-projection of Q, α, β ∈ [3]. Then the set R_{Γ}(K, L, d) consists exactly of the pairs (\overline{u}, \overline{v}) ∈ (V^{m})^{2} such that

|\{(\overline{x}, \overline{y}, \overline{z}) : (\overline{u}, \overline{x}) ∈ E_{1}, (\overline{x}, \overline{y}) ∈ R, (\overline{y}, \overline{z}) ∈ S, (\overline{z}, \overline{v}) ∈ E_{2}, (\overline{x}, \overline{z}) ∈ T \}| = dn^{3m−|V (K)|} (21)

where

E_{l} = \{(\overline{a}, \overline{b}) ∈ (V^{m})^{2} : \overline{a}_{i} = \overline{b}_{i}, i + (l − 1)m ∈ V (L)\}, l = 1, 2.

On the other hand, it is easy to see that the integer in the left side of (21) equals the (\overline{u}, \overline{v})-entry of the matrix A = (A(E_{1})A(R)A(S)A(E_{2})) ∘ A(T). Besides, it follows from the definitions that each of the relations R, S, T is of the form R_{Γ}(K′, K′, 1) with V (K′) ⊂ [2m] and hence both statements of the theorem hold for it due to the first part of the proof. Thus, A ∈ Ŵ and R_{Γ}(K, L, d) coincides with the union of those basis relations of Ŵ for which the coefficient at the corresponding basis matrix in the decomposition of A equals the integer in the right side of (21). This proves the both statements.

It is convenient to weaken the property of a graph to be (K, L)-regular (see Subsection 6.1) as follows. Let K be a colored graph with V (K) ⊂ [3m] and L a subgraph of K with V (L) ⊂ [2m]. A colored graph Γ on V is called (K, L)-regular of degree d ≥ 0 with respect to a binary relation R on V^{m} if

R ∩ R_{Γ}(L) ⊂ R_{Γ}(K, L, d)

where R_{Γ}(L) = ⋃_{d≥0} R_{Γ}(K, L, d). Thus, Γ is (K, L)-regular of degree d iff Γ is (K, L)-regular of degree d with respect to (V^{m})^{2}. We observe that if R ∩ R_{Γ}(L) ≠ ∅, then d is uniquely determined by K, L and R. Otherwise, any nonnegative integer can be taken as d. Clearly, if Γ is (K, L)-regular of degree d with respect to R_{1} and R_{2}, then so is Γ with respect to R_{1} ∪ R_{2}. In this language Theorem 6.1 sounds as follows.

Corollary 6.3 Let Γ, W, m, φ and φ̂ be as in Theorem 6.1. Then

(1) Γ is (K, L)-regular with respect to any basis relation of Ŵ for all admissible K, L,

(2) if Γ is (K, L)-regular with respect to some relation R of Ŵ, then Γ^{φ} is (K, L)-regular of the same degree with respect to Rφ̂.

6.3. 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 [15] and generalized to colored graphs in [14]. In fact the latter deals with complete colored graphs Γ, i.e. those with E(Γ) = V (Γ)^{2}. Namely, let t ≥ 2 be a positive integer. A complete colored graph Γ satisfies the t-vertex condition if given a complete colored graph K with V (K) = [k], 2 ≤ k ≤ t, the number q_{Γ}^{∗}(K, g_{u,v}) depends only on c_{Γ}(u, v) for all u, v ∈ V (Γ) where g_{u,v} : [l] → {u, v} with l = |{u, v}| is the bijection taking 1 to u and q_{Γ}^{∗}(K, g_{u,v}) is defined similarly to q_{Γ}(K, g_{u,v}) with additional assumption in (17) that h is an injection. (In terms of [14] the integer q_{Γ}^{∗}(K, g_{u,v}) divided by the order of the subgroup of Aut(K) leaving fixed the points of [l], equals the number of the subgraphs of Γ of the type K with respect to the pair (u, v).) It is convenient to extend this definition to an arbitrary colored graph Γ allowing K to be an arbitrary colored graph on [k] and replacing q_{Γ}^{∗}(K, g_{u,v}) by q_{Γ}(K, g_{u,v}). This does not lead to confusion because it is easy to see that for a complete colored graph Γ any number q_{Γ}(K, g_{u,v}) equals a linear combination of the numbers q_{Γ}^{∗}(K′, g_{u,v}) for some complete colored graphs K′ with |V (K′)| ≤ |V (K)|. One can see that according to the last definition a colored graph Γ satisfies the t-vertex condition iff Γ is (K, L)-regular for all colored graphs K with at most t vertices and all its subgraphs L with V (L) = {i, j} and E(L) = {(i, j)}. Clearly, we can assume that V (K) ⊂ [t] and V (L) ⊂ [2].

Theorem 6.4 A colored graph associated with an m-closed cellular algebra satisfies the 3mvertex condition.

Proof. Let Γ be a colored graph satisfying the hypothesis of the theorem. Then it suffices to prove that Γ is (K, L)-regular for all K, L with V (K) ⊂ [3m], V (L) = {i, j} ⊂ [2m] and E(L) = {(i, j)}. By statement (1) of Corollary 6.3 the graph Γ is (K, L)-regular of some degree d_{R} with respect to any R ∈ R(Ŵ^{(m)}). It follows from statement (1) of Lemma 6.2 and the assumption on L that d_{R} can be chosen not depending on R. Denoting this number by d we see that the graph Γ is (K, L)-regular of degree d with respect to (V^{m})^{2}, i.e. (K, L)- regular.

Proof of Theorem 4.3. Let Γ be a colored graph of W and m = ⌈n/3⌉. Denote by K a colored graph on the set [n] isomorphic to Γ. Then by statement (1) of Corollary 6.3 the graph Γ is (K, L)-regular of positive degree with respect to some basis relation R of Ŵ^{(m)} where L is the graph without vertices. Statement (2) of Corollary 6.3 shows then that given any weak isomorphism φ from W to another cellular algebra the graph Γ^{φ} is also (K, L)- regular of the same positive degree with respect to R^{φ}. This means that Γ^{φ} is isomorphic to K and also that φ is induced by the composition isomorphism from Γ to Γ^{φ} via K. Thus s(W) ≤ m. Further, according to Theorem 6.4 a colored graph associated with the m-closure of W satisfies the 3m-vertex condition and hence the n-vertex condition because n ≤ 3m. So this graph is associated with a Schurian cellular algebra by [14, Proposition 2.6.2]. Thus t(W) ≤ m.

7 Distance-regular graphs

7.1. Throughout the section we use notation from Section 6. A colored graph with symmetric one-color edge set not meeting the diagonal is treated below as a graph in sense of [4].

Let Γ be a connected graph with vertex set V and edge set R. Let us denote by R_{i}, i ∈ [0, d], the binary relation on V “to be at distance i in Γ”, where d is the diameter of Γ. In particular, R_{0} = Δ^{(2)}(V), R_{1} = R. According to [4, Chapter 1] the graph Γ is called distance-regular if C(Γ) = (V, {R_{i}}_{i=0}^{d}) where C(Γ) is the scheme of Γ. In this case the intersection numbers of C(Γ) 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 ∈ [d], called the intersection numbers or parameters of Γ. The cellular algebra W (Γ) (coinciding with the Bose-Mesner algebra of C(Γ)) equals ℂ[A_{0}, …, A_{d}] = ℂ[A_{1}] where A_{i} = A(R_{i}), i ∈ [0, d]. In particular, M(W (Γ)) = {A_{i}}_{i=0}^{d}. If distance-regular graphs Γ and Γ′ have the same intersection numbers, then the mapping A_{1} ↦ A′_{1} yields a weak isomorphism from W (Γ) to W (Γ′) taking A_{i} to A′_{i}, i ∈ [0, d]. Conversely, if φ is a weak isomorphism from W (Γ) to another cellular algebra W′ ≤ Mat_{V′}, then the corresponding structure constants of W (Γ) and W′ coincide and so by [4, Proposition 2.7.1] the graph Γ^{φ} = (V′, R^{φ}) is distance-regular, (R^{φ})_{i} = (R_{i})^{φ}, i ∈ [0, d], the parameters of Γ and Γ^{φ} coincide and W′ = W (Γ^{φ}).

Following [4] we say that a distance-regular graph Γ is uniquely determined by parameters if its intersection numbers determine Γ up to isomorphism. Also Γ is called distancetransitive, if the group Aut(Γ) acts transitively on any of the sets R_{i}, i ∈ [0, d]. Thus the following statement trivially holds.

Proposition 7.1 Let Γ be a distance-regular graph and C = C(Γ). Then

(1) Γ is uniquely determined by parameters iff s(C) = 1,

(2) Γ is distance-transitive iff t(C) = 1.

Below we assume that the relation R_{i} of the scheme C associated with a distance-regular graph Γ has color i in the colored graph Γ(C).

7.2. Let n, k be nonnegative integers, k ≤ n. The graph Γ = J(n, k) the vertices of which are k-subsets of [n] and the edges are pairs (u, v) with |u∩v| = k−1 is called a Johnson graph. It is known that Γ is a distance-transitive graph of diameter d = min(k, n − k). According to [4, Section 9.1.B] 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 Γ is isomorphic either to Γ or to one of the three Chang graphs which are not distance-transitive (see [4, p.105]). Below by J (n, k) we denote the scheme of the graph Γ and call it a Johnson scheme. Similarly, the scheme of a Chang graph will be called a Chang scheme.

Theorem 7.2 Let C be the scheme of a distance-regular graph with parameters of some Johnson graph. Then s(C) ≤ 2 and t(C) ≤ 2. More exactly,

(1) if C = J (n, k), then

s(C) = \{ \begin{matrix}1, & if (n, k) ≠ (8, 2); \\ 2, & otherwise \end{matrix}

and t(C) = 1 for all n, k,

(2) if C is a Chang scheme, then s(C) = t(C) = 2.

Proof. It follows from the above discussion and Proposition 7.1 that statement (1) holds for (n, k) ≠ (8, 2) and also that s(C) ≥ 2, t(C) = 1 if C = J (8, 2) and s(C) ≥ 2, t(C) ≥ 2 if C 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(C) = 2 if C 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(C) = 2 if C = J (8, 2) or C is a Chang scheme.

7.3. Let d ≥ 0 and q ≥ 2 be integers. Let us define the Hamming graph Γ = H(d, q) to be the product of d copies of the complete graph on the set X = [q]. This means that Γ has vertex set X^{d} and two vertices of Γ are adjacent iff they differ in precisely one coordinate. It is known that Γ is a distance-transitive graph of diameter d. According to [4, Section 9.2.B] it is uniquely determined by parameters unless q = 4, d ≥ 2. If q = 4, then any distance-regular graph having the same parameters as Γ is isomorphic to the graph D_{a,b} which is the direct product of a copies of the Shrikhande graph (see [4, p.104]) and b copies of the complete graph on 4 vertices, where a ≥ 0, b ≥ 0 are some integers with 2a + b = d. Obviously, Γ = D_{0,d}. If a ≥ 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 7.1 and Lemma 7.4 below.

Theorem 7.3 Let C be the scheme of a distance-regular graph with parameters of some Hamming graph. Then s(C) ≤ 2 and t(C) ≤ 2. More exactly,

(1) if C = H(d, q), then

s(C) = \{ \begin{matrix}1, & if q ≠ 4 or d ≤ 1; \\ 2, & otherwise \end{matrix}

and t(C) = 1 for all d, q,

(2) if C is a scheme of a Doob graph, then s(C) = t(C) = 2.

Let V_{a,b} and R_{a,b} be the vertex set and the edge set of the graph D_{a,b}. Set Δ_{a,b} = Δ^{(2)}(V_{a,b}), G_{a,b} = Aut(D_{a,b}) and W_{a,b} = W (D_{a,b}).

Lemma 7.4 The following two statements hold:

(1) the sets R_{a,0}×Δ_{0,b} and Δ_{a,0}×R_{0,b} are relations of the algebra \overline{W}_{a,b} = \overline{W_{a,b}}^{(2)}. Moreover,

\overline{W}_{a,b} = Z(G_{a,0}) ⊗ Z(G_{0,b}).  (22)

(2) If φ is a 2-isomorphism from W_{a,b} to W_{a′,b′} and (R_{a,b})^{φ} = R_{a′,b′}, then

(R_{a,0} × Δ_{0,b})\overline{φ} = R_{a′,0} × Δ_{0,b′}, (Δ_{a,0} × R_{0,b})\overline{φ} = Δ_{a′,0} × R_{0,b′}

where \overline{φ} = \overline{φ}^{(2)}. Moreover, a = a′ and b = b′.

Proof. Let Γ = Γ_{a,b} be a colored graph associated with W_{a,b} and K be the complete graph with V (K) = [4] all edges of which have the color of the relation R_{a,b}. It is easy to see that given g ∈ Emb(K, Γ) the vertices of the image of g differ in one fixed coordinate. So the number q_{Γ}(K, g) equals the corresponding number for the Shrikhande graph (Γ = Γ_{1,0}) or the complete graph on 4 vertices (Γ = Γ_{0,1}) depending on whether the pair (1^{g}, 2^{g}) belongs to R_{a,0} × Δ_{0,b} or Δ_{a,0} × R_{0,b}. Since the last numbers equal 0 and 2 respectively, we see that

R_{a,0} × Δ_{0,b} = pr_{1,2}(R(K, L, 0)) ∩ R_{a,b}, Δ_{a,0} × R_{0,b} = pr_{1,2}(R(K, L, 2)) ∩ R_{a,b}  (23)

where L is the subgraph of K induced by the set [2], the relation R(K, L, d), d = 0, 2, is defined according to (18) and pr_{i,j}(R) is as in statement (1) of Lemma 6.2. Thus the first part of statement (1) follows from the first statements of Theorem 6.1 and Lemma 6.2. Equalities (23) due to the second statements of Theorem 6.1 and Lemma 6.2 also imply the first part of statement (2). The second part follows from the first one, the obvious equalities d(R_{a,0} × Δ_{0,b}) = 6a, d(Δ_{a,0} × R_{0,b}) = 3b and statement (1) of Lemma 2.2.

Let us prove formula (22). Without loss of generality we assume that a > 0. It is wellknown 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}×Δ_{0,b} and T_{a,b} = T_{a,0} × Δ_{0,b} are relations of the algebra \overline{W}_{a,b}.

Denote by K′ the graph obtained from K 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 ∈ Emb(K′, Γ) the number q_{Γ}(K′, g) equals 2 or 0 depending on whether the pair (1^{g}, 2^{g}) belongs to S_{a,b} or R′_{a,b} \ S_{a,b}. So

S_{a,b} = pr_{1,2}(R(K′, L′, 2)) ∩ R′_{a,b}

where L′ is the subgraph of K′ induced by the set [2]. Thus S_{a,b} is a relation of \overline{W}_{a,b}. A straightforward computation shows that

A(R′_{a,b}) ∘ (A(R_{a,0} × Δ_{0,b}) · A(S_{a,b})) = 2aA(S_{a,b}) + 4aA(T_{a,b}) + A(T′)

where T′ = R′_{a,b} \ (S_{a,b} ∪ T_{a,b}). Since the left side belongs to \overline{W}_{a,b}, we conclude that A(T_{a,b}) ∈ \overline{W}_{a,b}, which proves the claim.

Now it follows from above that the algebra \overline{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 \overline{W}_{1,0} ↑ Sym(a) of \overline{W}_{1,0} by Sym(a) as defined in [11]. By [11, Theorem 3.4 and formula (5)] we have \overline{W}_{a,0} = Z(G_{a,0}). This implies that \overline{W}_{a,b} contains Z(G_{a,0}) ⊗ \{I_{V_{0,b}}\}. On the other hand, by the second of the equalities (23) and the distance-transitivity of D_{0,b} we see that it also contains {I_{V_{a,0}}} ⊗ Z(G_{0,b}). Thus \overline{W}_{a,b} ≥ Z(G_{a,0}) ⊗ Z(G_{0,b}). Since the converse inclusion is obvious, we are done.

The following assertion immediately follows from statement (2) of Lemma 7.4.

Corollary 7.5 The Doob graphs are pairwise nonisomorphic and nonisomorphic to the corresponding Hamming graph.

Remark 7.6 It follows from the proof of Lemma 7.4 that the graphs D_{a,b} can be distinguished by means of the 4-vertex condition.

7.4. Let 𝔽 be a finite field with q elements, n, k be nonnegative integers, k ≤ n. The graph Γ = J_{q}(n, k) the vertices of which are k-subspaces of the n-dimensional linear space over 𝔽 and the edges are pairs (u, v) with dim(u∩v) = k −1, is called a Grassmann graph. It is known that Γ is a distance-transitive graph of diameter d = min(k, n−k). According to [4, p.272] this graph is uniquely determined by parameters for \frac{2}{3}n ≤ k ≤ n − 3, (q, k) ≠ (2, \frac{2}{3}n).

Theorem 7.7 Let C be the scheme of the Grassmann graph J_{q}(n, k). Then s(C) ≤ 2 and t(C) = 1 for all q, n, k. Moreover, s(C) = 1 whenever \frac{2}{3}n ≤ k ≤ n − 3, (q, k) ≠ (2, \frac{2}{3}n).

Proof. By Proposition 7.1 it suffices to prove that s(C) ≤ 2. One can easily find (see also [4, Section 9.3]) that the graph Γ = J_{q}(n, k) satisfies the following two conditions:

(1) given two vertices u, v of Γ at distance 2, the subgraph of Γ induced by the set of vertices adjacent simultaneously to u and v is isomorphic to the Hamming graph H(2, q + 1),

(2) given three pairwise nonadjacent vertices u, v, w of Γ, the subgraph of Γ induced by the set of vertices adjacent simultaneously to u, v and w has no edges.

This means that the colored graph of the scheme C(Γ) is (K_{i}, L_{i})-regular of degree d_{i}, i ∈ [6], where

(K_{i}, L_{i}, d_{i}) = \{ \begin{matrix}(K_{2,1}, K_{2}, (q + 1)^{2}), & if i = 1; \\ (K_{2,1,1}, K_{2,1}, 2q), & if i = 2; \\ (K_{2,1,1,1}, K_{2,1,1}, q − 1), & if i = 3; \\ (K_{2,2,1}, K_{2,2}, 2), & if i = 4; \\ (K_{2,2,1,1}, K_{2,2}, 0), & if i = 5; \\ (K_{3,1,1}, K_{3,1}, 0), & if i = 6 \end{matrix}

and K_{n_{1},...,n_{s}} is the complete multipartite graph with parts [N_{i−1} +1, N_{i−1} +n_{i}], i ∈ [s], where N_{i} = ∑_{j=1}^{i} n_{j}. ^{2} (Here each pair of distinct vertices of the graph K_{i} has the color of the adjacency relation of Γ if these vertices are adjacent in K_{i}, and the color of the relation “to be at distance 2 in Γ” if they are not.) Indeed, the (K_{i}, L_{i})-regularity of degree d_{i}, i ∈ [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 ≠ 3 (see [6, p.92]). 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 (K_{i}, L_{i})- regularity of degree d_{i}, i ∈ [5], is equivalent to condition (1). Finally, the (K_{6}, L_{6})-regularity of degree 0 is obviously equivalent to condition (2).

2Thus K_{n} denotes the graph on the set [n] with no edges, i.e. \overline{K}_{n} in notation of [4].

Let φ be a 2-isomorphism of the algebra W = W (Γ) to another cellular algebra W′. Then W′ = W (Γ′) where Γ′ = Γ^{φ} is a distance-regular graph with the same parameters as Γ. It follows from statement (2) of Corollary 6.3 that Γ′ is (K_{i}, L_{i})-regular of degree d_{i} for all i ∈ [6]. So Γ′ satisfies conditions (1) and (2). This implies by [4, Corollary 9.3.8] 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 Γ′ is isomorphic to J_{q}(n, k). Thus φ ∈ Isow_{∞}(W, W′).

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 [18]). Finally, we notice that the 2-separability of the scheme J_{q}(n, 2) for n ≥ 6 follows also from [15, Lemma 5] and Theorem 6.4.

7.5. 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.

Lemma 7.8 Let W be a cellular algebra and m a positive integer. Assume that any cellular algebra lying between W and \overline{W}^{(∞)} the colored graph of which satisfies the 3m-vertex condition, coincides with \overline{W}^{(∞)}. Then t(W) ≤ m.

Proof. According to Theorem 6.4 the colored graph associated with the algebra \overline{W}^{(m)} satisfies the 3m-vertex condition. By the lemma’s hypothesis this implies that \overline{W}^{(m)} = \overline{W}^{(∞)}.

Let Γ be a strongly regular graph with the automorphism group of rank 4. Then there are exactly two cellular algebras between W and \overline{W}^{(∞)} where W = W (Γ). So the hypothesis of Lemma 7.8 is satisfied for m = 2 unless Γ satisfies the 6-vertex condition. In this case it follows that t(W) ≤ 2. Since obviously t(W) > 1, we conclude that t(W) = 2. Such a situation arises, for instance, if Γ is the Shrikhande graph, one of the graphs from [5, Theorem 1] for m ≥ 3, q > 2, or the graph on 256 vertices found by A. V. Ivanov (see [17]). 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 [14, p.74] this graph does not satisfy the 6-vertex condition.

7.6. Let P be a finite projective plane of order q with the point set P and the line set L (see [8]). Denote by Γ = Γ(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 Γ is a distance-regular graph of diameter 3 and valency q + 1. Moreover, any distance-regular graph with the same parameters as Γ is of the form Γ(P′) for some projective plane P′ of order q.

Theorem 7.9 Let P be a projective plane of order q and C be the scheme associated with the graph Γ = Γ(P). Then (1) s(C) ≤ O(log log q) and t(C) ≤ O(log log q),

(2) t(C) = 1 iff P is a Galois plane,

(3) s(C) ≤ 6 whenever P is a Galois plane.

Proof. A subset of P ∪ 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 ∪ L is the minimal closed set of P containing a set X ⊂ P ∪ 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 (Γ). Now it follows from [8, Theorem 3.2.17] 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) ≤ 5 and statement (3) is the consequence of Theorem 4.8. It follows from [8, Theorem 3.2.18] 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) ≤ O(log log q) and so statement (1) follows from Theorem 4.8. 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 [8, Theorems 4.4.20, 1.4.5]). Since the latter is a necessary condition for the Schurity of W, statement (2) follows.

8 Appendix

8.1. Throughout the section let m be a positive integer, W ≤ Mat_{V} be a cellular algebra, Ŵ = Ŵ^{(m)}, \overline{W} = \overline{W}^{(m)} and Δ^{(i)} = Δ^{(i)}(V) for all i.

Let Ê = Ê^{(m)} = Ê^{(m)}(W) and E = E^{(m)} = E^{(m)}(W) be the equivalences with supports V^{m} and Δ^{(m−1)}×V defined by the equality of the mth coordinates. Since Ŵ ≥ Z_{m}(V), we see that Ê, E ∈ E(Ŵ). It is easy to see that Ê ⊃ E and their classes are of the form

Û_{v} = V^{m−1} × {v}, U_{v} = Δ^{(m−1)} × {v}  (24)

respectively where v ∈ V. Besides, it follows from the definitions that ŴÊ ⊂ ∑_{v∈V} Mat_{V^{m−1}} ⊗{I_{v}} and Ŵ_{E} ⊂ ∑_{v∈V} Mat_{Δ^{(m−1)}} ⊗{I_{v}}. For X ⊂ V set

Ê_{X} = ⋃_{v∈X}(Û_{v})^{2}, E_{X} = ⋃_{v∈X}(U_{v})^{2}.  (25)

Lemma 8.1 The mapping X ↦ Ê_{X} (resp. X ↦ E_{X}) defines a bijection between the cells of \overline{W} and the indecomposable components of the equivalence Ê (resp. E).

Proof. It suffices to verify that if X ∈ Cel(\overline{W}), then Ê_{X} and E_{X} are indecomposable equivalences of Ŵ. It follows from Lemma 3.2 that the set R = (V^{m−1} × X)^{2} is a relation of Ŵ. Since Ê_{X} = Ê ∩ R and E_{X} = E ∩ R, we conclude that Ê_{X} and E_{X} are equivalences of Ŵ. Further, if Ê_{Y} (resp. E_{Y}) is an indecomposable component of Ê_{X} (resp. E_{X}), then Y is a cellular set of \overline{W} by statement (1) of Lemma 6.2 with R = Ê_{Y} (resp. R = E_{Y}) and i = j = m. Thus Y = X and we are done.

For v ∈ V and m ≥ 2 set

r̂_{v}(W) = r̂_{v}^{(m)}(W) = (Ŵ_{Ê,Û_{v}})ζ̂_{v}^{−1}, r_{v}(W) = r_{v}^{(m)}(W) = (Ŵ_{E,U_{v}})^{ζ_{v}^{−1}}

where ζ̂_{v} : V^{m−1} → Û_{v} and ζ_{v} : V → U_{v} are natural bijections.

Lemma 8.2 In the above notation the following statements hold:

(1) the algebra r_{v}(W) is (m − 1)-closed and also the algebra r̂_{v}(W) contains the (m − 1)- extended algebra of r_{v}(W),

(2) r_{v}(W) ≥ \overline{W_{v}}^{(m−1)} and r̂_{v}(W) ≥ Ŵ_{v}^{(m−1)}.

Proof. It is easy to see that

r̂_{v}(W) ≥ (Z_{m}(V)_{Ê,Û_{v}})ζ̂_{v}^{−1} = Z(Sym(V)_{v}, V^{m−1}) ≥ Z_{m−1}(V)  (26)

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 3.2 with W′ = 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 (9) that the algebra W^{m−1} ⊗ {I_{V} } is contained in Ŵ and hence in ŴÊ. So by (26) we have Ŵ^{(m−1)} ≤ r̂_{v}(W) and hence W ≤ r_{v}(W). Besides, I_{(v,...,v)} = (IÛ_{v}I_{Δ}IÛ_{v})ζ̂_{v}^{−1} whence I_{v} ∈ r_{v}(W). Thus

r_{v}(W) = (r̂_{v}(W)_{Δ^{(m−1)}})^{δ^{−1}} ≥ [W, I_{v}] = W_{v}

where δ : V → Δ^{(m−1)} is a natural bijection.

8.2. Let φ ∈ Isow_{m}(W, W′). Then Êφ̂ = Ê′ and Eφ̂ = E′ where Ê′ = Ê^{(m)}(W′) and E′ = E^{(m)}(W′) (see Lemma 2.2). Let (v, v′) ∈ X × X′ where X ∈ Cel(\overline{W}), X′ ∈ Cel(\overline{W′}) with X\overline{φ} = X′. Then by statement (2) of Lemma 6.2 we have F̂ φ̂ = F̂′ and F φ̂ = F′ where F̂ = Ê_{X}, F̂′ = Ê′_{X′} and F = E_{X}, F′ = E′_{X′} (see (25)). By Lemma 8.1 these equivalences are indecomposable: F̂ and F in Ŵ, whereas F̂′ and F′ in Ŵ′. Set

φ̂_{Û_{v},Û′_{v′}} = π_{F̂′,Û′_{v′}} ∘ φ̂F̂ ∘ π_{F̂,Û_{v}}^{−1}, φ_{U_{v},U′_{v′}} = π_{F′,U′_{v′}} ∘ φ̂_{F} ∘ π_{F,U_{v}}^{−1}

where φ̂F̂ : ŴF̂ → Ŵ′F̂′ and φ̂_{F} : Ŵ_{F} → Ŵ′_{F′} are the restriction isomorphisms induced by φ̂, and Û′_{v′} and U′_{v′} are the classes of the equivalences F̂′ and F′ corresponding to v′. Then the mappings

r̂_{v,v′}(φ) = (χ̂_{v′})^{−1} ∘ φ̂_{Û_{v},Û′_{v′}} ∘ χ̂_{v}, r_{v,v′}(φ) = (χ_{v′})^{−1} ∘ φ_{U_{v},U′_{v′}} ∘ χ_{v}  (27)

belong to Isow(r̂_{v}(W), r̂_{v′}W′) and Isow(r_{v}(W), r_{v′}(W′)) respectively where χ̂_{v} : r̂_{v}(W) → Ŵ_{F̂,Û_{v}} and χ_{v} : r_{v}(W) → Ŵ_{F,U_{v}} are the weak isomorphisms induced by the bijections ζ̂_{v} and ζ_{v}, and χ̂_{v′}, χ_{v′} are defined similarly.

Lemma 8.3 In the above notation the following statements hold:

(1) r_{v,v′}(φ) ∈ Isow_{m−1}(r_{v}(W), r_{v′}(W′)) and also r̂_{v,v′}(φ) extends the (m − 1)-extension of r_{v,v′}(φ),

(2) φ can be extended to an (m − 1)-isomorphism φ_{v,v′} : W_{v} → W′_{v′} such that φ_{v,v′}(I_{v}) = I_{v′}. In addition, r_{v,v′}(φ) (resp. r̂_{v,v′}(φ)) extends the (m−1)-closure (resp. the (m−1)- extension) of φ_{v,v′}.

Proof. To prove statement (1) we observe that

(I_{Δ^{(m−1)}(V)})^{ζ_{v}} = π_{F̂,Û_{v}}(A ∘ IX̂), (I_{Δ^{(m−1)}(V′)})^{ζ_{v′}} = π_{F̂′,Û′_{v′}}(A ∘ IX̂′)

where A = A(F), A′ = A(F′) and X̂, X̂′ are the supports of F̂ and F̂′. Since A ∈ Z_{m}(V), we have

φ̂F̂(A ∘ IX̂) = φ̂(A) ∘ φ̂(IX̂) = A′ ∘ IX̂′.

Thus

ψ̂_{v,v′}(I_{Δ^{(m−1)}(V)}) = I_{Δ^{(m−1)}(V′)}  (28)

where ψ̂_{v,v′} = r̂_{v,v′}(φ). Further,

C^{ζ_{v}} = π_{F̂,Û_{v}}((C ⊗ I_{V}) ∘ Â), (C′)^{ζ_{v′}} = π_{F̂′,Û′_{v′}}((C′ ⊗ I_{V′}) ∘ Â′)

where C ∈ r_{v}(W)^{m−1}, C′ ∈ r_{v′}(W′)^{m−1} and Â = A(Ê), Â′ = A(Ê′). Besides,

φ̂F̂((C ⊗ I_{V}) ∘ Â) = φ̂(C ⊗ I_{V}) ∘ φ̂(Â) = (ψ_{v,v′})^{m−1}(C) ⊗ I_{V′}) ∘ Â′,

where ψ_{v,v′} = r_{v,v′}(φ), whence

ψ̂_{v,v′}(C) = (ψ_{v,v′})^{m−1}(C), C ∈ r_{v}(W)^{m−1}.  (29)

The equalities (28) and (29) show that the restriction of ψ̂_{v,v′} to { \atop r_{v}(W)} is the (m−1)-extension of ψ_{v,v′}.

To prove statement (2) we note that according to statement (1) and Lemma 8.2 it suffices to verify only that ψ_{v,v′}(A) = φ(A), A ∈ W, and ψ_{v,v′}(I_{v}) = I_{v′}. Let us prove that

φ̂^{(m)}(A ⊗ I_{V}) = φ̂^{(m−1)}(A) ⊗ I_{V′}, A ∈ Ŵ^{(m−1)}.  (30)

Indeed, for A ∈ W^{m−1} this follows from the second condition of the definition of m-extension whereas for A = I_{Δ^{(m−1)}(V)} from the first one and the equality

φ̂^{(m)}(I_{Δ^{(m−1)}(V)} ⊗ I_{V}) = I_{Δ^{(m−1)}(V′)} ⊗ I′_{V} = φ̂^{(m−1)}(I_{Δ^{(m−1)}(V)}) ⊗ I_{V′}.

It follows from the definition of ψ̂_{v,v′} and (30) that ψ̂_{v,v′}(A) = φ̂^{(m−1)}(A), A ∈ Ŵ^{(m−1)}, and ψ̂_{v,v′}(I_{(v,...,v)}) = I_{(v′,...,v′)}, which completes the proof.

8.3. 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 ∈ V.

Theorem 8.4 Let X ∈ Cel(\overline{W}) and v ∈ X. Then for any basis relation S of the algebra r_{v}(W) the set

R = ⋃_{v′∈X} ψ_{v,v′}(S)

is a basis relation of the algebra \overline{W} where ψ_{v,v′} = r_{v,v′}(id_{W}).

Proof. Let F = E_{X} and C be the adjacency matrix of the binary relation on V^{m} consisting of all pairs (\overline{u}, \overline{v}) ∈ Δ^{(m)} × (Δ^{(m−1)} × X) such that \overline{u}_{1} = \overline{v}_{1}. Then C ∈ Ŵ and so

ρ : Ŵ_{F} → Ŵ_{Δ}, A ↦ CAC^{T}

is a linear mapping. A straightforward check shows that

ρ(A) = (∑_{v′∈X} π_{F,U_{v′}}(A)^{ζ_{v′}^{−1}})^{δ}.

Thus it suffices to prove that ρ(A) is a multiple of a basis matrix of Ŵ_{Δ} for any basis matrix A of Ŵ belonging to Ŵ_{F}. Let us consider another mapping

τ : Ŵ_{Δ} → Ŵ_{F} , B ↦ C^{T} BC.

Since CC^{T} = |X|I_{Δ}, τ is an injective linear mapping preserving the Hadamard multiplication and satisfying ρ(τ(B)) = |X|^{2}B for all B ∈ Ŵ_{Δ}. The last equality also implies that given B ∈ M(Ŵ_{Δ}) there exists a matrix A′ ∈ Ŵ_{F} with nonnegative entries such that ρ(A′) = B. So ρ(A) is a multiple of B for any basis matrix A with A∘A′ = 0. Since obviously each basis matrix of Ŵ belonging to Ŵ_{F} can be obtained as A in such a way when B runs over M(Ŵ_{Δ}), we are done.

Corollary 8.5 Let W ≤ Mat_{V}. Then

(\overline{W})_{v} ≤ r_{v}(W) ≤ \overline{(W_{v})}  (31)

for all v ∈ V.

Proof. To prove the first inclusion it suffices to prove that \overline{W} ≤ r_{v}(W), which is a straightforward consequence of Theorem 8.4. On the other hand, applying the same theorem to W = W_{v} and X = \{v\} we obtain r_{v}(W_{v}) = \overline{(W_{v})}. Since obviously r_{v}(W) ≤ r_{v}(W_{v}), the right inclusion follows.

References

[1] L. Babai, On the order of uniprimitive permutation groups, Annals of Math., 113 (1981), 553–568.

[2] L. Babai, Automorphism Groups, Isomorphism, reconstruction, in: R. L. Graham, M. Grötschel, L. Lovász (eds): Handbook of combinatorics, vol. 2, Amsterdam (etc.), Elsevier (etc.), 1995, 1447–1540.

[3] E. Bannai, T. Ito, Algebraic Combinatorics I. Association schemes, Benjamin Cummings, London, 1984.

[4] A. E. Brouwer, A. M. Cohen, A. Neumaier, Distance-Regular graphs, Springer, Berlin, 1989.

[5] A. E. Brouwer, A. V. Ivanov, M. H. Klin, Some new strongly regular graphs, Combinatorica, 9 (1989), 339–344.

[6] A. E. Brouwer, J. H. van Lint, Strongly Regular Graphs and Partial Geometries. In: “Enumeration and Design – Proc. Silver Jubilee Conf. on Combinatorics. Waterloo, 1982”, (ed. D. M. Jackson, S. A. Vanstone), Acad. Press Toronto, 1984, 85–122.

[7] P. J. Cameron, Permutation groups, Cambridge University Press, 1999.

[8] P. Dembowski, Finite Geometries, Springer, Berlin, 1968.

[9] S. Evdokimov, M. Karpinski, I. Ponomarenko, On a New High Dimensional Weisfeiler-Leman Algorithm, Journal of Algebraic Combinatorics, 10 (1999), 29–45.

[10] S. A. Evdokimov, I. N. Ponomarenko, Two Inequalities for the Parameters of a Cellular Algebra, Zapiski Nauchnykh Seminarov POMI, 240 (1997), 82–95.

[11] S. A. Evdokimov, I. N. Ponomarenko, On Primitive Cellular Algebras, Zapiski Nauchnykh Seminarov POMI, 256 (1999), 38–68.

[12] S. A. Evdokimov, I. N. Ponomarenko, On highly closed cellular algebras and highly closed isomorphisms, Electronic J. of Combinatorics, 6 (1999), #R18.

[13] S. A. Evdokimov, I. N. Ponomarenko, G. Tinhofer, On a New Class of Weakly Compact Graphs, Techn. Univ. München, Fak. f. Math., Report TUM M9715, (1997) (accepted for publication in Discrete Math.).

[14] I. A. Faradžev, M. H. Klin, M. E. Muzichuk, Cellular rings and groups of automorphisms of graphs, in: I.A. Faradžev et al. (eds): Investigations in algebraic theory of combinatorial objects, Kluwer Acad. Publ., Dordrecht, 1994, 1–152.

[15] D. G. Higman, Characterization of families of rank 3 permutation graphs by the subdegree I, II, Arch. Math., 21 (1970), 151–156; 353–361.

[16] D. G. Higman, Coherent configurations 1., Rend. Mat. Sem. Padova, 44 (1970), 1–25.

[17] A. V. Ivanov, Non rank 3 strongly regular graph with the 5-vertex condition, Combinatorica, 9 (1989), 255–260.

[18] E. Mendelsohn, Every (finite) group is the group of automorphisms of a (finite) strongly regular graph, Ars Combinatoria, 6 (1978), 75–86.

[19] M. E. Muzichuk, G. Tinhofer, Recognizing circulant graphs of prime order in polynomial time, Electronic J. of Combinatorics, 5 (1998), #R25.

[20] S. S. Shrikhande, The uniqueness of the L_{2} association scheme, Ann. Math. Statist., 30 (1959), 781–798.

[21] B. Ju. Weisfeiler (editor), On construction and identification of graphs, Springer Lecture Notes, 558, 1976.

[22] B. Ju. Weisfeiler, A. A. Leman, Reduction of a graph to a canonical form and an algebra which appears in the process, NTI, Ser.2, (1968), 9, 12–16.

[23] H. Wielandt, Finite permutation groups, Academic press, New York - London, 1964.

[24] H. Wielandt, Permutation groups through invariant relations and invariant functions, Lect. Notes Dept. Math. Ohio St. Univ., Columbus, 1969.