On highly closed cellular algebras and highly closed isomorphisms ^{∗}

Dedicated to A. A. Lehman and B. Yu. Weisfeiler on the occasion of the 30th anniversary of their paper where the cellular algebra first appeared. Sapienti sat...

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: June 2, 1998; Accepted: November 6, 1998

Abstract

We define and study m-closed cellular algebras (coherent configurations) and m-isomorphisms of cellular algebras which can be regarded as mth approximations of Schurian algebras (i.e. the centralizer algebras of permutation groups) and of strong isomorphisms (i.e. bijections of the point sets taking one algebra to the other) respectively. If m = 1 we come to arbitrary cellular algebras and their weak isomorphisms (i.e. matrix algebra isomorphisms preserving the Hadamard multiplication). On the other hand, the algebras which are m-closed for all m ≥ 1 are exactly Schurian ones whereas the weak isomorphisms which are m-isomorphisms for all m ≥ 1 are exactly ones induced by strong isomorphisms. We show that for any m there exist m-closed algebras on O(m) points which are not Schurian and m-isomorphisms of cellular algebras on O(m) points which are not induced by strong isomorphisms. This enables us to find for any m an edge colored graph with O(m) vertices satisfying the m-vertex condition and having non-Schurian adjacency algebra. On the other hand, we rediscover and explain from the algebraic point of view the Cai-Fürer-Immerman phenomenon that the m-dimensional Weisfeiler-Lehman method fails to recognize the isomorphism of graphs in an efficient way.

∗Research supported by RFFI, grants 96-15-96060 and 96-01-00676.

1 Introduction

The association scheme theory was called in [2] a “group theory without groups”. Indeed, the axiomatics of association schemes reflects combinatorial properties of permutation groups. The close connection between these objects is stressed by the fact that each permutation group produces a scheme the basis relations of which are exactly the 2-orbits of the group. However, this correspondence is not reversible and there are schemes which can not be obtained in such a way (for example, the scheme of the Shrikhande graph). A similar situation arises if one is interested in isomorphisms of schemes. Namely, each of them induces a combinatorial isomorphism which can be defined as an ordinary isomorphism of the adjacency algebras of the schemes preserving the basis matrices. But also in this case there are combinatorially isomorphic schemes which are not isomorphic (for example, the Hamming schemes and the schemes of the Doob graphs). The main purpose of this paper is to prove the nondegeneracy of the natural filtration of the class of all schemes (resp. of all combinatorial isomorphisms) whose limit is the class of all permutation group schemes (resp. genuine isomorphisms of schemes).

Having in mind the algebraic nature of the above questions we prefer to deal with the adjacency algebra of a coherent configuration being a generalization of an association scheme. These algebras were introduced by B. Yu. Weisfeiler and A. A. Lehman as cellular algebras and independently by D. G. Higman as coherent algebras (see [16] and [10]). They are by definition matrix algebras over ℂ closed under the Hadamard multiplication and the Hermitian conjugation and containing the identity matrix and the all-one matrix. Let W be a cellular algebra on a finite set V, i.e. a cellular subalgebra of the full matrix algebra Mat_{V} on V. The automorphism group Aut(W) of W consists by definition of all permutations of V preserving any matrix of W. In this language a group scheme corresponds to a Schurian cellular algebra (see [7] for the explanation of the term), i.e. one coinciding with the centralizer algebra of its automorphism group. A combinatorial isomorphism of coherent configurations is transformed to a weak isomorphism of cellular algebras which is by definition a matrix algebra isomorphism preserving the Hadamard multiplication.

Our technique is based on the following notion of the extended algebra introduced in [4] (for the exact definition see Section 3). For each positive integer m we define the m-dimensional extended algebra Ŵ^{(m)} of a cellular algebra W on V as the smallest cellular algebra on 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}. (This definition differs from that of [4] but Theorem 3.2 of this paper establishes the equivalence between them.) Using the natural bijection between the diagonal of V^{m} 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)} = … = Sch(W)

where Sch(W) is the centralizer algebra of Aut(W) in Mat_{V} and n is the number of elements of V. Thus the m-closure of W can be viewed as an mth approximation of its Schurian closure Sch(W). We say that W is m-closed if \overline{W}^{(m)} = W. Each algebra is certainly 1-closed and it is m-closed for all m iff it is Schurian. Thus

⋂_{m=1}^{∞} W_{m} = W_{∞}, W_{m} ⊃ W_{m+1}

where W_{m} (resp. W_{∞}) is the class of all m-closed (resp. Schurian) cellular algebras. Surely, the larger m is, the more an m-closed algebra is similar to the centralizer algebra of a permutation group. For example, some nontrivial facts from permutation group theory can be generalized even to 2-closed cellular algebras (see [5]). The following theorem shows in particular that the filtration {W_{m}}_{m=1}^{∞} does not collapse from any m.

Theorem 1.1 There exists ε > 0 such that for any sufficiently large positive integer n one can find a non-Schurian cellular algebra on n points which is m-closed for some m ≥ ⌊εn⌋.

One of the application of the theorem is related to constructing graphs satisfying the m-vertex condition in sense of [9] (see also Subsection 3.2). Namely, we show (Theorem 3.3) that the edge colored graph (coherent configuration) underlying an m-closed cellular algebra satisfies the m-vertex condition. So Theorem 1.1 implies the following statement.

Corollary 1.2 For any positive integer m there exists an edge colored graph with O(m) vertices satisfying the m-vertex condition and having non-Schurian adjacency algebra.

Concerning the combinatorial isomorphism problem we refine the concept of a weak isomorphism. Namely, we say 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 (see Section 4 for the exact definition). Obviously, each weak isomorphism is a 1-isomorphism in this sense. On the other hand, Theorem 4.5 shows that it is an m-isomorphism for all m iff it is induced by a strong isomorphism (which is by definition a bijection between the point sets preserving the algebras). The following theorem is similar to Theorem 1.1.

Theorem 1.3 There exists ε > 0 such that for any sufficiently large positive integer n one can find a cellular algebra on n points (even a Schurian one) admitting an m-isomorphism with m ≥ ⌊εn⌋ which is not induced by a strong isomorphism.

It follows from the proof of Theorem 1.3 that the required algebra can be chosen having simple spectrum. So there exist weak isomorphisms of cellular algebras with simple spectrum which are not induced by strong isomorphisms. This shows that Theorem 5.6 from [8] is not true.

Let us briefly outline the proofs of the theorems. To prove Theorem 1.3 we construct a family of cellular algebras with simple spectrum each of which corresponds to some cubic (3-regular) graph. Any such algebra admits a weak isomorphism φ which is not induced by a strong isomorphism (Theorem 5.5). Moreover, if the graph is a Ramanujan one, this weak isomorphism becomes induced by a strong one when restricted to sufficiently large point sets. In this case we are able to prove that φ is in fact an m-isomorphism for a sufficiently large m and the corresponding algebra W is a Schurian one. Theorem 1.1 is deduced from Theorem 1.3 by considering the wreath product of the cellular algebra W by the symmetric group on 2 points with respect to the weak isomorphism φ. This wreath product is not Schurian, since φ is not induced by a strong isomorphism. On the other hand, it is m-closed for a sufficiently large m due to the facts that so is W (being a Schurian one) and φ is an m-isomorphism. The last implication is the result of the detailed analysis of the extended algebras of general direct sums and wreath products (Theorems 7.5 and 7.7).

In the context of the discussed topics we can ask ourselves: is the filtration {W_{m}}_{m=1}^{∞} defined above natural in a sense. For instance, one can compare it to some other filtrations. A number of them arises from combinatorial algorithms related to the Graph Isomorphism Problem which is polynomial-time equivalent to the problem of constructing the Schurian closure of a cellular algebra. The analysis of such algorithms lead us in [4] to the following concept of a Schurian polynomial approximation scheme reflecting the idea of measuring non-Schurity.

Let us have a rule according to which given a cellular algebra W ≤ Mat_{V} and a positive integer m a cellular algebra S_{m}(W) ≤ Mat_{V} can be constructed. We say that the operators W ↦ S_{m}(W) (m = 1, 2, …) define a Schurian polynomial approximation scheme S if the following conditions are satisfied:

(1) W = S_{1}(W) ≤ … ≤ S_{n}(W) = … = Sch(W);

(2) S_{l}(S_{m}(W)) = S_{m}(W) for all l = 1, …, m;

(3) S_{m}(W) can be constructed in time n^{O(m)}

where n is the number of elements of V.

Each scheme of such a kind defines a filtration of the class of all cellular algebras. Moreover, there is a natural way to compare the filtrations by comparing the underlying schemes. Namely, let S and T be two Schurian polynomial approximation schemes. We say that S is dominated by T if there exists a positive integer c = c(S, T) such that S_{m}(W) ≤ T_{cm}(W) for all cellular algebras W and all m. Schemes S and T are called equivalent if each of them is dominated by the other.

We proved in [4] that the operators W ↦ \overline{W}^{(m)} mapping a cellular algebra W to its m-closure define a Schurian polynomial approximation scheme. Another example is given by the well-known m-dimensional Weisfeiler-Lehman method (m-dim W-L, see [3]). Despite the fact that in its original form this method can be applied only to graphs, a natural interpretation of it produces the algorithm which given a cellular algebra W constructs a certain cellular algebra WL_{m}(W) (m = 1, 2, ...) satisfying conditions (1)-(3) above (the exact definitions can be found in Section 6). The third main result of the paper shows that these schemes are equivalent.

Theorem 1.4 Let W be a cellular algebra on V. Then

WL_{m}(W) ≤ \overline{W}^{(m)} ≤ WL_{3m}(W), m = 1, 2, ….

In particular, the Schurian polynomial approximation schemes corresponding to the m-closure and the m-dimensional Weisfeiler-Lehman methods are equivalent.

The proof of the theorem is based on the notion of a stable partition of V^{m}, the axiomatics of which gathers some combinatorial regularity conditions generalizing those satisfied by the m-orbits of a permutation group. It should be noted that similar objects were considered in [11] and [13]. The key point of the analysis consists of the fact that the partition of V^{m} found by the m-dim W-L method is a stable partition of V^{m} in our sense (Theorem 6.1). Besides, it turns out that a stable partition of V^{3m} produces a coherent configuration on V^{m} (Lemma 6.3). Combining these observations and the inclusion WL_{m}(W) ≤ \overline{W}^{(m)} proved in [4] we obtain the required statement.

We complete the introduction by making some remarks concerning the m-dim W-L method. This method was discovered to test the isomorphism of two graphs by comparing the canonical colorings of V^{m} constructed from them. However it was proved in [3] that there exist infinitly many pairs of non-isomorphic vertex colored graphs with O(m) vertices for which the m-dim W-L method does not recognize their non-isomorphism. Nevertheless, the technique used for the proof of this result leaves the algebraic nature of this phenomenon unclear. In contrast to [3] the results of the present paper completely clarify the situation. Namely, let Γ_{1} and Γ_{2} be two graphs which can not be identified by the m-dim W-L method (see [3]). Then the cellular algebras W_{1} and W_{2} generated by the adjacency matrices of them are weakly isomorphic and this weak isomorphism is not induced by a strong one. Moreover, it follows from Theorem 6.4 that the last isomorphism can be extended to a weak isomorphism of the ⌊m/3⌋-extended algebras corresponding to W_{1} and W_{2}. So it is in fact an ⌊m/3⌋-isomorphism. Thus the algebraic reason for the high-dimensional W-L method to fail in recognizing the isomorphism of graphs is that there are highly closed isomorphisms of cellular algebras which are not induced by strong isomorphisms (Theorem 1.3).

In fact the construction underlying Theorem 1.3 produces for any positive integer m examples of non-isomorphic edge colored graphs (even vertex colored ones) with O(m) vertices which are indistinguishable by the m-dim W-L method due to Theorem 6.4. We notice that these graphs slightly differ from those found by Cai-Fürer-Immerman in [3].

The paper consists of six sections and Appendix. Section 2 contains the main definitions and notation concerning cellular algebras. In Section 3 we define extended algebras and closures. Also we describe the connection of these notions with the mvertex condition. Section 4 is devoted to refining the notion of a weak isomorphism. In Sections 5 and 6 we prove Theorems 1.1 and 1.3, and Theorem 1.4 respectively. Appendix contains the explicit description of the extended algebras of the direct sum and the wreath product by a permutation group. These results are used in proving Theorems 1.1 and 1.3.

Notation. As usual by ℂ we denote the complex field.

Throughout the paper V denotes a finite set with n = |V | elements.

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} . For U ⊂ V the algebra Mat_{U} is considered in a natural way as a subalgebra of Mat_{V} .

For U, U′ ⊂ V let J_{U,U′} denote the {0,1}-matrix with 1’s exactly on the places belonging to U × U′.

The transpose of a matrix A is denoted by A^{T}, its Hermitian conjugate by A^{∗}. Each bijection g : V → V′ defines a natural algebra isomorphism from Mat_{V} onto

Mat_{V′} . The image of a matrix A under g will be denoted by A^{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), Mat_{m}, V^{m} and V instead of [1, m], Sym([m]), Mat_{[m]}, V^{[m]} and V^{1} respectively.

2 Cellular algebras

All undefined terms below concerning cellular algebras and permutation groups can be found in [17] and [18] respectively.

2.1. By a cellular algebra on V we mean a subalgebra W of Mat_{V} for which the following conditions are satisfied:

(C1) I_{V} , J_{V} ∈ W;

(C2) ∀A ∈ W : A^{∗} ∈ W;

(C3) ∀A, B ∈ W : A ∘ B ∈ W,

where A ∘ B is the Hadamard (componentwise) product of the matrices A and B. It follows from (C2) that W is a semisimple algebra over ℂ.

Each cellular algebra W on V has a uniquely determined linear base R = R(W) consisting of {0,1}-matrices such that

∑_{R∈R} R = J_{V} and R ∈ R ⇔ R^{T} ∈ R.  (1)

The linear base R is called the standard basis of W and its elements the basis matrices. The nonnegative integers c_{R,S}^{T} defined by RS = ∑_{T ∈R} c_{R,S}^{T} · T where R, S ∈ R, are called the structure constants of W.

Set Cel(W) = {U ⊂ V : I_{U} ∈ R} and Cel^{∗}(W) = {⋃_{U∈S} U : S ⊂ 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, U′ ∈ Cel^{∗}(W) set R_{U,U′} = {R ∈ R : R ∘ J_{U,U′} = R}. Then

R = ⋃_{U,U′∈Cel(W)} R_{U,U′} (disjoint union).

Moreover, given cells U, U′ the number of 1’s in the uth row (resp. vth column) of the matrix R ∈ R_{U,U′} does not depend on the choice of u ∈ U (resp. v ∈ U′).

For each U ∈ Cel^{∗}(W) we view the subalgebra I_{U}W I_{U} of W as a cellular algebra on U and denote it by W_{U}. The basis matrices of W_{U} are in 1-1 correspondence to the matrices of R_{U,U}. If U ∈ Cel(W) we call W_{U} the homogeneous component of W corresponding to U.

Each matrix R ∈ R being a {0,1}-matrix is the adjacency matrix of some binary relation on V called a basis relation of W. By (1) the set of all of them form a partition of V × V which can be interpreted as a coherent configuration on V (see [10]). We use all the notations introduced for basis matrices also for basis relations.

2.2. A large class of cellular algebras comes from permutation groups as follows (see [17]). Let G ≤ Sym(V) be a permutation group and

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

be its centralizer algebra. Then Z(G) is a cellular algebra on V such that Cel(Z(G)) = Orb(G) and R(Z(G)) = Orb_{2}(G) where Orb(G) is the set of orbits of G and Orb_{2}(G) is the set of its 2-orbits.

We say that cellular algebras W on V and W′ on V′ are strongly isomorphic, if W^{g} = W′ for some bijection g : V → V′ called a strong isomorphism from W to W′. Clearly, g induces a bijection between the sets R(W) and R(W′). We use notation Iso(W, W′) for the set of all isomorphisms from W to W′.

The group Iso(W, W) contains a normal subgroup

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

called the automorphism group of W. If W = Z(Aut(W)), then W is called Schurian. It is easy to see that W is Schurian iff the set of its basis relations coincides with the set of 2-orbits of Aut(W). It follows from [18] that there exist cellular algebras which are not Schurian (see also [7]).

2.3. The set of all cellular algebras on V is ordered by inclusion. The largest and the smallest elements of this set are respectively the full matrix algebra Mat_{V} and the simplex on V, i.e. the algebra with the linear base {I_{V} , J_{V} }. For cellular algebras W and W′ we write W ≤ W′ if W is a subalgebra of W′.

Given subsets X_{1}, …, X_{s} of Mat_{V}, their cellular closure, i.e. the smallest cellular algebra containing all of them, is denoted by [X_{1}, …, X_{s}]. If X_{i} = {A_{i}} we omit the braces.

3 Extended algebras and closures

3.1. The notion of an m-closed cellular algebra was introduced in [4] in connection with the Schurity problem. It goes back to [17] where a similar notion was defined in an algorithmic way. We start with the main definitions concerning highly closed cellular algebras.

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

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

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-dimensional extended algebra of W. The group Aut(Ŵ) acts faithfully on the set

Δ = Δ^{(m)}(V) = {(v, …, v) ∈ V^{m} : v ∈ V }.

Moreover, the mapping δ : v ↦ (v, …, v) induces a permutation group isomorphism between Aut(W) and the constituent of Aut(Ŵ) on Δ. Set

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

We call \overline{W} the m-closure of W and say that W is m-closed if W = \overline{W}. Each cellular algebra is certainly 1-closed. The following proposition describes the relationship between the m-closures for m ≥ 1 and the Schurian closure Sch(W) = Z(Aut(W)) of a cellular algebra W and shows that in a sense \overline{W} can be regarded as an mth approximation of Sch(W).

Proposition 3.1 ([4], Proposition 3.3) For each cellular algebra W on n points the following statements hold:

(1) Aut(\overline{W}^{(m)}) = Aut(W) for all m ≥ 1;

(2) W = \overline{W}^{(1)} ≤ … ≤ \overline{W}^{(n)} = … = Sch(W);

(3) \overline{(\overline{W}^{(m)})}^{(l)} = \overline{W}^{(m)} for all l ∈ [m].

The following statement gives in fact an equivalent definition of the m-extended algebra and hence of the m-closure.

Theorem 3.2 Let W ≤ Mat_{V} be a cellular algebra. Then Ŵ = [W^{m}, I_{Δ}].

Proof. We will prove the following equality:

Z_{m}(V) = [Z_{1}(V)^{m}, I_{Δ}].  (2)

Then since obviously W^{m} ≥ Z_{1}(V)^{m}, we will have

Ŵ = [W^{m}, Z_{m}(V)] = [W^{m}, Z_{1}(V)^{m}, I_{Δ}] = [W^{m}, I_{Δ}].

To prove (2) it suffices to check that any 2-orbit R of the coordinatewise action of Sym(V) on V^{m} is a union of the basis relations of the algebra [Z_{1}(V)^{m}, I_{Δ}]. It is easy to see that the set of all of these 2-orbits is in 1-1 correspondence with the set of all equivalence relations E on [2m] having at most n classes so that

R = R(E) = {(ū, v̄) ∈ V^{m} × V^{m} : (ū · v̄)_{i} = (ū · v̄)_{j} ⇔ (i, j) ∈ E}  (3)

where ū · v̄ ∈ V^{2m} is the composition of ū and v̄. Any R(E) can be expressed with the help of set-theoretic operations by the sets

R(S) = {(ū, v̄) : i, j ∈ S ⇒ (ū · v̄)_{i} = (ū · v̄)_{j}}  (4)

with nonempty S ⊂ [2m]. Set A(S) = ( ⨂_{i=1}^{m} A_{i}^{(0)})I_{Δ}( ⨂_{i=1}^{m} A_{i}^{(1)}) where A_{i}^{(l)} coincides with I_{V} or J_{V} depending on whether lm + i belongs or does not belong to S ∩ [1 + lm, m + lm], l = 0, 1. Then a straightforward check shows that A(S) equals the adjacency matrix of the relation R(S). So the latter matrix belongs to the right side of (2).

3.2. In this subsection we prove a theorem which is needed for Corollary 1.2. Under a colored graph Γ on V we mean a pair (V, c) where c = c_{Γ} is a mapping

from V × V to the set of positive integers. The number c(u, v) is called the color of a pair (u, v). The following definition goes back to [9]. A colored graph Γ is called satisfying the m-vertex condition if for each colored graph K on m vertices with designated pair of vertices (x, y), the number of embeddings of K as induced subgraph of Γ such that (x, y) is mapped to (u, v), depends only on the color of the pair (u, v). A detailed information about this notion can be found in [7, p.70].

We say that a colored graph Γ is associated with a cellular algebra W if the color classes of Γ coincide with the basis relations of W. In fact, the graph Γ is nothing else than the coherent configuration (with labeling) underlying W.

Theorem 3.3 A colored graph associated with an m-closed cellular algebra satisfies the m-vertex condition.

Proof. First we prove the following statement.

Lemma 3.4 Let W be a cellular algebra on V and X be a cell of its m-extended algebra. Then the set R_{i,j}(X) = \{(v_{i}, v_{j}) : \overline{v} ∈ X\} is a basis relation of the algebra \overline{W} for all i, j ∈ [m].

Proof. It follows from statement (2) of Proposition 3.6 of [4] that R_{i,j}(X) ⊂ R for some R ∈ R(\overline{W}). On the other hand, by statement (1) of the same proposition the set X_{R} = {(u, …, u, v) ∈ V^{m} : (u, v) ∈ R} is a cell of Ŵ. So the number of 1’s in any row of the adjacency matrix of the relation \{(\overline{u}, \overline{v}) ∈ X_{R} × X : u_{1} = v_{i}, u_{m} = v_{j}\} is the same (this relation is obviously a union of basis ones). By the choice of R the last number is not zero. Thus R_{i,j}(X) = R.

Let now Γ be a graph associated with an m-closed algebra W ≤ Mat_{V} and K be an arbitrary colored graph on [m] with designated pair of vertices (x, y). Let u, v ∈ V and \overline{u} = u^{δ}, \overline{v} = v^{δ}. It is easy to see that the number of embeddings of K as induced subgraph of Γ such that (x, y) is mapped to (u, v) equals the cardinality of the set

\{\overline{w} ∈ V^{m} : w_{x} = u, w_{y} = v, c_{Γ}(w_{i}, w_{j}) = c_{K}(i, j), i, j ∈ [m]\}.  (5)

Since \overline{W} = W, by Lemma 3.4 the set X = \{\overline{w} : c_{Γ}(w_{i}, w_{j}) = c_{K}(i, j), i, j ∈ [m]\} is a cellular set of Ŵ and depends only on c_{Γ}(u, v), i.e. on the basis relation R of W such that (u, v) ∈ R. So the set (5) coincides with

\{\overline{w} ∈ V^{m} : (\overline{u}, \overline{w}) ∈ R_{1}, (\overline{w}, \overline{v}) ∈ R_{2}, \overline{w} ∈ X\}  (6)

where R_{1} (resp. R_{2}) is the binary relation on V^{m} defined by the equality of the first and xth (resp. yth and first) coordinates. However the cardinality of the set (6) equals the sum of the structure constants c_{S,T}^{R_{0}} of Ŵ where R_{0} = R^{δ}, and S and T run over the sets of basis relations of Ŵ contained in (Δ × X) ∩ R_{1} and (X × Δ) ∩ R_{2} respectively. Since the last number depends only on R, we are done.

Remark 3.5 In fact, it can be proved that the graph of Theorem 3.4 satisfies the 3m-vertex condition. However, the proof of this statement is out of the scope of this paper.

4 Weak isomorphisms and their extensions

4.1. Along with the notion of a strong isomorphism we consider for cellular algebras that of a weak one. Namely, cellular algebras W on V and W′ on V′ are called weakly isomorphic if there exists an algebra isomorphism φ : W → W′ such that

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

Any such φ is called a weak isomorphism from W to W′. The set of all of them is denoted by Isow(W, W′). If W = W′ we write Isow(W) instead of Isow(W, W). Clearly, Isow(W) forms a group which is isomorphic to a subgroup of Sym(R(W)). We note that each strong isomorphism from W to W′ induces in a natural way a weak isomorphism between these algebras.

The following statement establishes the simplest properties of weak isomorphisms.

Lemma 4.1 Let W ≤ Mat_{V}, W′ ≤ Mat_{V′} be cellular algebras and φ ∈ Isow(W, W′) be a weak isomorphism. Then

(1) φ(R) = R′ where R = R(W) and R′ = R(W′). Besides, φ(R^{T}) = φ(R)^{T} for all R ∈ R.

(2) φ induces a natural bijection U ↦ U^{φ} from Cel^{∗}(W) onto Cel^{∗}(W′) preserving cells such that φ(I_{U}) = I_{U^{φ}}. Moreover, |U| = |U^{φ}| and, in particular, |V | = |V′|.

(3) φ(R_{U_{1},U_{2}}) = R′_{U_{1}^{φ},U_{2}^{φ}} for all U_{1}, U_{2} ∈ Cel^{∗}(W).

Proof. The first part of statement (1) is trivial. The second follows from the observation that given R ∈ R, the matrix R^{T} is the only matrix of R whose product by R is not orthogonal to I_{V} with respect to the Hadamard multiplication. Let U ∈ Cel^{∗}(W). Then the equalities I_{U}I_{U} = I_{U} ∘ I_{U} = I_{U} imply that φ(I_{U})φ(I_{U}) = φ(I_{U})∘φ(I_{U}) = φ(I_{U}). So there exists U′ ⊂ V′ such that φ(I_{U}) = I_{U′}. Since I_{U′} ∈ W′, we have U′ ∈ Cel^{∗}(W′). Set U^{φ} = U′. Since I_{V} = ∑_{U∈Cel(W)} I_{U} and φ(I_{V}) = I_{V′}, the mapping U ↦ U^{φ} gives a bijection from Cel(W) to Cel(W′), which proves the first part of statement (2). Note that φ(J_{V}) = J_{V′}. So φ(J_{U}) = φ(I_{U}J_{V} I_{U}) = I_{U^{φ}}J_{V′}I_{U^{φ}} = J_{U^{φ}} for all U ∈ Cel^{∗}(W). Now the rest of statement (2) follows from the equality J_{U}^{2} = |U|J_{U}. Statement (3) is the consequence of the equality R_{U_{1},U_{2}} = {I_{U_{1}}RI_{U_{2}} : R ∈ R, I_{U_{1}}RI_{U_{2}} ≠ 0} and statements (1) and (2).

Lemma 4.1 implies that if U is a cellular set of W, then any weak isomorphism φ : W → W′ induces a weak isomorphism from W_{U} to W′_{U^{φ}}. It will be denoted by φ_{U} and called the restriction of φ to U.

4.2. Let φ : W → W′ be a weak isomorphism from a cellular algebra W ≤ Mat_{V} to a cellular algebra W′ ≤ Mat_{V′}.

Definition 4.2 We say that a weak isomorphism ψ : Ŵ → Ŵ′ is an m-extension of φ if the following conditions are satisfied:

(i) ψ(I_{Δ}) = I_{Δ′},

(ii) ψ(A) = φ^{m}(A) for all A ∈ W^{m},

where Δ and Δ′ are the diagonals of V^{m} and (V′)^{m} respectively and φ^{m} is the weak isomorphism from W^{m} to (W′)^{m} induced by φ.

The proof of Theorem 3.2 implies that ψ takes a basis matrix of Z_{m}(V) to the corresponding basis matrix of Z_{m}(V′) (i.e. with the same defining equivalence relation E on [2m], see (3)). It follows from (ii) that any 1-extension of φ coincides with φ.

Lemma 4.3 Let ψ be an m-extension of a weak isomorphism φ : W → W′. Then

(1) ψ is uniquely determined by φ.

(2) φ has an l-extension for all l ∈ [m].

Proof. The first statement immediately follows from Theorem 3.2 whereas the second one is the consequence of statement (2) of Lemma 7.3.

The weak isomorphism ψ : Ŵ → Ŵ′ (uniquely determined by φ according to Lemma 4.3) will be denoted below by φ̂.

4.3. Now we are ready to introduce the central notion of the paper.

Definition 4.4 A weak isomorphism φ is called an m-isomorphism if there exists an m-extension of φ.

Obviously, the inverse of an m-isomorphism as well as the composition of m-isomorphisms is also an m-isomorphism. The set of all m-isomorphisms from W to W′ will be denoted by Isow_{m}(W, W′). It follows from statement (2) of Lemma 4.3 that

Isow_{l}(W, W′) ⊃ Isow_{m}(W, W′), l ∈ [m].  (7)

Obviously, Isow_{1}(W, W′) = Isow(W, W′).

We note that given g ∈ Iso(W, W′) its m-fold Cartesian product g^{m} belongs to Iso(W^{m}, (W′)^{m}) and takes I_{Δ} to I_{Δ′}. So g^{m} belongs to Iso(Ŵ, Ŵ′) and the weak isomorphism from Ŵ to Ŵ′ induced by it is the m-extension of the weak isomorphism induced by g. Thus any weak isomorphism induced by a strong isomorphism (the set of all of them will be denoted by Isow_{∞}(W, W′)) is an m-isomorphism for all m. The following statement shows that the converse statement is also true.

Theorem 4.5 Isow_{m}(W, W′) = Isow_{∞}(W, W′) for all m ≥ n.

Proof. Let φ ∈ Isow_{m}(W, W′) where m ≥ n. Choose \overline{v} = (v_{1}, …, v_{m}) ∈ V^{m} such that V = \{v_{1}, …, v_{n}\} and denote by U the cell of Ŵ containing \overline{v}. Since U is contained in an orbit of Sym(V) acting on V^{m}, the last equality holds also for all points of U and |R(Ŵ_{U})| = |U|, i.e. Ŵ_{U} is the centralizer algebra of a regular permutation group. Hence by Lemma 4.1 so is the algebra Ŵ′_{U′} where U′ = U φ̂. It is easy to see that any weak isomorphism of such algebras is induced by a strong isomorphism. So there exists a bijection h : U → U′ inducing φ̂_{U}:

φ̂(A) = A^{h}, A ∈ Ŵ_{U}.  (8)

Since φ̂ takes a basis matrix of Z_{m}(V) to the corresponding basis matrix of Z_{m}(V′) (i.e. with the same defining equivalence relation E on [2m], see (3)), there exists a uniquely determined bijection g : V → V′ such that

\overline{v}^{h} = (v_{1}^{g}, …, v_{m}^{g}).  (9)

To complete the proof it suffices to check that (φ(R))_{v_{i}^{g},v_{j}^{g}} = R_{v_{i},v_{j}} for all R ∈ R(W) and i, j ∈ [n]. Denote by A_{i} (resp. A′_{i}) the adjacency matrix in Mat_{V^{m}} (resp. Mat_{(V′)^{m}}) of the relation (4) with S = {i} ∪ [m + 1, 2m]. Then

(φ(R))_{v_{i}^{g},v_{j}^{g}} = (A′_{i}φ(R)^{δ′}A′_{j}^{T})_{\overline{v}^{h},\overline{v}^{h}} = (φ̂(A_{i})φ̂(R^{δ})φ̂(A_{j})^{T})_{\overline{v}^{h},\overline{v}^{h}} = (A_{i}R^{δ}A_{j}^{T})_{\overline{v},\overline{v}} = R_{v_{i},v_{j}}

where δ and δ′ are the diagonal inclusions of V into V^{m} and V′ into (V′)^{m}. (We made use of (9), (8) and the fact that φ̂ is the m-extension of φ.)

4.4. It seems difficult to verify that a given weak isomorphism is actually an misomorphism. However, we can give a sufficient condition for this. To formulate it let us denote by Cel_{k}^{∗}(W) the set of all cellular sets of W containing at most k cells. We will also make use of the obvious inclusion Ŵ_{U} ≤ Ŵ_{U^{m}} where U ∈ Cel^{∗}(W) and Ŵ_{U} is the m-extended algebra of W_{U}.

Theorem 4.6 Let W ≤ Mat_{V} , W′ ≤ Mat_{V′} be cellular algebras and φ ∈ Isow(W, W′) be a weak isomorphism. Suppose also that for positive integers k, m the following conditions are satisfied:

(i) For any U ∈ Cel_{k}^{∗}(W) there exist an m-extension of φ_{U} and a weak isomorphism ψ_{U} ∈ Isow(Ŵ_{U^{m}}, Ŵ′_{(U^{φ})^{m}}) extending it.

(ii) For any U_{1}, U_{2} ∈ Cel_{k}^{∗}(W) the restrictions of ψ_{U_{1}} and ψ_{U_{2}} to (U_{1}∩U_{2})^{m} coincide.

Then φ ∈ Isow_{m}(W, W′) whenever k ≥ 3m.

Proof. Supposing k ≥ 3m let us define a mapping ψ : R → R′ where R = R(Ŵ) and R′ = R(Ŵ′) as follows. Given R ∈ R set

ψ(R) = ψ_{U}(R).  (10)

where U ∈ Cel_{k}^{∗}(W) is chosen such that R ∈ R_{U^{m},U^{m}}. Since 2m ≤ k, at least one such U does exist. By (ii) the element ψ(R) does not depend on the choice of U. Obviously, ψ is a bijection (the inverse map is given by (ψ_{U})^{−1}). This defines a linear 1-1 mapping from Ŵ to Ŵ′ for which we use the same notation ψ.

Let R, S ∈ R with RS ≠ 0. Then R, S ∈ R_{U^{m},U^{m}} for some U ∈ Cel_{3m}^{∗}(W). Since 3m ≤ k, we obtain from (10) and (i) that

ψ(RS) = ψ_{U}(RS) = ψ_{U}(R)ψ_{U}(S) = ψ(R)ψ(S),

which implies that ψ ∈ Isow(Ŵ). It also follows from (10) and (i) that the restriction of ψ to U^{m} extends the m-extension of φ_{U} for all U ∈ Cel_{k}^{∗}(W). So ψ is the mextension of φ.

In Section 5 it will be convenient for us to make use of a weaker version of the theorem as follows.

Corollary 4.7 The conclusion of Theorem 4.6 still holds if conditions (i) and (ii) are replaced by the following conditions:

(i′) For any U ∈ Cel_{k}^{∗}(W) there exists a bijection h = h(U) ∈ Iso(W, W′) such that U^{h} = U^{φ} and the weak isomorphism from W_{U} to W′_{U^{φ}} induced by it coincides

with φ_{U}.

(ii′) For any U_{1}, U_{2} ∈ Cel_{k}^{∗}(W) there exists a permutation h = h(U_{1}, U_{2}) ∈ Aut(W)

such that

(h_{1})_{U} = h_{U} (h_{2})_{U}

where h_{1} and h_{2} are the bijections associated with U_{1} and U_{2}, U = U_{1} ∩ U_{2} and h_{U}, (h_{1})_{U} and (h_{2})_{U} are the bijections obtained from h, h_{1} and h_{2} by restriction to U.

Proof. Set ψ_{U} to be the restriction to U^{m} of the weak isomorphism from Ŵ to Ŵ′ induced by the m-fold Cartesian product of h. Then conditions (i) and (ii) follow from (i′) and (ii′) respectively.

5 Proofs of Theorems 1.1 and 1.3

Our constructions below involve the notions of the direct sum of cellular algebras and the wreath product of a cellular algebra by a permutation group. As to the definitions see Subsection 7.1

5.1. Let G be an elementary Abelian group of order 4 and V_{i} = G, i ∈ [s], and consider G as acting on V_{i} by multiplications. Let us denote by K the class of all cellular algebras W on the disjoint union V of V_{i}’s such that

W ≥ ⊞_{i=1}^{s} Z(G, V_{i}), Cel(W) = {V_{i} : i ∈ [s]}.

For W ∈ K the group Aut(W) is naturally identified with a subgroup of G^{s} the elements of which will be denoted by (g_{1}, …, g_{s}). Moreover, each element of G^{s} can be considered as a strong isomorphism of W to itself inducing the identity isomorphism of all of its homogeneous components. Below we set R = R(W) and R_{i,j} = R_{V_{i},V_{j}} where i, j ∈ [s].

The following statement is straightforward from the definitions (see also [8]).

Lemma 5.1 Let W ∈ K. Then

(1) W_{V_{i}} = Z(G, V_{i}) for all i.

(2) If i ≠ j, then W_{V_{i}∪V_{j}} = Z(G_{i,j}, V_{i} ∪ V_{j}) where G_{i,j} is a subgroup of G × G of index 1, 2 or 4. Moreover, Aut(W_{V_{i}∪V_{j}}) = G_{i,j} and |R_{i,j}| = [G × G : G_{i,j}].

(3) If |R_{i,j}| = 2, then G_{i,j} is of the form

K(c_{1}, c_{2}) = ⟨c_{1}⟩ × ⟨c_{2}⟩ ∪ \overline{⟨c_{1}⟩} × \overline{⟨c_{2}⟩}

where c_{1} = c_{1}(i, j), c_{2} = c_{2}(i, j) are uniquely determined elements of G \ {1}, ⟨c_{l}⟩ = \{1, c_{l}\} and \overline{⟨c_{l}⟩} = G \ ⟨c_{l}⟩, l = 1, 2. Moreover, c_{1}(i, j) = c_{2}(j, i) and R_{i,j} consists of the adjacency matrices of the relation G_{i,j} and its complement in V_{i} × V_{j}.

It follows from statement (1) and Proposition 2.1 of [6] that K consists of algebras with simple spectrum.

5.2. In this paper we are especially interested in the subclass K^{∗} of the class K consisting of all cellular algebras W such that

(i) |R_{i,j}| ≤ 2 for all i ≠ j.

(ii) Given i ∈ [s] the elements c_{1}(i, j) with |R_{i,j}| = 2 are pairwise distinct.

We associate to such an algebra a graph Γ = Γ(W) with vertex set V (Γ) = [s] and edge set E(Γ) = {(i, j) : |R_{i,j}| = 2}. Since |R_{i,j}| = |R_{j,i}|, this graph can be considered as an undirected one. We observe that

|R_{i,j}| = \{ \begin{matrix}4, & if i = j, \\ 2, & if (i, j) ∈ E(Γ), \\ 1, & otherwise \end{matrix}  (11)

It should be noted that each weak isomorphism of the algebras belonging K^{∗} induces an isomorphism of the corresponding graphs. Moreover, it is easy to see that each isomorphism of the graphs is induced by a strong isomorphism of the algebras.

Lemma 5.2 Let Γ be an undirected graph with V (Γ) = [s]. Then Γ = Γ(W) for some W ∈ K^{∗} iff the degree of any vertex of Γ is at most 3.

Proof. Let W ∈ K^{∗}. It follows from (ii) and the definition of c_{1}(i, j) that the degree of a vertex i in the graph Γ(W) is at most |G \ {1}| = 3, which proves the necessity. Conversely, let the degree of any vertex of Γ be at most 3. For each i ∈ [s] choose an injection

f_{i} : {j : (i, j) ∈ E(Γ)} → G \ {1}

and denote by W the linear subspace of Mat_{V} spanned by ⊞_{i=1}^{s} Z(G, V_{i}) and the adjacency matrices A(i, j) of the relations K(c_{1}, c_{2}) ⊂ V_{i} × V_{j} where c_{1} = c_{1}(i, j) = f_{i}(j), c_{2} = c_{2}(i, j) = f_{j}(i) for all (i, j) ∈ E(Γ). Let (i, j), (j, k) ∈ E(Γ) and i ≠ k. Then c_{2}(i, j) ≠ c_{1}(j, k) and so

A(i, j) · A(j, k) = J_{V_{i},V_{k}}.

This implies that the linear space W is closed with respect to the matrix multiplication and hence is a cellular algebra from K^{∗}.

Let us study the isomorphisms of a cellular algebra W ∈ K^{∗} to itself leaving any cell of W fixed. For an edge (i, j) of the graph Γ = Γ(W) set

g_{(i,j)} = (h_{1}, …, h_{s}),  h_{k} = \{ \begin{matrix}c_{1}(i, j), & if k = i, \\ c_{2}(i, j), & if k = j, \\ 1, & otherwise. \end{matrix}  (12)

Let P = (i_{0}, …, i_{t}) ∈ [s]^{t+1} be a path in the graph Γ from i_{0} to i_{t} (i.e. (i_{l−1}, i_{l}) ∈ E(Γ) for all l ∈ [t]). We define a permutation of V by

g_{P} = ∏_{l=1}^{t} g_{(i_{l−1},i_{l})}.  (13)

Clearly, g_{P} ∈ Iso(W, W) for all P (including ones with t = 0 for which g_{P} = 1) and also

g_{P ·P′} = g_{P} g_{P′}, g_{P^{−1}} = g_{P}^{−1}  (14)

where P · P′ is the composition of the paths P and P′ (providing that the last vertex of P coincides with the first vertex of P′) and P^{−1} is the reverse of P. Denote by φ_{P} the weak isomorphism of the algebra W to itself induced by the strong isomorphism g_{P}. Obviously, φ_{P} is identical on each homogeneous component of W and φ_{P}^{2} = id_{W}.

Lemma 5.3 Let W ∈ K^{∗} and Γ = Γ(W). Then the following statements hold:

(1) Let φ = φ_{(i,j)} where (i, j) ∈ E(Γ). Then the action of φ on the set R_{a,b} is nontrivial iff (a, b) ∈ E(Γ) and |{a, b} ∩ {i, j}| = 1.

(2) If P = (i_{0}, …, i_{t}) is a closed path in the graph Γ (i.e. i_{0} = i_{t}), then g_{P} ∈ Aut(W).

(3) If Γ is a 3-connected graph, then W is a Schurian algebra.

Proof. If φ is not identical on R_{a,b}, then obviously (a, b) ∈ E(Γ) and {a, b} ∩ {i, j} ≠ ∅ (see (11) and (12)). Further, if {a, b} = {i, j}, then g_{(i,j)} is of the form (c_{1}(a, b), c_{2}(a, b)) on V_{a}∪V_{b} and consequently belongs to Aut(W_{V_{a}∪V_{b}}) (see Lemma 5.1) acting trivially on R_{a,b}. Conversely, let (a, b) ∈ E(Γ) and for instance a = i, b ≠ j. Then g_{(i,j)} is of the form (c_{1}(a, j), 1) on V_{a} ∪ V_{b} with c_{1}(a, j) ≠ c_{1}(a, b) and so can not belong to Aut(W_{V_{a}∪V_{b}}). This proves statement (1). Now, if P is a closed path in Γ, then by statement (1) and formula (14) the weak isomorphism φ_{P} acts trivially on the set R. This means that g_{P} ∈ Aut(W), which proves statement (2).

To prove statement (3) we will make use of the following property of a 3-connected graph: given an edge and a vertex nonincident to each other, there exists a cycle (a closed path without repeating vertices) passing through the edge but not through the vertex. (Indeed, the subgraph obtained by removing the vertex is 2-connected and so there is a cycle in it passing through the edge, see Corollaries 2 and 4 on pp. 168 and 169 of [1]). Given distinct i, j ∈ [s] we define a set S_{i,j} of cycles of the graph Γ as follows. If (i, j) ∈ E(Γ), then S_{i,j} consists of 3 elements: a cycle passing through i but not through j, a cycle passing through j but not through i and a cycle passing through the edge (i, j). If (i, j) ∉ E(Γ), then S_{i,j} consists of 4 elements: 2 cycles passing through i but not through j covering all edges incident to i and 2 cycles passing through j but not through i covering all edges incident to j.

It follows from (12) and (13) that the order of the group generated by all permutations g_{P}, P ∈ S_{i,j}, and even of its constituent H_{i,j} on V_{i} ∪ V_{j} equals 2^{|S_{i,j}|}. So

|H_{i,j}| = \{ \begin{matrix}8, & if (i, j) ∈ E(Γ), \\ 16, & otherwise. \end{matrix}

On the other hand, by statement (2) of the lemma the group H_{i,j} is a subgroup of Aut(W_{V_{i}∪V_{j}}) whereas | Aut(W_{V_{i}∪V_{j}}| = 16/|R_{i,j}| by statement (2) of Lemma 5.1. Thus H_{i,j} = Aut(W_{V_{i}∪V_{j}}) by (11). Since the algebra W_{V_{i}∪V_{j}} is obviously Schurian and each element of H_{i,j} is the restriction of an automorphism of W, statement (3) follows.

Remark 5.4 In fact, if Γ is a connected cubic graph, then the 3-connectivity of Γ is also necessary for W to be Schurian. This can be proved by using the fact that in this case the group Aut(W) is generated by the permutations g_{P} where P runs over all cycles of Γ.

5.3. Let W ∈ K^{∗} and a ∈ [s]. Set

ψ_{a} = ∏_{b∈Γ(a)} ψ_{a,b}

where Γ = Γ(W), Γ(a) is the neighbourhood of a in Γ and ψ_{a,b} is the weak isomorphism of the algebra W defined for R ∈ R by

ψ_{a,b}(R) = \{ \begin{matrix}J_{V_{a},V_{b}} − R, & if R ∈ R_{a,b}, \\ J_{V_{b},V_{a}} − R, & if R ∈ R_{b,a}, \\ R, & otherwise. \end{matrix}

Then ψ_{a} is an involutory weak isomorphism of W moving R iff R ∈ R_{a,b} ∪ R_{b,a} with b ∈ Γ(a). These weak isomorphisms are closely related to those of the previous subsection. Namely, by statement (1) of Lemma 5.3 we have φ_{(i,j)} = ψ_{i}ψ_{j} for all (i, j) ∈ E(Γ). So

φ_{P} = ψ_{a}ψ_{b}  (15)

where P is any path in the graph Γ from a to b.

Theorem 5.5 Let W ∈ K^{∗}, Γ = Γ(W) be a cubic graph and a ∈ [s]. Then

(1) The weak isomorphism ψ_{a} is not induced by a permutation of V.

(2) If Γ is a connected graph with no separator of some cardinality k ≥ 3m, then ψ_{a} ∈ Isow_{m}(W). (A set X is called a separator of Γ if any connected component of the induced subgraph Γ \ X on [s] \ X has at most s/2 vertices.)

Proof. Given φ ∈ Isow(W) leaving any cell of W fixed let us denote by T (φ) (resp. t(φ)) the set of all 2-subsets {i, j} of [s] such that φ(R) ≠ R for some R ∈ R_{i,j} ∪ R_{j,i} (resp. its cardinality). Then, obviously, t(ψ_{a}) = 3. So to prove statement (1) it suffices to check that

t(φ_{g}) ≡ 0 (mod 2), g ∈ G^{s}  (16)

where φ_{g} is the weak isomorphism of W induced by g (see Subsection 5.1). It is easy to see that

|T (φ_{gh})| = |T (φ_{g})| + |T (φ_{h})| − 2|T (φ_{g}) ∩ T (φ_{h})|, g, h ∈ G^{s}

whence t(φ_{gh}) = t(φ_{g}) + (φ_{h}) (mod 2) for all g, h. Now (16) follows from the straightforward equality t(φ_{g}) = 2 where g = (g_{1}, …, g_{s}) with exactly one of g_{i}’s not equal to 1.

To prove (2) it suffices to verify that for φ = ψ_{a} conditions (i′) and (ii′) of Corollary 4.7 are satisfied. Let U ∈ Cel_{k}^{∗}(W). Denote by C_{U} the vertex set of a largest connected component of the graph Γ\X_{U} where X_{U} is the subset of [s] corresponding to the cells of W contained in U. Choose a vertex b = b_{U} ∈ C_{U} and a path P = P_{U} in the graph Γ from a to b. Then by (15) and the fact that b ∉ U we have (φ_{P})_{U} = (ψ_{a})_{U}. So the condition (i′) is satisfied for h = g_{P}.

Let U_{1}, U_{2} ∈ Cel_{k}^{∗}(W). Set b_{i} = b_{U_{i}}, C_{i} = C_{U_{i}}, X_{i} = X_{U_{i}}, P_{i} = P_{U_{i}} (i = 1, 2). Then |C_{i}| > s/2, since X_{i} is not a separator of Γ by the hypothesis of statement (2). So C_{1} ∩ C_{2} ≠ ∅ and there exists a path P_{1,2} in Γ from b_{1} to b_{2} all vertices of which belong to C_{1} ∪C_{2}. Set P = P_{1} ·P_{1,2} ·P_{2}^{−1}. Then by (14) and the fact that P_{1,2} contains no vertices of U = U_{1} ∩ U_{2} we have

(g_{P})_{U} = (g_{P_{1}}g_{P_{1,2}}g_{P_{2}}^{−1})_{U} = (h_{1})_{U}(h_{2}^{−1})_{U}

where h_{1} = g_{P_{1}}, h_{2} = g_{P_{2}}. It follows from statement (2) of Lemma 5.3 that g_{P} ∈ Aut(W). Thus the condition (ii′) is satisfied for h = g_{P}.

Remark 5.6 Let Γ(W) be a connected cubic graph and φ_{1}, φ_{2} ∈ Isow(W) be weak isomorphisms leaving any cell of W fixed such that (φ_{1})_{V_{i}} = (φ_{2})_{V_{i}} for all i ∈ [s]. Then it can be proved by the same technique that φ_{1}φ_{2}^{−1} is induced by a strong isomorphism of W iff t(φ_{1}) = t(φ_{2}) (mod 2).

5.4. Proof of Theorem 1.3. It follows from [12] and [14] that for all sufficiently large l the graph CD(l, 3) defined in [12] is a connected, edge-transitive, cubic Ramanujan graph with s_{l} = 2 · 3^{l−⌊ \frac{l+2}{4} ⌋+1} vertices. One can easily veryfy that there exists ε′ > 0 such that any cubic Ramanujan graph with s vertices has no separator of cardinality k for all k ≤ ε′s. By Lemma 5.2 there exists a cellular algebra W (l) ∈ K^{∗} on 4s_{l} points with Γ(W (l)) = CD(l, 3). So by Theorem 5.5 there exists an ⌊\frac{s_{l}ε′}{3} ⌋-isomorphism φ(l) of W (l) which is not induced by a strong isomorphism. According to [15] the graph CD(l, 3) being a connected edge-transitive cubic graph, is 3-connected. Thus W (l) is a Schurian algebra by statement (3) of Lemma 5.3.

Let us define a cellular algebra W_{n} on n points by W_{n} = W (l) ⊞ Mat_{n−4s_{l}} where l is the largest positive integer for which 4s_{l} ≤ n. Let φ_{n} be the weak isomorphism of W_{n} coinciding with φ(l) on the first summand and identical on the second one. Then by above W_{n} is a Schurian algebra and φ_{n} is not induced by a strong isomorphism for all sufficiently large n. Set m = ⌊\frac{s_{l}ε′}{3} ⌋. Since φ(l) ∈ Isow_{m}(W (l)), Theorem 7.6 implies that φ_{n} ∈ Isow_{m}(W_{n}). Taking into account the inequality s_{l}/n ≥ s_{l}/s_{l+1} ≥ 1/12, we conclude that m ≥ ⌊nε⌋ where ε = ε′/36.

5.5. Proof of Theorem 1.1. Let W and φ be the Schurian algebra on n points and the m-isomorphism from Theorem 1.3. Set W′ = W ≀_{Ψ} G where W = {W_{i}}_{i=1}^{2}, Ψ = {ψ_{i,j}}_{i,j=1}^{2}, G = Sym(2) with W_{1} = W_{2} = W and ψ_{1,2} = φ. Then by statement (3) of Theorem 7.7 the algebra W′ is m-closed. On the other hand, W′ is not Schurian by Corollary 7.9. Thus for a sufficiently large even integer the required algebra is constructed. The odd case is reduced to the even one by considering the algebra W′ ⊞ Mat_{1}.

6 Proof of Theorem 1.4

We start with the description of the m-dimensional Weisfeiler-Lehman method and the Schurian polynomial approximation scheme associated with it. Below a mapping f from V^{m} to the set of positive integers is called a coloring of V^{m}. Any nonempty set f^{−1}(i) ⊂ V^{m} is called a color class of f. The following algorithm was described in [3] (see also [4]).

m-dim stabilization

Input: a coloring f_{0} of V^{m}. Output: a coloring f of V^{m}.

Step 1. Set k = 0. Step 2. For each v̄ ∈ V^{m} find a formal sum S(v̄) = ∑_{u∈V} f_{k}(v̄/u) where v̄/u = (v̄_{1,u}, …, v̄_{m,u}) with v̄_{i,u} = (v_{1}, …, v_{i−1}, u, v_{i+1}, …, v_{m}), and f_{k}(v̄/u) = (f_{k}(v̄_{1,u}), …, f_{k}(v̄_{m,u})). Step 3. Find a coloring f_{k+1} of V^{m} such that

f_{k+1}(v̄) = f_{k+1}(v̄′) ⇔ (f_{k}(v̄) = f_{k}(v̄′), S(v̄) = S(v̄′)).

If the numbers of color classes of f_{k} and f_{k+1} are different, then k := k + 1 and go to Step 2. Otherwise set f = f_{k}.

For a cellular algebra W on V with standard basis R let us denote by f_{0} the coloring of V^{m} defined by

f_{0}(v̄) = f_{0}(v̄′) ⇔ ∀R ∈ R ∀i, j ∈ [m] : ((v_{i}, v_{j}) ∈ R ⇔ (v′_{i}, v′_{j}) ∈ R)

and set

WL_{1}(W) = W and WL_{m}(W) = [R_{f}], m ≥ 2

where f is the coloring of V^{m} derived from f_{0} by the m-dim stabilization procedure and R_{f} is the set of the adjacency matrices of the relations

{(u′, v′) ∈ V × V : f(u′, …, u′, v′) = f(u, …, u, v)}, u, v ∈ V.

Let us define P_{m} = P_{m}(W) to be the partition of V^{m} into the cells of W if m = 1, and into the color classes of f if m ≥ 2. In the last case denote by P_{m,k}(W), k = 0, …, k̄ the partition of V^{m} into the classes of the coloring f_{k} obtained in applying the m-dim stabilization procedure to the coloring f_{0}. Then

P_{m,0} ≤ P_{m,1} ≤ ⋯ ≤ P_{m,k̄} = P_{m}  (17)

where for partitions P, P′ of V^{m} we write P ≤ P′ if P′ is the refinement of P.

Theorem 6.1 The partition P = P_{m}(W), m ≥ 1 satisfies the following conditions:

(P1) P is normal, i.e. the set π_{L}^{−1}(Δ^{(L)}) is a union of the elements of P for all L ⊂ M where Δ^{(L)} = Δ^{(L)}(V) = {(v, …, v) ∈ V^{L} : v ∈ V } and π_{L} = π_{L}^{M} : V^{M} → V^{L} is a natural projection,

(P2) P is invariant, i.e. P^{g} = P for all g ∈ Sym(M) where P^{g} = {T^{g} : T ∈ P}, g ∈ Sym(M),

(P3) P is regular, i.e. given T ∈ P, S ∈ π_{L}(P) the number |π_{L}^{−1}(\overline{u}) ∩ T | does not depend on \overline{u} ∈ S for all L ⊂ M where π_{L}(P) = \{π_{L}(T) : T ∈ P\},

where M = [m].

Proof. It follows from the definition of the coloring f_{0} that the partition P_{m,0} satisfies conditions (P1) and (P2). So P_{m,k+1} and hence P_{m} satisfies (P1) by (17) and (P2) by the definition of f_{k+1} at Step 3. Thus it suffices to check that P_{m} satisfies condition (P3) or, equivalently, the following condition:

(P3^{∗}) given l ∈ [m − 1] and S ∈ π_{l+1}(P), R ∈ π_{l}(P) the number |(π_{l}^{l+1})^{−1}(\overline{u}) ∩ S| does not depend on \overline{u} ∈ R

where π_{l}^{l+1} = π_{[l]}^{[l+1]} and π_{l} = π_{[l]}.

For l ∈ [m] let η_{l} be the mapping defined by

η_{l} : V^{m} → V^{m}, (v_{1}, …, v_{m}) ↦ (v_{1}, …, v_{l}, v_{1}, …, v_{1}).

Lemma 6.2 T ∈ P_{m} implies η_{l}(T) ∈ P_{m}.

Proof. Using induction on l = m, m − 1, … we assume that T = η_{l+1}(T). Let \overline{v} = (v_{1}, …, v_{m}) ∈ T. Then by the definition of the initial coloring f_{0} and formula (17) we conclude that the final color of the tuple \overline{v}_{l+1,u} for u = v_{1} differs from that for u ≠ v_{1} (see Step 2). So the final color of η_{l}(\overline{v}) does not depend on the choice of \overline{v} in the color class T due to the termination condition at Step 3. Thus η_{l}(T) ⊂ T′ for some T′ ∈ P_{m}. To prove the inverse inclusion we observe that T′ ⊂ η_{l}(V^{m}). On the other hand, given \overline{v}′ ∈ T′ the number |\{u ∈ V : \overline{v}′_{l+1,u} ∈ T \}| does not depend on \overline{v}′ and is positive since η_{l}(T) ≠ ∅. Thus T′ ⊂ η_{l}(T).

To prove (P3^{∗}) set S = π_{l+1}(T) and R = π_{l}(T′) where T, T′ ∈ P_{m}. By Lemma 6.2 we assume T = η_{l+1}(T), T′ = η_{l}(T′). For \overline{u} ∈ V^{l} set \overline{v} = η_{l}(\overline{v}′) where \overline{v}′ is any element of the set (π_{l}^{m})^{−1}(\overline{u}). Then obviously

|(π_{l}^{l+1})^{−1}(\overline{u}) ∩ S| = |\{u ∈ V : \overline{v}_{l+1,u} ∈ T \}|.

If \overline{u} runs over R, then \overline{v} runs over T′. Since the right side of the last equality does not depend on \overline{v} ∈ T′, we conclude that the left side of it does not depend on \overline{u} ∈ R.

Below given a finite set M a partition P of V^{M} satisfying (P1)–(P3) will be called stable. The following statement contains the simplest properties of a stable partition to be used in proving Theorem 1.4.

Lemma 6.3 Let P be a stable partition of V^{M}. Then

(1) π_{L}(P) is a stable partition of V^{L} for all L ⊂ M,

(2) if M = I × K, then P is a stable partition of (V^{I})^{K},

(3) if M = [3], then π_{[2]}(P) is the set of basis relations of a cellular algebra on V.

Proof. To prove statement (1) we observe first that the elements of π_{L}(P) are pairwise disjoint by (P3) and so π_{L}(P) is a partition of V^{L}. The obvious equality (π_{K}^{L})^{−1}(Δ^{(K)}) = π_{L}(π_{K}^{−1}(Δ^{(K)})) with K ⊂ L implies that this partition is normal. It is also invariant since π_{L}(T)^{g} = π_{L}(T g̃) for all g ∈ Sym(L) where g̃ is the image of g under the natural injection of Sym(L) into Sym(M). Finally, let S ∈ π_{L}(P), R ∈ π_{K}^{L}(π_{L}(P)), K ⊂ L, and \overline{u} ∈ R. Then

|V |^{|M\L|}|(π_{K}^{L})^{−1}(\overline{u}) ∩ S| = |π_{L}^{−1}((π_{K}^{L})^{−1}(\overline{u}) ∩ S)| = |π_{K}^{−1}(\overline{u}) ∩ π_{L}^{−1}(S)|.

Since π_{L}(P) is a partition of V^{L}, we see that π_{L}^{−1}(S) = ⋃_{T ∈P,T ∈π_{L}^{−1}(S)} T. So the last number equals ∑_{T} |π_{K}^{−1}(\overline{u}) ∩ T |. Thus the regularity of π_{L}(P) follows from the regularity of P.

Let us prove statement (2). The normality of P as a partition of (V^{I})^{K} follows from the equality

(π_{J}^{K})^{−1}(Δ^{(J)}(V^{I})) = ⋂_{i∈I} π_{{i}×J}^{−1}(Δ^{({i}×J)})

where J ⊂ K and the normality of P as a partition of V^{M}. The invariance (resp. regularity) of P as a partition of (V^{I})^{K} is obtained by the specialization of (P2) (resp. (P3)) for g belonging to the subgroup of Sym(M) equal to the wreath product of the identity group on I and Sym(K) (resp. for L = I × J, J ⊂ K).

Let us prove the third statement. Set R = π_{[2]}(P). It follows from statement (1) that R is a stable partition of V^{2}. In particular, V^{2} and Δ^{([2])}(V) are unions of the elements of R. Besides, R^{T} = R since R^{T} = R^{g} for all R ∈ R where g is the transposition belonging to Sym(2). So it suffices to check that given Q, R, S ∈ R the number

p(u_{1}, u_{2}; Q, R) = |{u ∈ V : (u_{1}, u) ∈ Q, (u, u_{2}) ∈ R}|

does not depend on the choice of (u_{1}, u_{2}) ∈ S. However, p(u_{1}, u_{2}; Q, R) coincides with the sum of the numbers |π_{L}^{−1}(\overline{u}) ∩ T | where L = [2], \overline{u} = (u_{1}, u_{2}) ∈ S and T runs over the elements of P contained in the set

π_{L}^{−1}(Q) ∩ π_{L}^{−1}(R)^{g} ∩ π_{L}^{−1}(S)^{h}

with g = (1, 2, 3), h = (2, 3) in cyclic notation. By (P3) these numbers do not depend on \overline{u}.

Now we are ready to prove Theorem 1.4. Let us compare the partitions of Cartesian powers of V associated with the Schurian polynomial approximation schemes \{\overline{W}^{(m)}\} and \{WL_{m}(W)\} where W is a cellular algebra on V.

Theorem 6.4 For all cellular algebra W and all m ≥ 1

P_{m}(W) ≤ Cel(Ŵ^{(m)}),  R(Ŵ^{(m)}) ≤ π_{2m}(P_{3m}(W)).  (18)

(We consider the elements of R(Ŵ^{(m)}) as subsets of V^{2m}, see proof of Theorem 3.2.)

Proof. The first inequality was in fact proved in Proposition 4.1 of [4]. According to Theorem 6.1 P_{3m}(W) is a stable partition of V^{3m}. So by Lemma 6.3 there exists a cellular algebra Â_{m}(W) on V^{m} whose set of basis relations coincides with π_{2m}(P_{3m}(W)). It follows from (P1) with P = P_{3m}(W) that I_{Δ^{(m)}} ∈ Â_{m}(W). Besides, R(W^{m}) ≤ π_{2m}(P_{3m,0}(W)) by the definition of the initial coloring f_{0}, whence W^{m} ≤ Â_{m}(W). Thus

Ŵ^{(m)} ≤ Â_{m}(W)

by Theorem 3.2.

The inclusion WL_{m}(W) ≤ \overline{W}^{(m)} was proved in Theorem 1.2 of [4] (in fact deduced from the first inequality of Theorem 6.4). To prove the inclusion \overline{W}^{(m)} ≤ WL_{3m}(W) we observe that by Theorem 6.1 the partition P_{3m}(W) is stable and hence

R(WL_{3m}(W)) = π_{2}(P_{3m}(W)) = π_{2}(π_{2m}(P_{3m}(W))) = π_{2}(R(Â_{m}))

where Â_{m} = Â_{m}(W) is the cellular algebra on V^{m} defined in the proof of Theorem 6.4. On the other hand, the stability of partition π_{2m}(P_{3m}(W)) (see Lemma 6.3) implies that π_{2}(R(Â_{m})) = R(((Â_{m})_{Δ})^{δ^{−1}}) where Δ and δ are defined in Subsection 3.1. So by the second inequality of Theorem 6.4 we have

R(WL_{3m}(W)) = R(((Â_{m})_{Δ})^{δ^{−1}}) ≥ R(((Ŵ^{(m)})_{Δ})^{δ^{−1}}) = R(\overline{W}^{(m)}).

This completes the proof of Theorem 1.4.

7 Appendix

7.1. Throughout the subsection we denote by W_{i} (resp.W′_{i}) a cellular algebra on a set V_{i} (resp.V′_{i}) where i ∈ [s].

Following [17] we call the cellular algebra

⊞_{i=1}^{s} W_{i} = [⋃_{i=1}^{s} R(W_{i})]

on the disjoint union V of V_{i}’s the direct sum of W_{i}’s. Obviously, it does not depend on the ordering of the summands. Any set V_{i} is a cellular set of this algebra. Any of its basis relations contained in V_{i} × V_{j} coincides with a basis relation of W_{i} (for i = j) or equals the direct product of a cell of W_{i} and a cell of W_{j} (for i ≠ j).

Let φ_{i} ∈ Isow(W_{i}, W′_{i}) for all i ∈ [s]. Then the mapping

φ : ⊞_{i=1}^{s} W_{i} → ⊞_{i=1}^{s} W′_{i}  (19)

coinciding with φ_{i} on W_{i} and taking J_{X,Y} to J_{X′,Y′} where X ∈ Cel(W_{i}), Y ∈ Cel(W_{j}), i ≠ j, and X′ = X^{φ_{i}}, Y′ = Y^{φ_{j}}, is obviously a weak isomorphism. We say that it is induced by φ_{i}’s. It is easy to see that each weak isomorphism φ of the direct sums such that φ(W_{i}) = W′_{i} for all i can be obtained in this way.

Let W ≤ Mat_{V} be a cellular algebra and Φ ⊂ Isow(W) be a group of its weak isomorphisms. Then according to [5] the set W^{Φ} = {A ∈ W : φ(A) = A, φ ∈ Φ} is a cellular algebra on V. If Φ ⊂ Isow_{m}(W), then Ŵ^{Φ} ≤ Ŵ Φ̂ where Φ̂ = {φ̂^{(m)} : φ ∈ Φ}.

Let now W = {W_{i}}_{i=1}^{s} and Ψ = {ψ_{i,j}}_{i,j=1}^{s} with ψ_{i,j} ∈ Isow(W_{i}, W_{j}) such that

ψ_{i,j} ψ_{j,k} = ψ_{i,k},  i, j, k ∈ [s]  (20)

It is easy to see that ψ_{i,i} = id_{W_{i}} and ψ_{i,j}^{−1} = ψ_{j,i} for all i, j. Any permutation g ∈ Sym(s) induces s weak isomorphisms ψ_{i,i^{g}} : W_{i} → W_{i^{g}}, i ∈ [s], and hence by (19) a weak isomorphism φ_{g} : W → W where W = ⊞_{i=1}^{s} W_{i}. Obviously, given a group G ≤ Sym(s) the set Φ(Ψ, G) = {φ_{g} : g ∈ G} is a subgroup of Isow(W).

Definition 7.1 The cellular algebra W^{Φ} with Φ = Φ(Ψ, G) is called the wreath product of the family W by the group G with respect to Ψ and is denoted by W ≀_{Ψ} G ^{1}.

The algebra W ≀_{Ψ} G contains two subalgebras

W^{Ψ} = {∑_{i=1}^{s} A_{i} : A_{i} ∈ W_{i}, A_{j} = ψ_{i,j}(A_{i}), i, j ∈ [s]}  (21)

and

W^{G} = { ∑_{O∈Orb_{2}(G)} α_{O}A_{O}, α_{O} ∈ ℂ},  A_{O} = ∑_{(i,j)∈O} J_{V_{i},V_{j}}  (22)

closed under the Hadamard multiplication and the Hermitian conjugation. It is easy to see that

W ≀_{Ψ} G = [W^{Ψ}, W^{G}].  (23)

Let W = W ≀_{Ψ} G with W = {W_{i}}_{i=1}^{s}, Ψ = {ψ_{i,j}}_{i,j=1}^{s}, W′ = W′ ≀_{Ψ′} G with W′ = {W′_{i}}_{i=1}^{s}, Ψ′ = {ψ′_{i,j}}_{i,j=1}^{s} and φ_{i} ∈ Isow(W_{i}, W′_{i}) for all i. If

φ_{i} ψ′_{i,j} = ψ_{i,j} φ_{j}, i, j ∈ [s],  (24)

then φ(W^{Ψ}) = (W′)^{Ψ′} and φ(W^{G}) = (W′)^{G} where φ is the weak isomorphism (19). By (23) this defines by restriction a weak isomorphism from W to W′ such that

φ(A_{O}) = A′_{O} for all O ∈ Orb_{2}(G).  (25)

In this case we say that it is induced by φ_{i}’s. Conversely, any φ ∈ Isow(W, W′) for which (25) is satisfied can be obtained in this way with uniquely determined φ_{i}’s.

According to [17] the tensor product ⨂_{i=1}^{s} W_{i} can be considered as a cellular algebra on the set ∏_{i=1}^{s} V_{i}. The basis matrices (resp. cells) of this algebra are exactly the Kronecker (resp. direct) products of the basis matrices (resp. cells) of W_{i}’s.

7.2. Here given a cellular algebra W ≤ Mat_{V} we define and study an auxiliary cellular algebra Ŵ^{∗} on the set V^{∗} = ⋃_{I⊂[m]} V^{I}. Below we denote by Mat_{V_{1},V_{2}} the linear space of all complex matrices the rows and columns of which are indexed by the elements of sets V_{1} and V_{2} respectively. The tensor product Mat_{V_{1},V_{2}} ⊗ Mat_{V′_{1},V′_{2}} is naturally identified with Mat_{V_{1}×V′_{1},V_{2}×V′_{2}}.

Given I, J ⊂ [m] let D_{I,J} = D_{I,J}(V) denotes the adjacency matrix of the binary relation \{(\overline{u}, \overline{v}) ∈ V^{I} × V^{J} : u_{i} = v_{i}, i ∈ I ∩ J\}. Set D_{I} = D_{I}(V) = D_{I,[m]}(V) and d_{I} = d_{I}(V) = |V |^{m−|I|}. Then

D_{I,I} = I_{V^{I}}, (D_{I,J})^{T} = D_{J,I}, d_{I∪J}D_{I,J} = D_{I}D_{J}^{T} .  (26)

Besides,

D_{I}^{T} D_{I} = E_{I}, D_{I}E_{I} = d_{I}D_{I}, E_{I}^{2} = d_{I}E_{I}  (27)

1We note that if G is transitive and W_{i} is homogeneous for all i, this is a special case of the corresponding construction of [17].

where E_{I} is the adjacancy matrix of the relation \{(\overline{u}, \overline{v}) : V^{m} × V^{m} : u_{i} = v_{i}, i ∈ I\}. We also observe that E_{I} ∈ Z_{m}(V).

For I, J ⊂ [m] set

Ŵ_{I,J} = D_{I} ŴD_{J}^{T} ,  R̂_{I,J} = {R_{I,J} : R_{I,J} = (d_{I,J}^{R})^{−1}D_{I}RD_{J}^{T} , R ∈ R̂}

where R̂ = R(Ŵ) and d_{I,J}^{R} is the coefficient at R in the decomposition of the matrix E_{I}RE_{J} with respect to R̂. Both of the sets are contained in Mat_{V^{I},V^{J}}. Set

Ŵ^{∗} = ∑_{I,J⊂[m]} Ŵ_{I,J},  R̂^{∗} = ⋃_{I,J⊂[m]} R̂_{I,J}(W).

Obviously, the sum is meant to be direct and the union is meant to be disjoint.

Lemma 7.2 The following statements hold:

(1) The linear space Ŵ^{∗} is a cellular algebra on V^{∗} and the set R̂^{∗} is its standard basis.

(2) Ŵ^{∗} = [Ŵ, {D_{I}}_{I⊂[m]}].

(3) For each I ⊂ [m] the set V^{I} is a cellular set of Ŵ^{∗}. Moreover, (Ŵ^{∗})_{V^{l}} ≥ Ŵ^{(l)} for all l ∈ [m] and also (Ŵ^{∗})_{V^{m}} = Ŵ, (Ŵ^{∗})_{V} = \overline{W}.

(4) Let I, J ⊂ [m] and {I_{k}}_{k=1}^{s}, {J_{k}}_{k=1}^{s} be partitions of I and J (with some of I_{k}, J_{k} possibly empty). Then ⨂_{k=1}^{s} Ŵ_{I_{k},J_{k}} ⊂ Ŵ_{I,J}.

Proof. Let us show that any matrix A = D_{I}RD_{J}^{T}, R ∈ R̂, is a d_{I,J}^{R}-multiple of a {0,1}- matrix. It is easy to see that given (\overline{u}, \overline{v}) ∈ V^{I} × V^{J} the number A_{\overline{u},\overline{v}} equals any (\overline{u}′, \overline{v}′)-element of the matrix B = E_{I}RE_{J} with (D_{I})_{\overline{u},\overline{u}′} > 0, (D_{J})_{\overline{v},\overline{v}′} > 0. If A_{\overline{u},\overline{v}} ≠ 0, then \overline{u}′, \overline{v}′ can be chosen so that in addition R_{\overline{u}′,\overline{v}′} > 0. So A_{\overline{u},\overline{v}} = B_{\overline{u}′,\overline{v}′} = d_{I,J}^{R} by the definition of d_{I,J}^{R}. Thus R̂_{I,J} consists of {0,1}-matrices. Moreover, any two of them are orthogonal with respect to the Hadamard multiplication or coincide. Indeed, let R_{I,J} ∘ S_{I,J} ≠ 0 where R, S ∈ R̂. Then S ∘ (E_{I}RE_{J}) ≠ 0 and R ∘ (E_{I}SE_{J}) ≠ 0. Since the matrices E_{I}RE_{J}, E_{I}SE_{J} belong to Ŵ and are multiples of {0,1}-matrices, they (and hence also D_{I}RD_{J}, D_{I}SD_{J}) coincide up to a scalar factor. It follows from above that the set R̂^{∗} consists of {0,1}-matrices summing up to J_{V^{∗}}. Besides, it is easy to see that it is closed under transposition and linearly spans Ŵ^{∗}. Since Ŵ_{I,J} Ŵ_{J,K} ⊂ Ŵ_{I,K} (see (27)), statement (1) follows. Statement (2) is the consequence of the definition of Ŵ^{∗}, statement (1) and the fact that D_{I} ∈ Ŵ_{I,[m]} for all I ⊂ [m]. To prove statement (3) it suffices to check that (Ŵ^{∗})_{V^{l}} ≥ Ŵ^{(l)}. To do this we observe that

I_{Δ^{(l)}} = D_{[l]}I_{Δ^{(m)}}D_{[l]}, R_{1} ⊗ … ⊗ R_{l} = d_{[l]}^{−1}D_{[l]}(R_{1} ⊗ … ⊗ R_{l} ⊗ I_{V} ⊗ … ⊗ I_{V})D_{[l]} (28)

where R_{i} ∈ R(W) for all i ∈ [l]. Thus we are done by Theorem 3.2 (with m = l).

Let us prove statement (4). First we observe that for all l ∈ [s]

D_{I,I_{l}}A_{l}D_{J_{l},J} = ⨂_{k=1}^{s} C_{k}^{(l)}, A_{l} ∈ Mat_{V^{I_{l}},V^{J_{l}}}

where C_{k}^{(l)} is the all-one matrix of Mat_{V^{I_{k}} ,V^{J_{k}}} if k ≠ l, and C_{l}^{(l)} = A_{l}. Since the Hadamard multiplication in Mat_{V^{I},V^{J}} = ⨂_{k=1}^{s} Mat_{V^{I_{k}} ,V^{J_{k}}} can be done factorwise, we come to the equality

(D_{I,I_{1}}A_{1}D_{J_{1},J}^{T}) ∘ ⋯ ∘ (D_{I,I_{s}}A_{s}D_{J_{s},J}^{T}) = ⨂_{k=1}^{s} A_{k}.  (29)

Thus, if A_{k} ∈ Ŵ_{I_{k},J_{k}} for all k, then by statement (1) each Hadamard factor in the left side of (29) (and hence the whole product) belongs to Ŵ_{I,J}.

We complete the subsection by defining and studying some natural weak isomorphisms of our auxiliary algebras.

Lemma 7.3 Let φ ∈ Isow_{m}(W, W′) and ψ = φ̂. Then

(1) There exists a uniquely determined weak isomorphism ψ^{∗} : Ŵ^{∗} → Ŵ′^{∗} such that (ψ^{∗})_{V^{m}} = ψ and ψ^{∗}(D_{I}) = D′_{I} for all I ⊂ [m].

(2) The mapping (ψ^{∗})_{V^{l}} induces by restriction an l-extension of φ for all l ∈ [m]. In particular, (ψ^{∗})_{V} : \overline{W} → \overline{W′} extends φ.

Proof. To prove statement (1) set

ψ^{∗}(A) = (d_{I}d_{J})^{−1}D′_{I}ψ(D_{I}^{T} AD_{J})(D′_{J})^{T} , A ∈ Ŵ_{I,J}.

It immediately follows from (26) and (27) that ψ^{∗}(A) = ψ(A) for all A from Ŵ = (Ŵ^{∗})_{V^{m}} and also ψ^{∗}(D_{I}) = D′_{I} for all I ⊂ [m]. Moreover, making use of the same properties of the matrices D_{I} and E_{I} we have for A ∈ Ŵ_{I,J}, B ∈ Ŵ_{J.K}:

d_{I}d_{K}ψ^{∗}(AB) = D′_{I}ψ(D_{I}^{T} ABD_{K})(D′_{K})^{T} = d_{J}^{−1}D′_{I}ψ(D_{I}^{T} AD_{J})ψ(D_{J}^{T} BD_{K})(D′_{K})^{T} =

d_{J}^{−3}D′_{I}ψ(D_{I}^{T} AD_{J}E_{J})ψ(E_{J}D_{J}^{T} BD_{K})(D′_{K})^{T} = d_{J}^{−2}D′_{I}ψ(D_{I}^{T} AD_{J})E′_{J}ψ(D_{J}^{T} BD_{K})(D′_{K})^{T} =

d_{J}^{−2}D′_{I}ψ(D_{I}^{T} AD_{J})(D′_{J})^{T} D′_{J}ψ(D_{J}^{T} BD_{K})(D′_{K})^{T} = d_{I}d_{K}ψ^{∗}(A)ψ^{∗}(B).

This shows that ψ^{∗} is a matrix algebra isomorphism. In particular,

ψ^{∗}(R_{I,J}) = (d_{I,J}^{R})^{−1}ψ^{∗}(D_{I})ψ(R)ψ^{∗}(D_{J}^{T}) = (d_{I,J}^{ψ(R)})^{−1}D′_{I}ψ(R)(D′_{J})^{T} = ψ(R)_{I,J}

for all R ∈ R̂ and I, J ⊂ [m]. Thus ψ^{∗} preserves the Hadamard multiplication and hence is a weak isomorphism. Since the uniqueness of ψ^{∗} follows from statement (2) of Lemma 7.2, we are done.

The second statement of the lemma follows from the first one, statement (3) of Lemma 7.2 and formula (28).

The isomorphism (ψ^{∗})_{V} will be denoted by \overline{φ} and called the m-closure of φ.

7.3. It is clear that the direct sum is Schurian iff so is any of its summands. In this subsection we generalize this observation to m-closed algebras. To do this we need to study the m-extended algebra of the direct sum.

Theorem 7.4 Let W = ⊞_{k=1}^{s} W_{k}. Then the set V^{∗} is a cellular set of the algebra ⨂_{k=1}^{s} Ŵ_{k}^{∗} and

Ŵ^{∗} = (⨂_{k=1}^{s} Ŵ_{k}^{∗})_{V^{∗}}.  (30)

Proof. It is easy to see that given I ⊂ [m] we have V^{I} = ⋃_{I} V^{I} where I = {I_{k}}_{k=1}^{s} runs over all ordered partitions of the set I into s classes (possibly empty) and V^{I} = ∏_{k=1}^{s} V_{k}^{I_{k}}. Since V_{k}^{I_{k}} is a cellular set of the algebra Ŵ_{k}^{∗} the first part of the theorem follows. Further, the right side of (30) denoted by W′ below, coincides with the direct sum over all I, J ⊂ [m] and all partitions {I_{k}}_{k=1}^{s} and {J_{k}}_{k=1}^{s} of I an J of the linear spaces ⨂_{k=1}^{s}(Ŵ_{k})_{I_{k},J_{k}}. Since (Ŵ_{k})_{I_{k},J_{k}} ⊂ Ŵ_{I_{k},J_{k}} for all k, we conclude by statement (4) of Lemma 7.2 that W′ is a subalgebra of Ŵ^{∗} .

To prove the inverse inclusion it suffices to check by statement (2) of Lemma 7.2 and Theorem 3.2 that W′ contains the algebra W^{m} and the matrices I_{Δ} and D_{I}, I ∈ [m]. Let us prove that I_{Δ} ∈ W′. Since I_{Δ} = ∑_{k=1}^{s} I_{Δ_{k}} where Δ_{k} = Δ^{(m)}(V_{k}), we need only to check that I_{Δ_{k}} ∈ W′ for all k. Given k ∈ [s] let us define a partition {I_{l}} of [m] so that I_{l} = ∅ for l ≠ k and I_{k} = [m]. Then, obviously,

I_{Δ_{k}} ∈ Ŵ_{k} = ⨂_{l=1}^{s}(Ŵ_{l})_{I_{l},I_{l}} ⊂ W′.

Further, given I ⊂ [m] it is easy to see that

D_{I} = ∑_{{I_{k}},{J_{k}}} ⨂_{k=1}^{s} D_{I_{k},J_{k}}(V_{k})

where the sum is taken over all partitions of the sets I and [m] respectively with I_{k} ⊂ J_{k} for all k ∈ [s]. Since D_{I_{k},J_{k}}(V_{k}) = d_{J_{k}}(V_{k})^{−1}D_{I_{k}}(V_{k})D_{J_{k}}(V_{k})^{T} (see (26)) and D_{I_{k}}(V_{k}), D_{J_{k}}(V_{k}) belong to Ŵ_{k}^{∗} by statement (2) of Lemma 7.2, we conclude that D_{I} ∈ W′.

Let us prove now that W^{m} ⊂ W′. It follows from the definition of the direct sum that W coincides with the cellular closure of the sets R(W_{k}), k ∈ [s], and the matrices J_{V_{k},V_{l}}, k, l ∈ [s]. So it suffices to prove that W′ contains any matrix A = ⨂_{i=1}^{m} A_{i} with A_{i} ∈ R(W_{k}) for some k or A_{i} = J_{V_{k},V_{l}} = J_{V_{k},∅} ⊗ J_{∅,V_{l}} for k ≠ l. Let us define partitions {I_{k}} and {J_{k}} of [m] by

I_{k} = {i ∈ [m] : A_{i} ∈ Mat_{V_{k},V} }, J_{k} = {i ∈ [m] : A_{i} ∈ Mat_{V,V_{k}}}.

Then

A = ⨂_{k=1}^{s} A^{(k)} with A^{(k)} = A^{(k,0)} ⊗ A^{(k,1)} ⊗ A^{(k,2)}

where A^{(k,0)} = ⨂_{i∈I_{k}∩J_{k}} A_{i}, A^{(k,1)} = D_{I_{k}\J_{k},∅}(V_{k}), A^{(k,2)} = D_{∅,J_{k}\I_{k}}(V_{k}). We only need to prove that A^{(k)} ∈ (Ŵ_{k})_{I_{k},J_{k}} for all k ∈ [s]. However, this follows from statement (4) of Lemma 7.2 applied to the partitions of I_{k} and J_{k} with 3 classes I_{k,0} = J_{k,0} = I_{k} ∩J_{k}, I_{k,1} = I_{k} \ J_{k}, I_{k,2} = J_{k,1} = ∅ and J_{k,2} = J_{k} \ I_{k}.

Theorem 7.4 enables us to obtain the following decomposition of the m-extended algebra of the direct sum:

Ŵ = ∑_{I,J} Ŵ_{I,J} ,  Ŵ_{I,J} = ⨂_{k=1}^{s}(Ŵ_{k})_{I_{k},J_{k}}  (31)

where I = {I_{k}}_{k=1}^{s} and J = {J_{k}}_{k=1}^{s} run over all ordered partitions of the set [m] into s classes (possibly empty). According to this each basis matrix of Ŵ can uniquely be represented as the Kronecker product over k ∈ [s] of the “basis” matrices of (Ŵ_{k})_{I_{k},J_{k}}.

For each k ∈ [s] let us define the partition I^{(k)} = {I_{l}^{(k)}}_{l=1}^{s} of the set [m] by I_{l}^{(k)} = ∅, if l ≠ k, and I_{k}^{(k)} = [m]. Then it is easy to see that V^{I^{(k)}} = V_{k}^{m}, Ŵ_{I^{(k)},I^{(k)}} = Ŵ_{k} and Ŵ_{I^{(k)},I^{(l)}} for k ≠ l coincides with the linear span of the matrices J_{X,Y} where X ∈ Cel(Ŵ_{k}), Y ∈ Cel(Ŵ_{l}). Thus, restricting Ŵ to the union of V^{I^{(k)}}, k ∈ [s], we come by (31) to the following statement.

Theorem 7.5 Let W = ⊞_{k=1}^{s} W_{k}. Then

(1) The set U = ⋃_{k=1}^{s} V_{k}^{m} is a cellular set of the algebra Ŵ and Ŵ_{U} = ⊞_{k=1}^{s} Ŵ_{k}.

(2) \overline{W} = ⊞_{k=1}^{s} \overline{W}_{k}.

(3) The algebra W is m-closed iff so is W_{k} for all k.

Another consequence of Theorem 7.4 concerns the m-extensions of weak isomorphisms between direct sums.

Theorem 7.6 Let W = ⊞_{k=1}^{s} W_{k}, W′ = ⊞_{k=1}^{s} W′_{k} and φ : W → W′ be the weak isomorphism induced by weak isomorphisms φ_{k} : W_{k} → W′_{k}, k ∈ [s]. Then φ ∈ Isow_{m}(W, W′) iff φ_{k} ∈ Isow_{m}(W_{k}, W′_{k}) for all k.

Proof. The necessity is obvious. Conversely, let φ_{k} ∈ Isow_{m}(W_{k}, W′_{k}) for all k. It follows from Theorem 7.4 and Lemma 7.2 that the algebras Ŵ and Ŵ′ coincide with the restrictions to V^{m} and to (V′)^{m} of the tensor products ⨂_{k=1}^{s} Ŵ_{k}^{∗} and ⨂_{k=1}^{s} Ŵ′_{k}^{∗} respectively. By statement (1) of Lemma 7.3 the isomorphism φ̂_{k} is extended to the weak isomorphism φ̂_{k}^{∗} : Ŵ_{k}^{∗} → Ŵ′_{k}^{∗} taking (V_{k})^{I} to (V′_{k})^{I} for all I ⊂ [m]. So the restriction to V^{m} of the weak isomorphism ⨂_{k=1}^{s} φ̂_{k}^{∗} is a correctly defined weak isomorphism from Ŵ to Ŵ′ being in fact the m-extension of φ.

7.4. Here we use the results of the previous subsection to give a sufficient condition for the wreath product W≀_{Ψ}G to be m-closed. We note that if ψ_{i,j} ∈ Isow_{m}(W_{i}, W_{j}) for all i, j, then by Theorem 7.6 φ_{g} ∈ Isow_{m}(W) for all g ∈ Sym(s) where W = ⊞_{i=1}^{s} W_{i}. In this case we can consider the group { \atop Φ(Ψ, G)} = \{φ̂_{g} : g ∈ G\} ⊂ Isow(Ŵ).

Theorem 7.7 Let W ≀_{Ψ} G be the wreath product of W = {W_{i}}_{i=1}^{s} by G ≤ Sym(s) with respect to Ψ = {ψ_{i,j}}_{i,j=1}^{s}. Suppose that ψ_{i,j} ∈ Isow_{m}(W_{i}, W_{j}) for all i, j. Then

(1) The set U = ⋃_{i=1}^{s} V_{i}^{m} is a cellular set of { \atop W ≀_{Ψ} G} and ({ \atop W ≀_{Ψ} G})_{U} = Ŵ ≀Ψ̂ G where Ŵ = {Ŵ_{i}}_{i=1}^{s} and Ψ̂ = {ψ̂_{i,j}}_{i,j=1}^{s}.

(2) \overline{W ≀_{Ψ} G} = \overline{W} ≀\overline{Ψ} G where \overline{W} = \{\overline{W_{i}}\}_{i=1}^{s} and \overline{Ψ} = \{\overline{ψ_{i,j}}\}_{i,j=1}^{s} with \overline{ψ_{i,j}} being the m-closure of ψ_{i,j}.

(3) The algebra W ≀_{Ψ} G is m-closed iff so is W_{i} for all i.

Proof. We prove only the first statement since the others are straightforward from it. It is easy to see that the adjacency matrix of the relation ⋃_{i=1}^{s} V_{i}^{m} × V_{i}^{m} ⊂ V^{m} × V^{m} is a multiple of AI_{Δ}A where A is the m-fold tensor product of the matrix ∑_{i=1}^{s} J_{V_{i}} belonging to W ≀_{Ψ} G, and so belongs to { \atop W ≀_{Ψ} G}. Thus the first part of statement (1) follows. Further, since W ≀_{Ψ} G ≤ ⊞_{i=1}^{s} W_{i}, we have

({ \atop W ≀_{Φ} G})_{U} ≤ ⊞_{i=1}^{s} Ŵ_{i}

by statement (1) of Theorem 7.5. The group Φ̂ = { \atop Φ(Ψ, G)} acts trivially on the algebra (W ≀_{Ψ} G)^{m} and leaves the matrix I_{Δ} fixed. So it acts trivially also on { \atop W ≀_{Ψ} G} by Theorem 3.2, which implies that the group Φ(Ψ̂, G) coinciding with Φ̂_{U} acts trivially on ({ \atop W ≀_{Ψ} G})_{U}. Since Ŵ ≀Ψ̂ G is obviously the largest subalgebra of ⊞_{i=1}^{s} Ŵ_{i} with this property, we conclude that

({ \atop W ≀_{Ψ} G})_{U} ≤ Ŵ ≀Ψ̂ G.

To prove the converse inclusion we make use of the equality (23) with W and Ψ replaced by Ŵ and Ψ̂ and verify that ŴΨ̂, Ŵ^{G} ⊂ ({ \atop W ≀_{Ψ} G})_{U}. A straightforward check shows that I_{U}(W^{Ψ})^{m}I_{U} = (W^{m})^{Ψ^{m}} where W^{m} = {W_{i}^{m}}, Ψ^{m} = {ψ_{i,j}^{m}}. So (W^{m})^{Ψ^{m}} ⊂ ({ \atop W ≀_{Ψ} G})_{U}. Since I_{Δ} also belongs to (W ≀_{Ψ} G)_{U}, this algebra contains the smallest algebra satisfying (C2) and (C3) and containing (W^{m})^{Ψ^{m}} and I_{Δ} = ∑_{i=1}^{s} I_{Δ_{i}}. The last algebra coincides with ŴΨ̂ by Theorem 3.2 applied to Ŵ_{i}, i ∈ [s] (see (21)). On the other hand, for any O ∈ Orb_{2}(G) we have

Â_{O} = ∑_{(i,j)∈O} J_{V_{i}^{m},V_{j}^{m}} = I_{U}( ∑_{(i,j)∈O} J_{V_{i},V_{j}})^{m}I_{U} = I_{U}A_{O}^{m}I_{U}

where A_{O}^{m} is the m-fold tensor product of the matrix A_{O} (see (22)). This implies that the algebra Ŵ^{G} spanned by Â_{O}’s is contained in ({ \atop W ≀_{Ψ} G})_{U}, which completes the proof.

Remark 7.8 It follows from the above proof that { \atop W ≀_{Ψ} G} ≤ ({ \atop ⊞_{i=1}^{s} W_{i}})Φ̂. On the other hand, it is easy to see that each Schurian algebra is strongly isomorphic to the wreath product of one-point matrix algebras by its automorphism group. So the equality would imply in particular that the m-extended algebra of a Schurian algebra is also Schurian. However, this does not seem to be true.

Corollary 7.9 Let G be a transitive group. Then the algebra W ≀_{Ψ} G is Schurian iff so is W_{i} for all i and ψ_{i,j} ∈ Isow_{∞}(W_{i}, W_{j}) for all i, j.

Proof. By statement (3), Theorem 4.5 and the fact that \overline{W}^{(m)} = Sch(W) for all W ≤ Mat_{V} and m ≥ n (see Proposition 3.1) it suffices to prove that if W ≀_{Ψ} G is Schurian, then ψ_{i,j} is induced by a bijection g_{i,j} from V_{i} to V_{j} for all i, j. Since the group G is transitive, each cell of W ≀_{Ψ} G meets any set V_{i}. The Schurity of W ≀_{Ψ} G implies then that so does each orbit of its automorphism group. However, the relation ⋃_{i=1}^{s} V_{i} × V_{i} is invariant with respect to this group. So given i, j ∈ [s] there exists an automorphism of W ≀_{Ψ} G taking V_{i} to V_{j}, which produces the required bijection g_{i,j}.

The analog of Theorem 7.6 for wreath products is the following statement in which we use the notation of Subsection 7.1.

Theorem 7.10 Let W = W ≀_{Ψ} G, W′ = W′ ≀_{Ψ′} G and φ : W → W′ be the weak isomorphism induced by weak isomorphisms φ_{i} : W_{i} → W′_{i}, i ∈ [s], satisfying (24). Suppose that ψ_{i,j} ∈ Isow_{m}(W_{i}, W_{j}) for all i, j. Then φ ∈ Isow_{m}(W, W′) iff φ_{i} ∈ Isow_{m}(W_{i}, W′_{i}) for all i.

Proof. Let us prove the necessity. Since U = ⋃_{i=1}^{s} V_{i}^{m} and U′ = ⋃_{i=1}^{s}(V′_{i})^{m} are cellular sets of the algebras Ŵ and Ŵ′ and U φ̂ = U′, we have φ̂(Ŵ_{U}) = Ŵ′_{U′}. By statement (1) of Theorem 7.7 Ŵ_{U} = Ŵ ≀Ψ̂ G where Ŵ = {Ŵ_{i}}, Ψ̂ = {ψ̂_{i,j}}. It is easy to see that φ̂(ŴΨ̂) = (W̃′)Ψ̃′ for some W̃′ = {W̃′_{i}}_{i=1}^{s} with W̃′_{i} ≤ Mat_{(V′_{i})^{m}} and Ψ̃′ = {ψ̃′_{i,j}}_{i,j=1}^{m} with ψ̃′_{i,j} ∈ Isow(W̃′_{i}, W̃′_{j}). Moreover, φ̂ takes Ŵ^{G} to (W̃′)^{G} so that condition (25) is satisfied. So Ŵ′_{U′} = W̃′ ≀Ψ̃′ G and the weak isomorphism

φ̂_{U} : Ŵ ≀Ψ̂ G → W̃′ ≀Ψ̃′ G

is induced by some weak isomorphisms φ̃_{i} : Ŵ_{i} → W̃′_{i}, i ∈ [s]. It suffices to check that W̃′_{i} = Ŵ′_{i} and φ̃_{i} is an m-extension of φ_{i} for all i.

First we observe that φ̂(E) = E′ where E (resp. E′) is the adjacency matrix of the equivalence relation ⋃_{i=1}^{s} V_{i}^{m} × V_{i}^{m} (resp. ⋃_{i=1}^{s}(V′_{i})^{m} × (V′_{i})^{m}). So,

∑_{i} φ̃_{i}( ⨂_{j} A_{i}^{(j)}) = φ̂( ∑_{i} ⨂_{j} A_{i}^{(j)}) = φ̂(E ∘ ( ⨂_{j} ∑_{i} A_{i}^{(j)})) =

φ̂(E)∘φ̂( ⨂_{j} ∑_{i} A_{i}^{(j)}) = E′∘( ⨂_{j} φ(∑_{i} A_{i}^{(j)})) = E′∘( ⨂_{j} ∑_{i} φ(A_{i}^{(j)})) = ∑_{i} ⨂_{j} φ_{i}(A_{i}^{(j)})

where i runs over [s], j runs over [m] and A_{i}^{(j)} ∈ W_{i} with ∑_{i} A_{i}^{(j)} ∈ W^{Ψ} for all j. Thus φ̃_{i}(A) = φ_{i}^{m}(A) for all A ∈ W_{i}^{m} and all i ∈ [s]. Finally,

∑_{i=1}^{s} φ̃_{i}(I_{Δ_{i}}) = φ(I_{Δ}) = I_{Δ′} = ∑_{i=1}^{s} I_{Δ′_{i}}

where Δ_{i} (resp. Δ′_{i}) is the diagonal of V_{i}^{m} (resp. (V′_{i})^{m}). So φ̃_{i}(I_{Δ_{i}}) = I_{Δ′_{i}} for all i. Therefore, W̃′_{i} = [(W′_{i})^{m}, I_{Δ′}] = Ŵ′_{i} and φ̃_{i} is an m-extension of φ_{i} (see Theorem 3.2 and Definition 4.2).

Conversely, let φ_{i} ∈ Isow_{m}(W_{i}, W′_{i}) for all i ∈ [s]. Then the weak isomorphism from ⊞_{i=1}^{s} W_{i} to ⊞_{i=1}^{s} W′_{i} induced by φ_{i}’s is an m-isomorphism by Theorem 7.6. The m-extension of it takes I_{Δ} to I_{Δ′} and coincides with φ^{m} on W^{m} (we use Definition 4.2 and the fact that φ is induced by φ_{i}’s). Thus we are done by Theorem 3.2.

References

[1] C. Berge, Graphs and Hypergraphs, North-Holland Publ. Co., London, 1973.

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

[3] J. Cai, M. Fürer, N. Immerman, Optimal lower bound on the number of variables for graph identification, Combinatorica 12 (1992), 389–410.

[4] S. A. Evdokimov, M. Karpinski, I. N. Ponomarenko, On a New High Dimensional Weisfeiler-Lehman Algorithm, (accepted to J. of Algebraic Combinatorics).

[5] S. A. Evdokimov, I. N. Ponomarenko, On primitive cellular algebras, to appear in Zapiski Nauchnykh Seminarov POMI, 256 (1999).

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

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

[8] S. Friedland, Coherent algebras and the graph isomorphism problem, Discrete Appl. Math., 25 (1989), 73–98.

[9] M. D. Hestens, D. G. Higman, Rank 3 groups and strongly regular graphs, SIAM-AMS Proc., 4 (1971), 141–159.

[10] D. G. Higman, Coherent algebras, Linear Algebra Appl., 93 (1987), 209–239.

[11] G. Ivanyos, On the combinatorics of Evdokimov’s deterministic factorization method, Preprint, 1997.

[12] F. Lazebnik, V. A. Ustimenko, A. J. Woldar, A characterization of the components of the graphs D(k, q), Discrete Math., 157 (1996), 271–283.

[13] J. D. H. Smith, Association schemes, superschemes, and the relation invariant under permutation groups, European J. Combin., 15 (1994), 285–291.

[14] V. A. Ustimenko, Coordinates of Trees and their Quotients, in “Voronoj’s Impact in Modern Science”, Kiev, Institute of Mathematics, 2 (1998), 125–152.

[15] M. Watkins, Connectivity of transitive graphs, J. Combin. Theory, 8 (1970), 23–29.

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

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

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