Also available on http://amc.imfm.si
ARS MATHEMATICA CONTEMPORANEA 1 (2008) 38–43
On the Cayley Isomorphism Problem for a
Digraph with 24 Vertices
Pablo Spiga
Università degli Studi di Padova
Dipartimento di Matematica Pura ed Applicata, 35131 Via Trieste 63, Padova, Italy
Received 9 January, accepted 15 May 2007, published online 19 June 2008
Abstract
In this paper we are mainly concerned with the Cayley isomorphism problem for groups
containing Q8. We prove that the group Q8 × C3 is not a CI-group with respect to colour
ternary relational structures. Further, we prove that the non-nilpotent group C3 nQ8 is not a
CI-group with respect to graphs.
Keywords: Regular subgroup, Cayley isomorphism.
Math. Subj. Class.: 05E20, 05E99
1 Introduction
A k-ary relational structure X is an ordered pair (Ω, E), where E is a subset of the set Ωk.
A 3-ary relational structure is also referred to as a ternary relational structure. Further, if we
assign a colour to each “edge” of E, then the resulting structure X is said to be a colour
k-ary relational structure. Let X = (Ω, E) be a colour k-ary relational structure. We denote
by AutX the permutation group on Ω defined by {σ ∈ Sym(Ω) | eσ ∈ E for any e ∈
E and e, eσ have the same colour}.
Let G be a permutation group on Ω and X be a (colour) k-ary relational structure on Ω.
We say that X is a Cayley (colour) k-ary relational structure on the group G if the right
regular representation of G is contained in AutX . We note that in this case there is a natural
bijection between Ω and G. Therefore, X is isomorphic to the (colour) k-ary relational
structure (G,F ), for some subset F of Gk. In particular, without loss of generality, we can
assume that the underlying “vertex-set” of a Cayley (colour) k-ary relational structure on G
is the group G itself.
E-mail address: spiga@math.unipd.it (Pablo Spiga)
Copyright c© 2008 DMFA – založništvo
P. Spiga: On the Cayley Isomorphism Problem for a Digraph with 24 Vertices 39
Recall that if X = (G,E) and X ′ = (G,E′) are Cayley (colour) k-ary relational struc-
tures on G, then X and X ′ are said to be Cayley isomorphic if there exists an automorphism
of G that takes E to E′.
The group G is said to be a CI-group with respect to (colour) k-ary relational structures
if, for all Cayley (colour) k-ary relational structures X and X ′ on G, the structures X and X ′
are isomorphic if and only if they are Cayley isomorphic.
See [2] for an account of Cayley colour k-ary relational structures and CI-groups. We
note that if k = 2, then we get the usual definition of digraph, Cayley graph and CI-group.
Furthermore, it is clear that if G is a CI-group with respect to Cayley colour k-ary relational
structures, then G is CI-group with respect to Cayley k-ary relational structures
We recall that G is a CI-group with respect to (colour) k-ary relational structures if and
only if, for any Cayley (colour) k-ary relational structure X on G, any two regular subgroups
of AutX isomorphic to G are conjugate in AutX , see [1].
It is fairly interesting to note that, if k ≥ 4, then the classification of CI-groups with
respect to (colour) k-ary relational structures was achieved in [5].
Note that the classification of CI-groups with respect to (colour) graphs is a wide open
and very interesting problem, see [4] for an overview of the main results.
We point out that the classification of CI-groups with respect to (colour) ternary relational
structures is also wide open. We refer to [2] for an account of this problem.
In Theorem 6, we prove that SL(2, 3) is not a CI-group with respect to graphs. In partic-
ular this result gives further restrictions on the structure of a CI-group and it narrows the list
of possible CI-groups given in [4]. We note that SL(2, 3) is isomorphic to C3 n Q8, where
the action of C3 on Q8 is non-trivial.
Also, in Theorem 8, we prove thatQ8×C3 is not a CI-group with respect to colour ternary
relational structures. So, this result improves the list of possible CI-groups with respect to
colour ternary relational structures given in [2].
It is worth noticing thatQ8 and C3 are CI-groups with respect to colour ternary relational
structures. In particular, Q8 × C3 is the only example known to the author of this paper, of
a non CI-group with respect to colour ternary relational structures that is the direct product
of CI-groups with respect to colour ternary relational structures of coprime order. We would
like to point out that no example of this behaviour is known for CI-groups with respect to
graphs.
2 The construction
Let QH and QK be isomorphic to Q8, with generators iH , jH and iK , jK (respectively). So,
i2H = j
2
H = [iH , jH ] ∈ ξ(QH) and i4H = 1, and similar relations hold for the group QK . In
this paper, ξ(G) denotes the centre of a group G.
We denote by E the extraspecial groupQH ◦QK , i.e. the central product ofQH andQK ,
see [3]. In other wordsE is the direct product ofQH andQK with their centres identified, i.e.
E = (QH×QK)/〈i2H i2K〉. ThenE is the 2-group of order 32 with generators iH , jH , iK , jK
and with relations
i4H = [iH , iK ] = [iH , jK ] = [jH , iK ] = [jH , jK ] = 1,
i2H = i
2
K = j
2
H = j
2
K = [iH , jH ] = [iK , jK ] ∈ ξ(E).
We recall that if G is a finite group and ϕ : G → G is a function mapping a generating
40 Ars Mathematica Contemporanea 1 (2008) 38–43
set of G to another generating set of G and preserving the defining relations of G, then ϕ is
an automorphism of G.
Now we denote by C the subgroup of Aut(E) generated by x, y, t, where x, y and t are
defined as follows:
ixH = jH , j
x
H = iHjH , i
x
K = iKjK , j
x
K = iK
iyH = iHjH , j
y
H = iH , i
y
K = iKjK , j
y
K = iK
itH = iK , j
t
H = jK , i
t
K = iH , j
t
K = jH .
Using the previous paragraph and the relations of E given above, the reader may check that
x, y and t define automorphisms of E.
Lemma 1. (i) t2 = x3 = y3 = 1,
(ii) xt = x−1, [x, y] = 1 and [t, y] = 1 (so y is in the centre of C),
(iii) C is isomorphic to Sym(3)× C3, and
(iv) xy centralizes iH , jH and xy−1 centralizes iK , jK .
Proof. (i) By definition of t, we have that t2 fixes iH , jH , iK , jK . Therefore, t2 fixes every
element of E, thus t2 = 1. Now,
ix
3
H = (i
x
H)
x2 = (jxH)
x = (iHjH)x = jH iHjH = iH .
This yields that x3 centralizes iH . Similarly, the reader can check that x3, y3 centralize the
generators iH , jH , iK , jK of E. Therefore x3 = y3 = 1.
(ii) We note that ix
t
H = i
txt
H = i
xt
K = (iKjK)
t = iHjH = ix
−1
H . Similarly, the reader can
check that jx
t
H = j
x−1
H , i
xt
K = i
x−1
K , j
xt
K = j
x−1
K . This says that x
t = x−1. The proofs that
[y, t] = 1 and [x, y] = 1 are analogous.
(iii) It follows from (i), (ii).
(iv) By definition of x and y, we have ixyH = j
y
H = iH and j
xy
H = (iHjH)
y = iHjH iH =
jH . Thus xy centralizes iH , jH . Similarly, the reader can check that xy−1 centralizes iK , jK .
If H is a subgroup of a group G, then we say that H is a core-free subgroup of G if the
only normal subgroup of G contained in H is 1, i.e. ∩g∈GHg = 1. Recall that if H is a
core-free subgroup of G, then the action of G on the right cosets of H in G is faithful.
Now we denote by A the group C n E. Consider B = 〈iH i−1K , t, x〉. We denote by v1
the element iH i−1K , and set v2 = v
x
1 , v3 = v
x
2 and BE = B ∩ E.
Lemma 2. The group BE is an elementary abelian 2-group of order 4 and consists of
id, v1, v2, v3. The group B is isomorphic to Sym(4) and B ∩ By = 〈x, t〉. The group B
is a core-free subgroup of A.
Proof. The elements v1, v2, v3 have order 2 and
v1v2 = iH i−1K jH(iKjK)
−1 = iHjHj−1K = v3.
So, v1, v2, v1v2 are involutions and hence v1 and v2 commute. Therefore 〈v1, v2, v3〉 is an
elementary abelian 2-group of order 4. Further, vt1 = v1 and v
t
2 = v3. This shows that
BE = 〈v1, v2〉. In particular, BE = {id, v1, v2, v3}.
P. Spiga: On the Cayley Isomorphism Problem for a Digraph with 24 Vertices 41
Now, B = 〈x, t〉nBE and Lemma 1(i), (ii) yields B ∼= Sym(4).
By Lemma 1(ii), we have B ∩ By ≥ 〈x, t〉. Now, as B is isomorphic to Sym(4) and
〈x, t〉 is isomorphic to Sym(3), we have that either B ∩ By = 〈x, t〉 or B = By . Since
vy1 = iHjH(iKjK)
−1 ∈ By \B, we get B ∩By = 〈x, t〉.
Thus, if B contains a normal subgroup N of A, we must have N ≤ 〈x, t〉. But 〈x, t〉 ∼=
Sym(3), and the only subgroup of Sym(3) normal in Sym(4) is 1. So N = 1. Thus B is a
core-free subgroup of A.
Define H = 〈iH , jH , xy〉, K = 〈iK , jK , xy−1〉, U = 〈iH , jH , y〉 and V = 〈iH , jH ,
xy−1〉.
Note that, by the definition of x, y and by Lemma 1(iv), the groups H,K are isomorphic
to Q8 × C3 and U, V are isomorphic to SL(2, 3) (we recall that SL(2, 3) is isomorphic to
C3 nQ8, where the action of C3 on Q8 is non-trivial).
Lemma 3. B ∩H = B ∩K = B ∩ U = B ∩ V = 1 and BH = BK = BU = BV = A.
Proof. We first prove that B ∩ H = B ∩ K = 1 and BH = BK = A. Since t lies in
B and Ht = K, it is enough to prove that B ∩ H = 1 and BH = A. We have B ∩
H ⊆ E〈x, t〉 ∩ E〈xy〉 = E. So, B ∩ H = B ∩ (H ∩ E) = B ∩ 〈iH , jH〉 = 1. Since
|A| = |E||C| = 32 · 18 = 24 · 24 = |H||B| and B ∩H = 1, we have BH = HB = A.
Now, we prove that B ∩ U = 1 and BU = A. We have B ∩ U ⊆ E〈x, t〉 ∩ E〈y〉 = E.
So, B ∩ U = B ∩ (U ∩ E) = B ∩ 〈iH , jH〉 = 1. Since |A| = |U ||B| and B ∩H = 1, we
have BU = A. Similarly, the reader can check that B ∩ V = 1 and BV = A.
Next, we consider the action of A on the right cosets Ω = A/B. Lemma 2 yields that A
is a permutation group of degree 24 with point stabilizer isomorphic to Sym(4). Lemma 3
yields that H,K,U and V are regular subgroups of A.
Lemma 4. Let ∆ be the B-orbit of the point By of Ω. We have
∆ = {By,Byv1, Byv2, Byv3}
and the action of B on ∆ is equivalent to the action of Sym(4) on four points.
Proof. By Lemma 2, we have B ∩ By = 〈x, t〉. Therefore, the group BE acts regularly
on ∆. Since y centralizes 〈x, t〉, we have that every element of 〈x, t〉 fixes By. So, ∆ =
{By,Byv1, Byv2, Byv3}. Moreover,
Byv1x = Bx(yv1)x = Byv2, Byv2x = Bx(yv2)x = Byv3.
This shows that x acts on ∆ as a 3-cycle. Similarly,
Byv1t = Btyv1 = Byv1, Byv2t = Bt(yv2)t = Byv3.
This says that t acts on ∆ as a 2-cycle. Thus the lemma is proved.
Let S be the orbital corresponding to the suborbit ∆ ofA, i.e. S = {(Ba,Bya) | a ∈ A}.
Let Γ be the orbital digraph of A corresponding to the orbital S, we recall that Γ has vertex
set Ω and edge set S. We note that, by construction, A is a subgroup of Aut Γ.
Proposition 5. A = Aut Γ.
Proof. Since B acts 4-transitively on ∆, it is enough to prove that if σ is an automorphism
of Γ fixing the vertex B and the out-neighbours of B, then σ = id. We leave this routine
exercise to the conscientious reader.
42 Ars Mathematica Contemporanea 1 (2008) 38–43
3 SL(2, 3)
In this section, we prove that SL(2, 3) is not a CI-group (with respect to graphs). We recall
that U ∼= V ∼= SL(2, 3).
Theorem 6. The group SL(2, 3) is not a CI-group with respect to graphs.
Proof. The groups U, V are regular subgroups of A isomorphic to SL(2, 3). Furthermore, by
Proposition 5, the group A is the automorphism group of the digraph Γ. In particular, Γ is a
Cayley graph on SL(2, 3). Therefore, it is enough to prove that U, V are not conjugate in A.
We argue by contradiction. Let g be inA such that Ug = V . Since 〈iH , jH〉 is a characteristic
subgroup of U and V , we have 〈iH , jH〉g = 〈iH , jH〉, i.e. g ∈ NA(〈iH , jH〉) = 〈x, y〉E.
Now, g = ze for some z ∈ 〈x, y〉 and e ∈ E. The element y lies in U , therefore yg =
(yz)e = ye = y[y, e] lies in V . But V ⊆ 〈xy−1〉E and [y, e] ∈ E, so y ∈ 〈xy−1〉, a
contradiction.
4 Q8 × C3
In this section, we prove that Q8 × C3 is not a CI-group with respect to colour ternary
relational structures. We recall that H ∼= K ∼= Q8 × C3.
Set G = E〈x, y〉. Let T1 be the subset of Ω3 defined by {(Bg,Bg,Byg) | g ∈ G}.
Also, let T2 be the subset of Ω3 given by {(Bg,BiHg,Bj−1H g) | g ∈ G}. The sets T1, T2
define two ternary relational structures on Ω. We recall that Aut Ti = {σ ∈ Sym(Ω) | tσ ∈
Ti for any t ∈ Ti}, for i = 1, 2.
Proposition 7. G = Aut T1 ∩Aut T2.
Proof. We claim that A = Aut T1. The group G is a transitive subgroup of A and, by
Lemma 4, the stabilizer in G of the point B of Ω is isomorphic to Alt(4) and acts transitively
on ∆. This says that {(Bg,Byg) | g ∈ G} = {(Ba,Bya) | a ∈ A} = S. Let σ be in
Aut T1 and e be in S. Now, e = (Bg,Byg), for some g ∈ G. Set τ = (Bg,Bg,Byg).
Now, τ ∈ T1, therefore τσ ∈ T1. So, τσ = (Bg′, Bg′, Byg′), for some g′ ∈ G. In particular
eσ = (Bg′, Byg′) ∈ S. Since e is an arbitrary element of S, we get σ ∈ Aut Γ = A. Since σ
is an arbitrary element of Aut T1, we get Aut T1 ⊆ A. By a similar argument, A ⊆ Aut T1.
Therefore, A = Aut T1.
By construction, the group G is a subgroup of Aut Ti, for i = 1, 2. The group G has
index 2 in A and A = G〈t〉. Therefore G = Aut T1∩Aut T2 if and only if t /∈ Aut T2. Now,
by Lemma 1, (B,BiH , Bj−1H )
t = (Bt,BiHt, Bj−1H t) = (B,BiK , Bj
−1
K ). Since there is
no element g ∈ G such that (Bg,BiHg,Bj−1H g) = (B,BiK , Bj
−1
K ), we have t /∈ Aut T2.
Thus the proposition is proved.
Theorem 8. The group Q8 × C3 is not a CI-group with respect to colour ternary relational
structures.
Proof. The groups H,K are regular subgroups of G. Furthermore, by Proposition 7, the
group G is the automorphism group of a colour ternary relational structure (indeed, with just
two colours: T1, T2). In particular, Ti is a Cayley ternary relational structure on Q8 × C3,
for i = 1, 2. So, it is enough to prove that H,K are not conjugate in G. We argue by
contradiction. Let g be in G such that Hg = K. Clearly, 〈iH , jH〉g = 〈iK , jK〉. Since
〈iH , jH〉 is a normal subgroup of G, we get a contradiction.
P. Spiga: On the Cayley Isomorphism Problem for a Digraph with 24 Vertices 43
References
[1] L. Babai, Isomorphism problem for a class of point-symmetric structures, Acta Math. Acad. Sci.
Hungar. 29 (1977), 329–336.
[2] E. Dobson, On the Cayley isomorphism problem for ternary relational structures, J. Combin. The-
ory Ser. A 101 (2003), no. 2, 225–248.
[3] C. R. Leedham-Green and S. McKay, The structure of groups of prime power order, London Math-
ematical Society Monographs. New Series, 27, Oxford Science Publications, Oxford University
Press, Oxford, 2002. xii+334 pp.
[4] C. H. Li, On Isomorphisms of finite Cayley graphs – a survey, Discrete Math. 246 (2002), 301–334.
[5] P. P. Pálfy, Isomorphism problem for relational structures with a cyclic automorphism, European
Journal of Comb. 8 (1987), 35–43.