arXiv:1704.00990v2 [math.CO] 7 Apr 2017

TESTING ISOMORPHISM OF CENTRAL CAYLEY GRAPHS
OVER ALMOST SIMPLE GROUPS IN POLYNOMIAL TIME
ILIA PONOMARENKO AND ANDREY VASIL’EV
In memory of Sergei Evdokimov
Abstract. A Cayley graph over a group G is said to be central if its connection set is a normal subset of G. It is proved that for any two central
Cayley graphs over explicitly given almost simple groups of order n, the set
of all isomorphisms from the first graph onto the second can be found in time
poly(n).

1. Introduction
In the present paper, we are interested in a special case of the following restriction
of the Graph Isomorphism Problem to the class of Cayley graphs.
Cayley Graph Isomorphism Problem. For two explicitly given finite groups
G and G′ and two sets X ⊂ G and X ′ ⊂ G′ , construct the set Iso(Γ, Γ′ ), where
Γ = Cay(G, X) and Γ′ = Cay(G, X ′ ).
Here the input consists of the multiplication tables of G and G′ and the sets
X and X ′ , whereas the output is either empty or given by an element of the
set Iso(Γ, Γ′ ) and a generating set of the group Aut(Γ) (of size polynomial in the
order n of the group G). Obviously, the Luks algorithm [12] solves the Cayley
Graph Isomorphism Problem in polynomial time for every group G, whenever the
set X is of constant sizes. If G is cyclic, then the problem with no restriction for X
is also solvable in polynomial time (see [6] and [13]). It should be noted that if
G = G′ and G is a so-called CI-group, then an obvious algorithm solves the Cayley
Graph Isomorphism Problem in time polynomial in | Aut(G)| (for details, see [10]).

The aforementioned special case is formed by the two following conditions imposed on the input graphs and groups. First, we assume that Γ is a central Cayley
graph over G, which means that X is a normal subset of G, i.e., X g = X for every
g ∈ G. Second, the group G is assumed to be almost simple, i.e., the socle of G
is a nonabelian simple group. The same conditions are imposed on the graph Γ′
and group G′ . Even in this rather restrictive case, the problem is still nontrivial;
at least the number of possible input graphs is exponential in n.
Example. Let G = Sym(m) be a symmetric group of degree m. Then the
number N (m) of central colored Cayley graphs over G is equal to 2p(m) , where p(m)
is the number
of all partitions of the set {1, . . . m}. Since p(m) is approximately
√
equal to 2 m , the number N (m) is exponential in n = m!.
By technical reasons, it is more convenient to deal with colored Cayley graphs.
Such a graph is given by a partition P of the group G into k ≥ 2 classes X0 , . . . , Xk−1
with X0 = {1}, and can be thought as arc-colored complete graph with vertex set
1

2

ILIA PONOMARENKO AND ANDREY VASIL’EV

G and the ith color class of arcs coinciding with the arc set of the Cayley graph
Cay(G, Xi ), i = 0, . . . , k − 1. We say that P is the Cayley partition of this graph
and denote the latter by Cay(G, P). In what follows, all Cayley graphs are assumed
to be colored: the graph Cay(G, X) is treated as Cay(G, P) for k = 3 and X1 = X.
Theorem 1.1. For any two central Cayley graphs Γ and Γ′ over explicitly given
almost simple groups G and G′ of order n, the set Iso(Γ, Γ′ ) can be found in time
poly(n).
Corollary 1.2. The automorphism group of a central Cayley graph over an explicitly given almost simple group of order n can be found in time poly(n).
The proof of Theorem 1.1 is a mix of combinatorial and permutation group
techniques. Section 2 provides a relevant background for the combinatorial part
including coherent configurations and Cayley schemes. In Section 3, we use a
classification of regular almost simple subgroups of primitive groups [11] to prove
(Lemma 3.2) that except for one special case, if K ≤ Sym(G) is a 2-closed primitive
group containing regular almost simple subgroup, then
(1)

K = Sym(G)

or K ≤ D(2, G),

where D(2, G) is the subgroup of Sym(G) generated by the holomorph of G and
the permutation σ : g 7→ g −1 , g ∈ G. We extend this result to non-primitive groups
in Sections 4 and 5 by showing that in this case, either formula (1) holds or K is a
nontrivial generalized wreath product (Theorems 4.1 and 5.1). We apply this fact
in Section 6 to the automorphism group K of a central Cayley graph Γ over the
group G to establish that
(2)

K S = Sym(S) or K S ≤ D(2, S),

where S = Soc(G) is the socle of G and K S is the restriction to S of the setwise
stabilizer of S in K. Note that if G is a symmetric group of degree at least 5, then
the group D(2, G) is isomorphic to the group G ≀ Sym(2). Thus as a byproduct
of (2), we obtain the following generalization of the result [9, Theorem 1.1] on the
automorphism group of the Cayley graph Cay(G, X), where G is a symmetric group
and X is the set of its transpositions.
Theorem 1.3. Let G be a symmetric group of degree at least 5, X a proper normal
subset of G \ Soc(G), and Γ = Cay(G, X). Then Aut(Γ) = D(2, G).
In Sections 7 and 8, we develop algorithmic tools to find the above structure of
the group K with the help of the related Cayley scheme and the group G. The
main algorithm providing the proof of Theorem 1.1 is given in Section 9.
Notation.
The diagonal of the Cartesian product Ω × Ω is denoted by 1Ω .
For s ⊆ Ω × Ω, set s∗ = {(β, α) : (α, β) ∈ s}.
For α ∈ Ω and s ⊆ Ω × Ω, set αs = {β ∈ Ω : (α, β) ∈ s}.
For ∆ ⊆ Ω and s ⊆ Ω × Ω, set s∆ = s ∩ (∆ × ∆).
For a partition E of a set Ω and s ⊆ Ω × Ω, set sE to be the relation consisting
of the pairs (∆, ∆′ ) ∈ E × E such that s meets ∆ × ∆′ .
For a set S of binary relations, put S ∪ to be the set of all unions of relations
from S.
The symmetric and alternating groups on Ω are denoted by Sym(Ω) and Alt(Ω),
respectively.

TESTING ISOMORPHISM OF CENTRAL CAYLEY GRAPHS

3

For f ∈ Sym(Ω) and s ⊆ Ω × Ω, set sf = {(αf , β f ) : (α, β) ∈ s}.
For a group G and its subgroup L, set Llef t and Lright to be the subgroups
of Sym(G) induced by left and right multiplications of L, respectively, and L∗ =
Llef t Lright .
For a group G, set D(2, G) to be the subgroup of Sym(G) generated by the group
Hol(G) = NSym(G) (Gright ) and the permutation σ : g 7→ g −1 .
For a group K ≤ Sym(G) and a set H ⊆ G, the restriction to H of the setwise
stabilizer of H in K is denoted by K H .
For an imprimitivity system L of a transitive group K, set KL and K L to be,
respectively, the intersection of all K H with H ∈ L and the permutation group
induced by the action of K on L.
For a group G and a permutation group K, set Reg(K, G) to be the set of all
regular subgroups of K that are isomorphic to G.
2. Coherent configurations and Cayley schemes
This section contains well-known basic facts on coherent configurations. All of
them can be found in [7] and papers cited there.
2.1. Main definitions. Let Ω be a finite set and S a partition of Ω × Ω. The pair
X = (Ω, S) is called a coherent configuration on Ω if the following conditions hold:
(C1) 1Ω ∈ S ∪ ,
(C2) S ∗ = S,
(C3) given r, s, t ∈ S, the number ctrs = |αr ∩ βs∗ | does not depend on the choice
of the pair (α, β) ∈ t.

The elements of Ω and S, and the numbers ctrs are called the points and basis
relations, and the intersection numbers of X , respectively. The numbers |Ω| and
|S| are called the degree and the rank of X . The coherent configuration X is said
to be homogeneous if 1Ω ∈ S.
Denote by Φ = Φ(X ) the set of Λ ⊆ Ω such that 1Λ ∈ S. The elements of Φ are
called the fibers of X . In view of condition (C1), the set Ω is the disjoint union of all
of them. Moreover, for each s ∈ S, there exist uniquely determined fibers Λ and ∆
such that s ⊆ Λ × ∆. Note that the coherent configuration X is homogeneous if
and only if |Φ| = 1.
Let e ∈ S ∪ be an equivalence relation and E the set of its classes. Given ∆ ∈ E
denote by S∆ the set of all nonempty relations s∆ with s ∈ S. Then the pair
X∆ = (∆, S∆ )
is a coherent configuration called the restriction of X to ∆. This enables to define
the restriction of X to a set Λ ∈ Φ∪ : the corresponding equivalence relation is
equal to the union of ∆ × ∆, where ∆ runs over the fibers contained in Λ. Another
coherent configuration associated with e is obtained as follows. Denote by SE the
set of all nonempty relations sE , s ∈ S. Then
XE = (E, SE )
is a coherent configuration called the quotient of X modulo e.

4

ILIA PONOMARENKO AND ANDREY VASIL’EV

2.2. Combinatorial and algebraic isomorphisms. A bijection f : Ω → Ω′
is called the (combinatorial) isomorphism from X onto a coherent configuration
X ′ = (Ω′ , S ′ ) if the set S ′ contains the relation sf for each s ∈ S. The set of all
isomorphisms f is denoted by Iso(X , X ′ ). The group of all isomorphisms of X to
itself contains a normal subgroup
Aut(X ) = {f ∈ Sym(Ω) : sf = s, s ∈ S}

called the automorphism group of X . Conversely, let G ≤ Sym(Ω) be a permutation
group, and let S be the set of orbits of the component-wise action of G on Ω × Ω.
Then the pair X = (Ω, S) is a coherent configuration; we say that X is associated
with G and denote it by Inv(G).
According to Wielandt [17], a permutation group G on Ω is said to be 2-closed
if it is equal to its 2-closure
G(2) = Aut(Inv(G)),
or, equivalently, if G is an automorphism group of a family of binary relations
on Ω (such a family can always be chosen as the set of basis relations of a coherent
configuration on Ω). If G is 2-closed and L is an imprimitivity system of G, then
the group GL is 2-closed. However, the group GL is not always 2-closed.
A bijection ϕ : S → S ′ , r 7→ r′ is called an algebraic isomorphism from X
onto X ′ if
′

ctrs = ctr′ s′ ,

(3)

′

r, s, t ∈ S.

In this case, X and X are said to be algebraically isomorphic. Each isomorphism f
from X onto X ′ induces an algebraic isomorphism ϕf : r 7→ rf between these
configurations. The set of all isomorphisms inducing the algebraic isomorphism ϕ
is denoted by Iso(X , X ′ , ϕ). In particular,
(4)

Iso(X , X , idS ) = Aut(X ),

where idS is the identity mapping on S.

An algebraic isomorphism ϕ induces a bijection from S ∪ onto (S ′ )∪ : the union
r∪s∪· · · of basis relations of X is taken to r′ ∪s′ ∪· · · . This bijection is also denoted
by ϕ. It preserves the equivalence relations e ∈ S ∪ ; moreover, the equivalence
relations e and ϕ(e) have the same number of classes as well as the same multiset
of their sizes. In this case, if E and E′ are the sets of classes of e and ϕ(e),
respectively, and ∆ ∈ E, then ϕ induces the algebraic isomorphisms
′
ϕ∆ : X∆ → X∆
′ , s 7→ ϕ(s)∆′

for a suitable ∆′ ∈ E′ .

and ϕE : XE → XE′ ′ , sE 7→ ϕ(s)E′

2.3. Direct sum and wreath product. Let X = (Ω, S) and X ′ = (Ω′ , S ′ ) be
coherent configurations. Denote by Ω ⊔ Ω′ the disjoint union of Ω and Ω′ , and by
S ⊞ S ′ the union of the set S ⊔ S ′ and the set of all relations ∆ × ∆′ and ∆′ × ∆
with ∆ ∈ Φ(X ) and ∆′ ∈ Φ(X ′ ). Then the pair
X ⊞ X ′ = (Ω ⊔ Ω′ , S ⊞ S ′ )

is a coherent configuration called the direct sum of X and X ′ . The automorphism
group of this configuration equals the direct product Aut(X ) × Aut(X ′ ) acting on
the set Ω⊔Ω′ . Furthermore, if ϕ is an algebraic isomorphism from X ⊞X ′ to another
coherent configuration, then the latter is also the direct sum Y ⊞ Y ′ and ϕ induces

TESTING ISOMORPHISM OF CENTRAL CAYLEY GRAPHS

5

algebraic isomorphisms X → Y and X ′ → Y ′ coinciding with the restrictions of ϕ
on Ω and Ω′ , respectively.
Let X be a homogeneous coherent configuration, e ∈ S ∪ an equivalence relation,
and E the set of classes of e. We say that X is the wreath product with respect to e
if for each s ∈ S such that s 6⊆ e,
[
Λ × ∆.
s=
(Λ,∆)∈sE

In what follows, we always assume that the classes of e can be identified with the
help of a family of the isomorphisms fΛ,∆ : XΛ → X∆ , Λ, ∆ ∈ E, such that
(5)

(sΛ )fΛ,∆ = s∆ ,

s ∈ S.

In this case, X is isomorphic to the usual wreath product X∆ ≀ XE for all ∆ ∈ E
(see [15, p.45]). The automorphism group of this coherent configuration is permutation isomorphic to the wreath product Aut(X∆ ) ≀ Aut(XE ) in imprimitive action.

Furthermore, if ϕ is an algebraic isomorphism from the wreath product X with
respect to e to another coherent configuration, then the latter is also the wreath
product X ′ with respect to e′ = ϕ(e) and ϕ induces algebraic isomorphisms X∆ →
′
′
X∆
′ and XE → XE′ coinciding with the restrictions of ϕ on ∆ and E, respectively,
′
where E is the set of classes of e′ and ∆′ ∈ E′ .
2.4. Cayley schemes. A coherent configuration X = (Ω, S) is called the Cayley
scheme over a group G if
Ω = G and Gright ≤ Aut(X ).

In this case, X is homogeneous and each basis relation s is the set of arcs of
Cayley graph Cay(G, X), where X is the neighborhood of the identity of G in
relation s. In particular, X can be treared as a color graph Cay(G, P), where
classes of the Cayley partition P are the neighborhoods of the identity of G in
basis relations of X .

the
the
the
the

The class of Cayley schemes is closed with respect to taking restrictions and
quotients. Namely, if X is a Cayley scheme over a group G and e ∈ S ∪ is an
equivalence relation, then the class H of e containing the identity of G is a subgroup
of G. Moreover, the set E of classes of e coincides with the right H-cosets of G. It
follows that
with

XH = Cay(H, EH ) and XE = Cay(G/H, EG/H ),

EH = {X ∈ E : X ⊂ H} and EG/H = {π(X) : X ∈ E},
where in the latter case, H is a normal subgroup of G and π : G → G/H is the
canonical epimorphism.
Assume that the Cayley scheme X is the wreath product with respect to an
equivalence relation e ∈ S ∪ . Then for any two classes Λ, ∆ ∈ E, there exists a
permutation f ∈ Gright taking Λ to ∆; set fΛ,∆ to be the restriction of f to Λ. Since
all these f are automorphisms of X , the family {fΛ,∆ }Λ,∆∈E satisfies conditions (5).

The Cayley scheme X is said to be central if Glef t ≤ Aut(X ) which is by definition of a Cayley scheme is equivalent to G∗ ≤ Aut(X ). One can see that X is
central if and only if the colored Cayley graph associated with X is central.

6

ILIA PONOMARENKO AND ANDREY VASIL’EV

2.5. Partial order and the WL-algorithm. There is a natural partial order ≤
on the set of all coherent configurations on the same set Ω. Namely, given two
coherent configurations X = (Ω, S) and X ′ = (Ω, S ′ ), we set
X ≤ X ′ ⇔ S ∪ ⊆ (S ′ )∪ .

The minimal and maximal elements with respect to this order are, respectively,
the trivial and discrete coherent configurations. The first one is a unique coherent
configuration TΩ with at most two basis relations: 1Ω and its complement to Ω×Ω (if
Ω consists of at least two points). Every basis relation of the discrete configuration
is a singleton. With respect to this order, the direct sum X ⊞ X ′ is the minimal
coherent configuration on Ω ⊔ Ω′ , the restrictions of which to Ω and Ω′ are equal
to X and X ′ , respectively.
One can prove that given a set T ⊆ 2Ω×Ω , there exists a unique minimal coherent
configuration X ′ such that every relation of T is the union of some basis relations
of X ′ . This coherent configuration is called the coherent closure of T and can
be constructed by the well-known Weisfeiler-Leman algorithm (WL-algorithm) [15,
Section B] in time polynomial in sizes of T and Ω. To stress this fact, the coherent
closure of T is denoted by WL(T ). For a color graph Γ with the set S of color
classes, we set
WL(Γ, T ) = WL(S ∪ T )

and write WL(Γ) instead of WL(Γ, ∅). It is important to note that the automorphism group of the coherent configuration WL(Γ, T ) is equal to the subgroup of
Aut(Γ) leaving each relation of T fixed (as a set). This implies that if Γ is a Cayley
graph over G, then the coherent configuration WL(Γ) is a Cayley scheme over G.
Since any coherent configuration X can be considered as a color graph, we extend
our notation to write WL(X , T ). Concerning the following statement, we refer
to [14, Theorem 2.4].
Theorem 2.1. Let S and S ′ be m-sets of binary relations on an n-element set.
Then given a bijection ψ : S → S ′ , one can check in time mnO(1) whether or not
there exists an algebraic isomorphism ϕ : WL(S) → WL(S ′ ) such that ϕ|S = ψ.
Moreover, if ϕ does exist, then it can be found within the same time.
3. Almost simple groups
In this section, we collect several known facts on finite almost simple groups and
deduce some auxiliary results to be used throughout the paper.
Lemma 3.1. Let G be an almost simple group of order n. Then
(i) |G/L| ≤ log n, where L = Soc(G),
(ii) | Reg(K, G)| = nO(1) for every K ≤ Sym(G) containing G as a normal
regular subgroup.
Proof. From the description of the automorphism groups of simple groups (see, e.g.,
[4, Introduction]), it follows that | Aut(L)/L| ≤ log |L|. Therefore, statement (i) is
a consequence of the inclusions L ≤ G ≤ Aut(G) ≤ Aut(L). The inclusions also
imply that | Aut(G)| ≤ n log n. Since the centralizer of G in Sym(G) is of order n
[16, Exercise 4.5’], we have
|K| ≤ |NSym(G) (G)| ≤ |CSym(G) (G)| · | Aut(G)| ≤ n2 log n.

TESTING ISOMORPHISM OF CENTRAL CAYLEY GRAPHS

7

On the other hand, the group G is 3-generated
 [5]. Thus, the number of regular
subgroups of K isomorphic to G is at most K

3 and statement (ii) follows.
In the following statement, we use the classification of regular almost simple
subgroups of a primitive group [11, Theorem 1.4].

Lemma 3.2. Let G be an almost simple group and G∗ ≤ K ≤ Sym(G). Suppose
that K is primitive. Then one of the following holds:
(i) K ≥ Alt(G),
(ii) G = Soc(G) and K ≤ D(2, G),
(iii) G = Sym(5) and K = Sp8 (2) is 2-transitive.
Proof. Without loss of generality, we assume that neither K ≥ Alt(G), nor G =
Soc(G) and K ≤ D(2, G). Then by aforementioned classification, exactly one of
the following pairs (G, Soc(K)) occurs:
(a) (Alt(p2 − 2), Alt(p2 + 1)), where p = 3 (mod 4) is prime,
(b) (Sym(p − 2), Alt(p)) or (Sym(p − 2), Alt(p + 1)), where p ≥ 7 is prime,
(c) the twelve pairs in the table below.
N o.
G
Soc(K)
1
Alt(5) L2 (59)
2
Alt(7) Alt(11)
3
Alt(7) Alt(12)
4
Sym(5) Alt(9)
5
Sym(5) Sp4 (4)
6
Sym(5) Sp6 (2)

N o.
G
Soc(K)
7
Sym(5)
Ω+
8 (2)
8
Sym(5) Sp8 (2)
9
L2 (16).4 Sp6 (4)
10 L2 (16).4 Ω+
8 (4)
11
L3 (4).2
M23
12
L3 (4).2
M24

The assumption G∗ ≤ K, in particular, implies that |G|2 ≤ |K|. By straightforward
check this excludes cases (a) with p > 3, (b) with p > 7, and cases 11 and 12 from
the table. Similarly, the remaining cases in (a) and (b) as well as cases 1–4, and 9
are impossible because |G|2 must divide |K|.
In cases 5, 6, 7, and 10 from the table, we check the maximal subgroups of K and
show that none of them includes the subgroup isomorphic to G∗ . Indeed, in cases 5
and 6 none of the maximal subgroups contains Alt(5) × Alt(5) [2, Tables 8.14, 8.28,
8.29]. In case 10, information from [11, Table 2] shows that K is an extension of
Ω+
8 (4) by a field automorphism. This group contains the only (up-to conjugation)
maximal subgroup with section isomorphic to L2 (16) × L2 (16) [2, Table 8.50], but
the order of this subgroup is less than |G∗ |. In case 7, we make use of [11, Table 2]
to see that K = Ω+
8 (2). Again this group includes up to conjugation the only
maximal subgroup M with section isomorphic to Alt(5)×Alt(5) (see [2, Table 8.50]).
However, |M | = |G∗ | but M ≃ D(2, Alt(5)) is not isomorphic to G∗ ≃ Sym(5) ×
Sym(5).
This leaves us with case 8 of the table where Soc(K) = Sp8 (2) = K and we
arrive at case (iii) of the conclusion of the lemma.


8

ILIA PONOMARENKO AND ANDREY VASIL’EV

4. The structure of automorphism groups: the principal section
4.1. Preliminaries. Let G be a finite group. The automorphism group of every
central Cayley graph over G contains a subgroup G∗ (see Notation). In this section,
we establish some basic facts on the permutation groups K satisfying the following
condition:
(6)

G∗ ≤ K ≤ Sym(G),

where G is an almost simple group. We use a concept of the generalized wreath
product of permutation groups introduced and studied in [8]. Namely, a transitive
group K is the generalized wreath product if it has two imprimitivity systems L
and U such that every block of L is contained in a block of U and
Y
KL =
(KL )X .
X∈U

The generalized wreath product is said to be trivial if either L consists of singletons
or U = {Ω}. When L = U, the group K is permutation isomorphic to the wreath
product K X ≀ K L in imprimitive action, where X ∈ U.
Theorem 4.1. Let G be an almost simple group, and let K be a 2-closed group
satisfying condition (6). Then one of the following statements holds:
(i) K = Sym(G) or G∗ E K,
(ii) K is a nontrivial generalized wreath product.
The proof of Theorem 4.1 is given in the end of Section 6.
4.2. The minimal block. Let K satisfy condition (6) and X a K-block containing
the identity of G. Since K is a permutation group on G that includes Gright , the
block X is a subgroup of G [16, Theorem 24.12]. Taking into account that Glef t
also lies in K, we conclude that X is normal. Denote by L the intersection of all
non-singleton K-blocks containing the identity of the group G. Then L is a K-block
and we call it the minimal block of K.
Lemma 4.2. Let K satisfy condition (6) and L the minimal block of K. Then
L is normal subgroup of G including Soc(G). In particular, L is an almost simple
group such that Soc(L) = Soc(G).
Proof. According to the above remark, every K-block containing the identity of G is
a normal subgroup of G. If the block is not a singleton, then this normal subgroup
is nontrivial and hence contains Soc(G), because the group G is almost simple.
Thus, the minimal block L being the intersection of nontrivial normal subgroups
of G is a normal subgroup and contains Soc(G).

Denote by L the imprimitivity system containing L. Obviously,
Orb(L∗ , G) = L.
Recall that according to the definition, KL is a normal subgroup of K leaving each
block of L fixed (as a set), and given X ∈ L, the group (L∗ )X ≤ Sym(X) is induced
by right multiplications of L.
Lemma 4.3. For any X ∈ L, the group (KL )X is primitive and contains (L∗ )X .

TESTING ISOMORPHISM OF CENTRAL CAYLEY GRAPHS

9

Proof. The normality of L in G implies that the orbits of the action of L∗ on G
coincide with the L-cosets. It follows that the permutation group induced by this
action is contained in KL . This proves the second statement. To prove the first
statement, in view of the transitivity of K, we may assume that X = L.
Assume on the contrary that the group K ′ = (KL )L is not primitive. Then
there exists a minimal non-singleton K ′ -block L′ < L. Taking into account that
K ′ E K L , we conclude that L′′ = (L′ )k is a also K ′ -block for every k ∈ K [16,
Proposition 6.2]. The imprimitivity system L′ of the group K ′ that contains L′
coincides with the imprimitivity system containing L′′ , for otherwise by the minimality of L′ and Lemma 4.2 applied for the group K ′ , one can choose the block L′′
so that
1 = L′ ∩ L′′ ⊇ Soc(L) = Soc(G) ) 1,

a contradiction. Thus, L′ is an imprimitivity system of the group K L . Consequently, L′ is a non-singleton K-block strictly contained in L, which is impossible
by the definition of L.

4.3. The wreath decomposition of KL . For every two sets X, X ′ ∈ L, we write
X ∼ X ′ if the restriction epimorphisms
(7)

′

(KL )X∪X → (KL )X

′

and (KL )X∪X → (KL )X

′

′

are isomorphisms. In particular, the groups (KL )X and (KL )X are isomorphic. It
is easily seen that ∼ is an equivalence relation on L. This relation is K-invariant,
because KL is a normal subgroup of K. Denote by U the union of L-cosets belonging
to the class of ∼ that contains L. Then U is obviously a K-block and hence is a
normal subgroup of G. Thus,
L E U E G.
The imprimitivity system of the group K that contains the block U is denoted by U.
We say that U/L is the principal K-section of G, and U and L are the associated
partitions.
Theorem 4.4. Let G be an almost simple group, K a 2-closed group satisfying
condition (6), and U, L are the partitions associated with the principal K-section.
Then the coherent configuration Inv(KL ) is the direct sum of the coherent configurations Inv(KL )Y , where Y ∈ U. In particular,
Y
(8)
KL =
(KL )Y ,
Y ∈U

i.e., K is generalized wreath product.
Proof. The subgroup KL of 2-closed group K is 2-closed too (see Subsection 2.2).
Therefore, equality (8) follows from the first statement of the theorem, because the
automorphism group of the direct sum equals the direct product of the summands
(see Subsection 2.3). To prove the first statement, it suffices to verify that given
X, X ′ ∈ Orb(KL , G),
(9)

X 6∼ X ′

⇒

X × X ′ ∈ Orb(KL , X × X ′ ).
′

To this end, we note that the group (KL )X∪X is the subdirect product of the
′
transitive constituents M = (KL )X and M ′ = (KL )X . Therefore, there exist

10

ILIA PONOMARENKO AND ANDREY VASIL’EV

uniquely determined normal subgroups H and H ′ of M and M ′ , respectively, and
a group isomorphism ϕ : M/H → M ′ /H ′ such that
(10)

′

(KL )X∪X = {(k, k ′ ) ∈ M × M ′ : ϕ(k) = k ′ }.

Now if X 6∼ X ′ , then at least one of the epimorphisms (7) is not an isomorphism.
Therefore, one of the groups H and H ′ , say H, is nontrivial. It follows that H
being a normal subgroup of the primitive group M (Lemma 4.3) acts transitively
′
on X. By (10), this implies that (KL )X∪X contains the subgroup H × 1. Thus,
(x, x′ )H×1 = X × {x′ }
′

for all x′ ∈ X ′ and hence the group (KL )X∪X is transitive on the set X × X ′ . 
5. The normalizer of Soc(G)∗ in Sym(G)
The goal of this section is to prove the following theorem that shows (as we will
see) that the case U = G is very similar to the case where the group K is primitive.
Theorem 5.1. Let G be an almost simple group, S = Soc(G), and N = NSym(G) (S ∗ ).
Then
(11)

N = D(2, G).

Clearly, N is a proper subgroup of Sym(G) and condition (6) is satisfied for
K = N . In particular, the minimal block of N coincides with S.
Lemma 5.2. In the above notation, CSym(G) (S ∗ ) = 1.
Proof. Set C = CSym(G) (S ∗ ). Then obviously, C = CN (S ∗ ). Since N is transitive
and C is normal in N , the orbits of C form an imprimitivity system of N . Denote
by X the block of this system that contains the identity of G. We may assume
that the block X is not a singleton, for otherwise C = 1 and we are done. Then
S ⊆ X, because S is the minimal N -block. Since C is transitive on X and S is a
block of C X , there exists c ∈ C such that S c = S and cS 6= 1. However, the latter
is impossible, because cS centralizes the subgroups Slef t and Sright .

Proof of Theorem 5.1. By Lemma 5.2, there exists a monomorphism from
N = NSym(G) (S ∗ ) to Aut(S ∗ ). Since the latter is isomorphic to the wreath product
W = Aut(S) ≀ Sym(2), this monomorphism induces a monomorphism
ϕ : N → W.

Clearly, ϕ can be chosen so that the subgroups Slef t and Sright of the group N
go to the subgroup Inn(S) × 1 of the group A = Aut(S) × 1 and to the subgroup
1 × Inn(S) of the group B = 1 × Aut(S), respectively. Set
W1 = im(ϕ)

and W0 = im(ϕ) ∩ (A × B).

Then since the index of A × B in W equals 2 and W1 is not contained in A × B,
we conclude that
(12)

|W1 : W0 | = 2.

Note that the centralizer of the group ϕ(Sright ) ≤ B in the group W0 is contained in
A, because the group B is almost simple with the socle ϕ(Sright ). Since the group
Glef t ≤ N centralizes Sright , this proves the first of the two following inclusions
(the second one can be proved in a similar way):
ϕ(Glef t ) ≤ A and ϕ(Gright ) ≤ B.

TESTING ISOMORPHISM OF CENTRAL CAYLEY GRAPHS

11

The first inclusion implies that ϕ(Glef t ) ≤ W0 ∩ A. The reverse inclusion follows from the fact that the centralizer of Glef t in Sym(G) is equal to Gright [16,
Proposition 4.3]. Thus, we obtain the equalities:
(13)

ϕ(Glef t ) = W0 ∩ A and ϕ(Gright ) = W0 ∩ B.

This immediately implies that ϕ(Glef t ) and ϕ(Gright ) are normal in W0 . This
group has trivial center and hence can be identified with a subgroup of the direct
product of the groups A′ = Aut(ϕ(Glef t )) and B ′ = Aut(ϕ(Gright )) (isomorphic to
Aut(G)). It follows that
′

′

′

W 0 = W0 /ϕ(G∗ ) ≤ A × B ,
′

where A = A′ /ϕ(Glef t ) and B = B ′ /ϕ(Gright ). Moreover in view of formulas (13),
′
′
the group W 0 intersects each of the groups A and B trivially. Therefore,
(14)

|W 0 | = | Aut(G)/G|.

Now, the inclusion ϕ(Aut(G)) ≤ W0 and formula (14) show that W0 = ϕ(Hol(G)).
Formula (12) yields that |N : Hol(G)| = 2. Since the permutation σ : g 7→ g −1 lies
in N , formula (11) holds.

6. Symmetric and normal types of the automorphism group
Let G be an almost simple group, K be a 2-closed group satisfying condition (6), and U/L the principal K-section of G. Then the group L is almost simple
(Lemma 4.2) and K L is primitive (Lemma 4.3). We say that K is of symmetric
type if either K L ≥ Alt(L), or G = Sym(5) and K = Sp8 (2) is 2-transitive; if
L = Soc(L) and K L ≤ D(2, L), the group K is said to be of normal type. The
following statement is a straightforward consequence of Lemma 3.2 and the above
definitions.
Proposition 6.1. Let G be an almost simple group, and let K ≤ Sym(G) be a
2-closed group containing G∗ . Then K is of symmetric or normal type.
Let us study a group of symmetric and normal types in detail. As the following
statement shows, any group of symmetric type is, in fact, the wreath product in
imprimitive action. In what follows, U and L are the partitions associated with the
principal K-section of G.
Theorem 6.2. Let K be a group of symmetric type. Then
L=U

and

(KL )L = Sym(L).

In particular, K is permutation isomorphic to the wreath product Sym(L) ≀ K L in
imprimitive action.
Proof. Let X, X ′ ∈ L and X ∼ X ′ . We claim that there exists a bijection f : X →
X ′ , for which
(15)

sf ∈ Orb(KL , X × X ′ ),

where sf = {(α, αf ) : α ∈ X} is the graph of f . Indeed, consider the group
′
M = (KL )X∪X . Since X ∼ X ′ , the group M acts faithfully on X and X ′ . As the
group K is of symmetric type, each of these actions is 2-transitive. However, M
has a unique faithful 2-transitive representation of degree d = |X|: this is obvious if
M ≥ Alt(d) and follows from the classification of 2-transitive groups if M = Sp8 (2)

12

ILIA PONOMARENKO AND ANDREY VASIL’EV

(see, e.g., [3, Table 7.4]). Consequently, among 2d point stabilizers Mβ , β ∈ X ∪X ′ ,
there are exactly d distinct, and also Mβ 6= Mγ whenever β and γ are distinct points
in X. Therefore, for every α ∈ X there is the only α′ ∈ X ′ such that
Mα = Mα′ = Mα,α′ .
Thus, the required bijection f takes α to α′ .
To prove that L = U, assume on the contrary that U contains a block X ∈ L
other than L. Denote by f : L → X the bijection defined in the above claim for
X = L and X ′ = X. Then by the assumption, the element f (1), where 1 is the
identity of the group G, does not belong to L. The binary relation sf is invariant
with respect to the group KL ≥ L∗ and hence for all x ∈ L,
(x, f (1)x) = (1, f (1))xr = (x, f (x)) = (1, f (1))xl = (x, xf (1)),

where xr and xl are the permutations of L∗ induced by the right and left multiplication by x. This implies that the element f (1) ∈ X ⊂ U centralizes L. However,
this is impossible, because f (1) 6= 1 and the group U is almost simple.
Let us prove the second equality. The 2-closedness of K implies that KL is
2-closed. Furthermore, in view of the 2-transitivity of the group (KL )X its the
2-closure equals Sym(X). By Theorem 4.4 and equality L = U, this implies that
Y
Y
Y
KL = (KL )(2) = (
(KL )X )(2) =
((KL )X )(2) =
Sym(X).
X∈L

X

Thus, (KL )

X∈L

= Sym(X) for all X ∈ L and we are done.

X∈L


U

Theorem 6.2 shows that in the case of symmetric type, the group K = Sym(U )
is the largest possible. In the normal type case, the group K U is quite small. More
exactly, the following statement holds.
Theorem 6.3. Let K be a group of normal type. Then K U ≤ D(2, U ).
Proof. By the hypothesis of the theorem, L = Soc(L) and K L ≤ D(2, L). By
Lemma 4.2, the first equality implies that L = Soc(G) and hence
(16)

L = Soc(U ).

The second inclusion implies that (L∗ )X is a characteristic subgroup of the group
(KL )X for all X ∈ L. By the definition of U , this implies that (L∗ )U is a characteristic subgroup of the group (KL )U . However, the latter group is normal in K U .
Thus,
(L∗ )U E K U .
It follows that K U is contained in the normalizer of (L∗ )U in Sym(U ). However,
this normalizer is contained in D(2, U ) by Theorem 5.1 applied for G = U with
taking into account equality (16).

Proof of Theorem 4.1. Let U/L be the principal K-section of the group G.
By Proposition 6.1, the group K is of symmetric or normal type. Suppose first that
U = G. Then statement (i) of Theorem 4.1 holds. Indeed, if K is of symmetric
type, then K = Sym(G) (Theorem 6.2), whereas if K is of normal type, then
K ≤ D(2, G) (Theorem 6.3) and the required statement follows from the fact that
G∗ is normal in D(2, G). Finally, if U < G, then statement (ii) of Theorem 4.1
holds by Theorem 4.4.


TESTING ISOMORPHISM OF CENTRAL CAYLEY GRAPHS

13

Proof of Theorem 1.3. First, assume that the group K = Aut(Γ) is a nontrivial generalized wreath product. Note that S = Soc(G) is a unique proper normal
subgroup in G and |G/S| = 2. Therefore the generalized wreath product must be a
usual one and the group K is permutation isomorphic to the wreath product M ≀ C2
in imprimitive action for some group M ≤ Sym(S). It follows that G \ S is an orbit
of the point stabilizer Kα , where α is the identity of G. Since X ⊂ G \ S is a union
of some orbits of Kα , we conclude that X = G \ S, a contradiction.
The group K is 2-closed as the automorphism group of a graph. The normality
of X implies that K satisfies condition (6) with G = Sym(m) for m ≥ 5. Finally, K
is not a nontrivial generalized wreath product by above, and K 6= Sym(G), because
the graph Γ is neither complete nor empty. Thus, by Theorem 4.1, the group G∗
is normal in K and
G∗ ≤ K ≤ D(2, G),
hence K = G∗ or K = D(2, G), because |D(2, G) : G∗ | = 2. However, since X is
a normal subset of a symmetric group, we have X = X −1 , so the graph Γ has the
automorphism σ : g 7→ g −1 , g ∈ G. Thus, K = hG∗ , σi = D(2, G), as required. 
7. Finding the principal section in a Cayley scheme
7.1. The main resut. Let X be a central Cayley scheme over an almost simple
group G. Then the group K = Aut(X ) is 2-closed and satisfies condition (6).
Therefore, K is of symmetric or normal type by Proposition 6.1. In this section,
we develop an algorithmic technique to determine (with no K in hand) which of
these cases occurs for the scheme X . The main result here is Theorem 7.1 below
which immediately follows from Corollaries 7.3 and 7.5 proved in Subsections 7.2
and 7.3, respectively.
Theorem 7.1. Given a central Cayley scheme X over an almost simple group G
of order n, one can determine the type of K = Aut(X ) and find the principal
K-section of G in time poly(n).
7.2. The case of symmetric type. For a group H ≤ G, denote by H and
WL(X , H) the partition of G into the right H-cosets and the Cayley scheme WL(X , T )
with T = {1X : X ∈ H}, respectively. Recall that TX is the trivial coherent configuration on X. Denote by H0 the set of groups H such that Soc(G) ≤ H ≤ G
and
(17)

WL(X , H) = ⊞ TX .
X∈H

Lemma 7.2. In the above notation, the following statements hold:
(i) if the group K is of symmetric type, then the set H0 is nonempty and the
minimal block L of K is the largest (by inclusion) element of H0 ,
(ii) K is of symmetric type if and only if H0 contains S = Soc(G),
Proof. To prove statement (i), assume that the group K is of symmetric type. Set
U and L to be the partitions associated with the principal K-section of G. Then by
Theorem 6.2, we have L = U and Inv(K X ) = TX for all X ∈ L. By Theorem 4.4,
this implies that
(18)

Inv(KL ) = ⊞ TX .
X∈L

14

ILIA PONOMARENKO AND ANDREY VASIL’EV

The minimality of the direct sum implies that WL(X , L) = Inv(KL ), which proves
formula (17) for H = L and H = L, in particular, H0 is nonempty. If L is not the
largest element of H0 , then there exists H ∈ H0 such that H \ L 6= ∅. It follows
that
K ≥ Sym(H) × idG\H ,
where idG\H is the identity subgroup of Sym(G \ H). Hence there is a permutation
k ∈ K that moves the identity of G to H \ L and leaves all non-identity elements
of L fixed. But this is impossible, because L is a K-block.
To prove the necessity for statement (ii), let K be of symmetric type. Then
formula (18) holds. Therefore, if S is the partition of G into the cosets of S, then
S refines L and hence
WL(X , S) = WL(WL(X , L), S) = ⊞ WL(TX , SX ) = ⊞ TX ,
X∈L

X∈S

where SX is the partition of X induced by S. Consequently, S ∈ H0 . Conversely,
assume on the contrary that K is of normal type. Then K U ≤ D(2, U ) by Theorem 6.3. Therefore K S ≤ Hol(S). On the other hand, since S ∈ H0 , we have
Sym(S) = K S ≤ Hol(S), a contradiction.


From statement (i) of Lemma 3.1, it follows that the number of groups H ≤ G
containing Soc(G) is at most log n, where n is the order of G; in particular, |H0 | ≤
log n. Moreover, for each H, the coherent configuration WL(X , H) can be efficiently
found by the WL-algorithm and condition (17) can be verified by checking at most
|H|2 ≤ n2 basis relations. Therefore, the set H0 can be found in time poly(n). By
statement (ii) of Lemma 7.2, this is enough to test efficiently whether or not K is of
symmetric type, and if it so, then to find the minimal block L = U of the group K
(statement (i) of the same lemma).
Corollary 7.3. Given a central Cayley scheme X over an almost simple group G
of order n, one can test in time poly(n) whether the group Aut(X ) is of symmetric
type, and (if so) find the principal section of Aut(X ) within the same time.

7.3. The case of normal type. In view of Corollary 7.3 and Proposition 6.1,
one can efficiently test whether the automorphism group K of a central Cayley
scheme X is of normal type. Denote by H1 the set of all groups H such that
Soc(G) ≤ H E G and
(19)

H ∗ × idG\H ≤ K,

where the left-hand side denotes the subgroup of Sym(G) that leaves each point of
G \ H fixed and coincides with H ∗ on H.
Lemma 7.4. Suppose that the group K is of normal type and U/L is the principal
K-section of G. Then L = Soc(G), the set H1 is nonempty, and U is the smallest
element of H1 .
Proof. Lemma 3.2 yields that L = Soc(G). From Theorem 4.4, it is easily follows
that U ∈ H1 . Assume on the contrary that the group U is not the smallest in H1 .
Then there is a group V ∈ H1 such that L ≤ U ∩ V < U . Take a non-identity
element w ∈ U ∩V and denote by kU (respectively, kV ) the permutation on G acting
on U (respectively, V ) by right multiplication by w and acting trivially outside U
(respectively, V ). Then kU , kV ∈ K, the permutation
k = kU kV−1

TESTING ISOMORPHISM OF CENTRAL CAYLEY GRAPHS

15

is not identity on U , and U k = U and k U∩V = idU∩V . Clearly, k U belongs
to K U , and hence to D(2, U ) because K is of normal type. However, as is easily
seen, the identity element is the only element of D(2, U ) that leaves all points of
L ≤ U ∩ V fixed, a contradiction.


Again from statement (i) of Lemma 3.1 it follows that the number of groups H
such that Soc(G) ≤ H E G is at most log n, and so is |H1 |. For every H and each
k ∈ H ∗ × idG\H one can efficiently test whether k is an automorphism of X . Thus,
Lemma 7.4 immediately implies the following statement.
Corollary 7.5. Given a central Cayley scheme X over an almost simple group G
of order n, one can test in time poly(n) whether the group Aut(X ) is of normal
type, and (if so) find the principal section of Aut(X ) within the same time.
8. A majorant for the coset of isomorphisms

Throughout this section, we assume that X is a central Cayley scheme over
an almost simple group G and K = Aut(X ). The principal K-section of G and
the associated partitions are denoted by U/L and U and L, respectively. The
equivalence relations corresponding to the partitions U and L, are denoted by eU
and eL . Let ϕ be an algebraic isomorphism from X onto a Cayley scheme X ′ over
an almost simple group G′ . Assume that
(20)

ϕ(eU ) = eU′

and ϕ(eL ) = eL′ ,

′

where in what follows, the group K , the principal section U ′ /L′ , the partitions U′
and L′ , and the equivalence relations eU′ and eL′ are defined for the scheme X ′ in
a similar way.
Lemma 8.1. In the above notation, |U| = |U′ | and |L| = |L′ |. Moreover, the groups
K and K ′ either both of symmetric type, or both of normal type.
Proof. The first statement follows from assumption (20). To prove the second one,
we note that by Lemma 7.2 the group K is of symmetric type if and only if the
scheme X is isomorphic to the wreath product TU ≀ Y, where Y is the quotient of X
modulo the equivalence relation eL . Since algebraic isomorphisms respect wreath
products, we are done.

For all Y ∈ U and Y ′ ∈ U′ , the algebraic isomorphism ϕ induces an algebraic
isomorphism
ϕY ,Y ′ : XY → XY′ ′ ,
that takes a relation sY to the relation s′Y ′ for all basis relations s ⊆ eU of the
scheme X , where s′ = ϕ(s). It follows that if X ′ = X and ϕ is trivial, then ϕY,Y is
trivial for all Y ∈ U.
For each Y ∈ U, set
(
Sym(Y )
DY =
D(2, U Y ) ∩ Aut(XY )

if K is of symmetric type,
otherwise,

where, for brevity, U Y denotes the restriction of the permutation group Uright to
the set Y . Note that the form of the group DY does not depend on Y ∈ U, and
DY contains K Y for all Y (Theorems 6.2 and 6.3). Furthermore, if Z ∈ U, then
any permutation of G∗ taking Y to Z induces a permutation isomorphism from the
group DY onto the group DZ .

16

ILIA PONOMARENKO AND ANDREY VASIL’EV

Lemma 8.2. (DY )f = DY f for all Y ∈ U and all f ∈ Iso(X , X ′ , ϕ).

Proof. Without loss of generality, we may assume that both K and K ′ are of normal
types (Lemma 8.1). Let Y ∈ U and f ∈ Iso(X , X ′ , ϕ). Then in view of (20),
Aut(XY )f = Aut(XY′ ′ ),

(21)

where Y ′ = Y f . Thus, it suffices to verify that D(2, V )f = D(2, V ′ ), where V = U Y
′
and V ′ = (U ′ )Y . However, by the definition of U, we have V = U g for suitable
g ∈ G and
D(2, V ) = D(2, U gr ),
where gr : U → V is the bijection induced by right multiplication by g. A similar
statement holds for V ′ , U ′ , and a suitable bijection (g ′ )r . Therefore, without loss
of generality, we may assume that Y = U and Y ′ = U ′ .
Recall that U is an almost simple group with Soc(U ) = L, and also U ∗ ≤ K U .
Therefore, Soc(K U ) = L∗ . The same is true with K, U , and L, replaced by K ′ , U ′ ,
′
and L′ , respectively. Taking into account that f takes K U to (K ′ )U , we conclude
that
(L∗ )f = (L′ )∗ .
This implies that f takes the normalizer of the group L∗ ≤ Sym(U ) to the normalizer of the group (L′ )∗ ≤ Sym(U ′ ). However by Theorem 5.1, these normalizers
are equal to D(2, U ) and D(2, U ′ ). Thus, f takes the first of these groups to the
second, and we are done.

Definition 8.3. Denote by Cϕ (X , X ′ ) the set of all bijections f : G → G′ taking
U to U′ and satisfying the following conditions for every Y ∈ U:
(22)

f Y ∈ Iso(XY , XY′ f , ϕY ,Y f )

and

(DY )f = DY f .

Let us find the explicit form of the set C = Cϕ (X , X ′ ) when X = X ′ and ϕ = id.
In this case, C is obviously a subgroup of Sym(G) preserving the partition U.
Condition (22) means that f Y belongs to the intersection of Aut(XY ) and the
normalizer of DY in Sym(Y ) for all f ∈ CU . This proves the first of the equalities
Y
DY = CU and C U = Sym(U);
Y ∈U

the second equality follows from the fact that any g ∈ G induces the permutation
isomorphism from DY onto DY g that induces ϕY ,Y g . Thus, the group C is permutation isomorphic to the wreath product DU ≀ Sym(U) (in imprimitive action). For
arbitrary X ′ and ϕ, an for each f ∈ Cϕ (X , X ′ ), we obviously have
(23)

Cϕ (X , X ′ ) = Cid (X , X )f.

Thus if the set Cϕ (X , X ′ ) is not empty, then it can be given by a generator set
of the group C = Cid (X , X ) and the bijection f . In the sense of the following
statement, the set Cϕ (X , X ′ ) can be called a majorant of Iso(X , X ′ , ϕ).
Theorem 8.4. Iso(X , X ′ , ϕ) ⊆ Cϕ (X , X ′ ). Moreover, the set Cϕ (X , X ′ ) can be
found in time poly(n).

Proof. The first statement immediately follows from Lemma 8.2. To prove the
second one, it suffices to find the set
C0 = {f0 ∈ Isoψ (XU , XU′ ′ ) : (DU )f0 = DU ′ },

TESTING ISOMORPHISM OF CENTRAL CAYLEY GRAPHS

17

where ψ = ϕU ,U ′ . Indeed, if this set is empty, then obviously so is the majorant
Cϕ (X , X ′ ). On the other hand, if f0 ∈ C0 , then to construct the majorant given
by formula (23) it suffices to find DU and the bijection f defined as follows:
f Y = (gY )−1 f0 gY′ ′ ,

Y ∈ U,

′

where Y 7→ Y is an arbitrary bijection from U onto U′ taking U to U ′ , and the
bijections gY : U → Y and gY′ ′ : U ′ → Y ′ are induced by the right multiplications
by the elements g ∈ G and g ′ ∈ G′ such that Y = U g and Y ′ = U ′ g ′ .
To find the sets DU and C0 , assume first that K is of symmetric type (recall that
this can efficiently checked by Theorem 7.1). Then the coherent configurations XU
and XU′ ′ are trivial. Thus, DU = Sym(U ) and for any bijection f0 : U → U ′ ,
C0 = Sym(U )f0 .
Let now K be of normal type. Then DU ≤ D(2, U ) and DU ′ ≤ D(2, U ′ ). In
particular, DU = D(2, U ) ∩ Aut(XU ) can be found in time poly(n). Furthermore,
every element f0 ∈ C0 takes DU to DU ′ (Lemma 8.2), and induces a permutation
group isomorphism from Uright onto a group
V ′ ∈ Reg(DU ′ , U ′ ).

By statement (ii) of Lemma 3.1, the set Reg(DU ′ , U ′ ) is of cardinality at most
|U ′ |c ≤ nc for some constant c > 0, and all its elements can be found by exhaustive
search of all 3-generated subgroups of the group DU ′ . Since for a fixed V ′ , there
are at most | Aut(V ′ )| ≤ nc distinct elements f0 ∈ C0 taking Uright to V ′ , one can
test in time poly(n), whether the set C0 is not empty and (if so) find it in the form
C0 = DU f0
with arbitrary f0 ∈ C0 .


9. Proof of Theorem 1.1

9.1. Reduction to Cayley schemes. Let Γ be a central Cayley graph over an
almost simple group G, {ei : i ∈ I} the set of color classes of Γ, and K = Aut(Γ).
The principal K-section of G and the associated partitions are denoted by U/L and
U and L, respectively. Set
X = WL(Γ, {eU , eL }),
where eU and eL are the equivalence relations corresponding to the partitions U
and L. For other central Cayley graphs Γ′ , we use similar notation, e.g., G′ and K ′
denote the underlying group and the automorphism group of Γ′ , respectively.
Lemma 9.1. Given central Cayley graphs Γ and Γ′ over almost simple groups G
and G′ , respectively, one can construct in time poly(n) the Cayley schemes X
and X ′ over the same underlying groups and check whether there exists a (unique)
algebraic isomorphism ϕ : X → X ′ such that
(24)

ϕ(ei ) = e′i for all i ∈ I

and

ϕ(eU ) = eU′ , ϕ(eL ) = eL′ ,

and (if so) find ϕ within the same time. Moreover, K = Aut(X ), K ′ = Aut(X ′ ),
and also
(25)

Iso(Γ, Γ′ ) = Iso(X , X ′ , ϕ).

18

ILIA PONOMARENKO AND ANDREY VASIL’EV

Proof. By Theorem 7.1, the principal sections and hence the equivalence relations
eU , eL and eU′ , eL′ can be found in time poly(n). Therefore the first part of the
statement immediately follows from Theorem 2.1. To prove the second one, we
observe that every f ∈ Iso(Γ, Γ′ ) takes the group K to the group K ′ . By the
definition of the minimal block (Subsection 4.2) this implies that f takes eL to
eL′ and hence takes eU to eU′ . Thus, the isomorphism f induces ϕ. This means
that f ∈ Iso(X , X ′ , ϕ) and hence the left-hand side of (25) is contained in the
right-hand side. Since the reverse inclusion is obvious, equality (25) is completely
proved. Next, if Γ′ = Γ, then ϕ = id and equality (25) shows that K = Aut(X ).
Similarly, K ′ = Aut(X ′ ).

9.2. Determining the coset of isomorphisms. Denote by π the canonical epimorphism from G onto G = G/L = L. Then π induces a map taking the set S of
basis relations of the Cayley scheme X over G to the set S of basis relations of the
∪
quotient Cayley scheme X over G. In particular, π takes S ∪ to S . Set Γ to be the
Cayley graph over G with color classes π(ei ), i ∈ I. For any set C of the bijections
f : G → G′ taking eU to eU′ and eL to eL′ , we denote by C the set of bijections
′
f : G → G induced by f ∈ C.
Theorem 9.2. Let Γ and Γ′ be central Cayley graphs over almost simple groups G
and G′ , respectively. Assume that the algebraic isomorphism ϕ from Theorem 9.1
does exist. Then
Iso(Γ, Γ′ ) = π −1 (C ∩ B),

(26)
′

where B = Iso(Γ, Γ ), C = Cϕ (X , X ′ ), and the right-hand side consists of all f ∈ C
for which f ∈ B.
Proof. To prove that that the left-hand side of (26) is contained in the right-hand
side, let f ∈ Iso(Γ, Γ′ ). Then the uniqueness of the principal sections implies that
(eU )f = eU′

and (eL )f = eL′ .

Therefore, the isomorphism f induces the algebraic isomorphism ϕ. By Theo′
rem 8.4, this implies that f ∈ C. Consequently, the induced bijection f : G → G
belongs to the set C. Since obviously f ∈ B, we conclude that f belongs to the
right-hand side of (26), as required.
Conversely, let f belong to the right-hand side of (26). By formula (25) in
Lemma 9.1, it suffices to verify that f induces ϕ. To this end, let s ∈ S. Assume
first that s ⊆ eU . Then s equals the union of sY , Y ∈ U. Therefore since f ∈ C,
conditions (22) are satisfied for all Y and hence
[
[
[
sf = (
sY )f =
(sY )f =
ϕY,Y f (sY ) = ϕ(s).
Y ∈U

Y ∈U

Y ∈U

Now assume that s is outside the equivalence relation eU . Let us prove that
[
[
X ×Y
and
sf =
(27)
s=
X ′ × Y ′,
X,Y ∈L,
(X,Y )∈s

X ′ ,Y ′ ∈L′ ,
(X ′ ,Y ′ )∈s′

where s = π(s) and s′ = π ′ (sf ). Since (eU )f = eU′ , the relation sf is outside the
equivalence relation eU′ . Therefore, it suffices to verify the first equality of (27);
denote the right-hand side of this equality by t. Clearly, s ⊆ t. Conversely, let

TESTING ISOMORPHISM OF CENTRAL CAYLEY GRAPHS

19

(X, Y ) ∈ t for some (X, Y ) ∈ s. Since s is outside eU , we conclude that X × Y
is a basis relation of the coherent configuration Inv(KL ) (Theorem 4.4). Since
Inv(KL ) ≥ X , it follows that this basis relation is contained in a basis relation of
X which equals s, because (X, Y ) ∈ s. Therefore, t ⊆ s. This completes the proof
of (27) implying s = π −1 (s) and sf = (π ′ )−1 (s′ ).
On the other hand, the graph isomorphism f ∈ B ∩ C induces an algebraic
′
isomorphism ϕ : X → X that coincides with the restriction of the algebraic isomorphism ϕ modulo eL . Thus,
ϕ(s) = ϕ(π −1 (s)) = (π ′ )−1 (ϕ(s)) = (π ′ )−1 ((s)f ) = (π ′ )−1 (s′ ) = sf ,
as required.



9.3. The algorithm. In the algorithm below, the input is given by two central
Cayley graphs Γ and Γ′ over almost simple groups G and G′ , respectively. It is
assumed that these groups are presented by the multiplication tables. The output
consists of the set Iso(Γ, Γ′ ), which is either empty or equals the set Aut(Γ)f for
some f ∈ Iso(Γ, Γ′ ). Here, the group Aut(Γ) is presented by a generating set.
Central Cayley graph isomorphism test
Step 1. Find the principal sections of the automorphism groups of the (central
Cayley) schemes WL(Γ) and WL(Γ′ ) (Theorem 7.1); denote by U, L and U′ , L′ the
associated partitions of G and G′ , respectively.
Step 2. Find the schemes X = WL(Γ, {eU , eL }) and X ′ = WL(Γ′ , {eU′ , eL′ }) and
the algebraic isomorphism ϕ satisfying condition (24); if ϕ does not exist, output
Iso(Γ, Γ′ ) = ∅.
Step 3. Find the set C = Cϕ (X , X ′ ) (Theorem 8.4).
Step 4. Using the graph isomorphism and coset intersection algorithms from [1],
′
find the set B = Iso(Γ, Γ ) and then the set B ′ = B ∩ C.
Step 5. Output Iso(Γ, Γ′ ) = π −1 (B ′ ).

To complete the proof of Theorem 1.1, we show that the above algorithm correctly finds the set Iso(Γ, Γ′ ) in time poly(n). Note that every graph isomorphism
f ∈ Iso(Γ, Γ′ ) induces an algebraic isomorphism ϕ satisfying condition (24). Therefore, the output at Step 2 is correct. Thus, the correctness of the output at Step 5
and hence of the algorithm immediately follows from Theorem 9.2.
To estimate the running time, we note that all the steps except for Step 4 run in
polynomial time (Theorem 7.1, Lemma 9.1, and Theorem 8.4). Furthermore, the
graph isomorphism and coset intersection algorithms from [1] are applied at Step 4
to graphs with m = |L| vertices and to the cosets contained in√Sym(m), respectively.
Each of these algorithms runs in time at most exp((log m)c m). Since m ≤ log n,
the complexity of this step does not exceed
√
exp((log m)c m) ≤ exp((log log n)c (log n)1/2 ) ≤ exp(log n) ≤ n
for sufficiently large n and a suitable constant c > 0. Thus, the running time of the
algorithm is polynomial in n, as required.


20

ILIA PONOMARENKO AND ANDREY VASIL’EV

References
[1] L. Babai, W. Kantor, and E. M. Luks, “Computational complexity and the classification of
finite simple groups,” in: Proceedings of the 24th Ann. Symp. Found. Comput. Sci (1983),
pp. 162–171.
[2] J. Bray, J. Holt, and D. Roney-Dougal, The Maximal Subgroups of the Low-Dimensional
Finite Classical Groups, Cambridge University Press, Cambridge (2013).
[3] P. J. Cameron, Permutation Groups, Cambridge University Press (1999).
[4] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson, An ATLAS of
Finite Groups, Oxford University Press, Oxford (1985).
[5] F. Dalla Volta and A. Lucchini, “Generation of almost simple groups,” J. Algebra, 178, No. 1,
194–223 (1995).
[6] S. Evdokimov and I. Ponomarenko, “Recognizing and isomorphism testing circulant graphs
in polynomial time,” Algebra Analiz, 15, No. 6, 1–34 (2003).
[7] S. Evdokimov and I. Ponomarenko, “Permutation group approach to association schemes,”
Eur. J. Combin., 30,1456–1476 (2009).
[8] S. Evdokimov and I. Ponomarenko, “Schurity of S-rings over a cyclic group and generalized
wreath product of permutation groups,” Algebra Analiz, 24, No. 3, 84–127 (2012).
[9] A. Ganesan, “Automorphism group of the complete transposition graph,” J. Algebr. Combin.,
42, No. 3, 793–801 (2015).
[10] C. H. Li, “On isomorphisms of finite Cayley graphs – a survey,” Discrete Math., 256, 301-334
(2002).
[11] M. W. Liebeck, Ch. E. Praeger, and J. Saxl, “Regular subgroups of primitive permutation
groups,” Memoirs Amer. Math. Soc., 203, No. 952, 1–88 (2010).
[12] E. M. Luks, “Isomorphism of graphs of bounded valence can be tested in polynomial time,”
J. Comp. Sys. Sci., 25, 42–65 (1982).
[13] M. Muzychuk, “A solution of the isomorphism problem for circulant graphs,” Proc. London
Math. Soc., 88, 1–41 (2004).
[14] I. Ponomarenko, “Bases of schurian antisymmetric coherent configurations and isomorphism
test for schurian tournaments,” J. Math. Sci., 192, No. 3, 316–338 (2013).
[15] B. Weisfeiler (editor), On Construction and Identification of Graphs, Lecture Notes Math.,
558 (1976).
[16] H. Wielandt, Finite Permutation Groups, Academic press, New York - London (1964).
[17] H. Wielandt Permutation Groups Through Invariant Relations and Invariant Functions,
Lect. Notes Dept. Math. Ohio St. Univ., Columbus (1969).
St.Petersburg Department of the Steklov Mathematical Institute, St.Petersburg,
Russia
E-mail address: inp@pdmi.ras.ru
Sobolev Institute of Mathematics, Novosibirsk, Russia
Novosibirsk State University, Novosibirsk, Russia
E-mail address: vasand@math.nsc.ru

