The action of Sylow 2-subgroups of symmetric groups on the set of bases and the problem of isomorphism of their Cayley graphs
Base (minimal generating set) of the Sylow 2-subgroup of S₂n is called diagonal if every element of this set acts non-trivially only on one coordinate, and different elements act on different coordinates. The Sylow 2-subgroup Pn(2) of S₂n acts by conjugation on the set of all bases. In presented pap...
Збережено в:
| Опубліковано в: : | Algebra and Discrete Mathematics |
|---|---|
| Дата: | 2016 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2016
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/155248 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | The action of Sylow 2-subgroups of symmetric groups on the set of bases and the problem of isomorphism of their Cayley graphs / B.T. Pawlik // Algebra and Discrete Mathematics. — 2016. — Vol. 21, № 2. — С. 264–281. — Бібліогр.: 6 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860260898724118528 |
|---|---|
| author | Pawlik, B.T. |
| author_facet | Pawlik, B.T. |
| citation_txt | The action of Sylow 2-subgroups of symmetric groups on the set of bases and the problem of isomorphism of their Cayley graphs / B.T. Pawlik // Algebra and Discrete Mathematics. — 2016. — Vol. 21, № 2. — С. 264–281. — Бібліогр.: 6 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | Base (minimal generating set) of the Sylow 2-subgroup of S₂n is called diagonal if every element of this set acts non-trivially only on one coordinate, and different elements act on different coordinates. The Sylow 2-subgroup Pn(2) of S₂n acts by conjugation on the set of all bases. In presented paper the~stabilizer of the set of all diagonal bases in Sn(2) is characterized and the orbits of the action are determined. It is shown that every orbit contains exactly 2n−1 diagonal bases and 2²n−²n bases at all. Recursive construction of Cayley graphs of Pn(2) on diagonal bases (n≥2) is proposed.
|
| first_indexed | 2025-12-07T18:55:30Z |
| format | Article |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 21 (2016). Number 2, pp. 264–281
© Journal “Algebra and Discrete Mathematics”
The action of Sylow 2-subgroups of symmetric
groups on the set of bases and the problem
of isomorphism of their Cayley graphs
Bartłomiej Pawlik
Communicated by V. I. Sushchansky
Abstract. Base (minimal generating set) of the Sylow 2-
subgroup of S2n is called diagonal if every element of this set acts
non-trivially only on one coordinate, and different elements act on
different coordinates. The Sylow 2-subgroup Pn(2) of S2n acts by
conjugation on the set of all bases. In presented paper the stabilizer
of the set of all diagonal bases in Sn(2) is characterized and the orbits
of the action are determined. It is shown that every orbit contains
exactly 2n−1 diagonal bases and 22
n
−2n bases at all. Recursive
construction of Cayley graphs of Pn(2) on diagonal bases (n > 2) is
proposed.
Introduction
Let n be a positive integer greater then 1 and let p be a prime. By
Pn(p) we denote the Sylow p-subgroup of the symmetric group Spn . In
this paper by base of a group we mean a minimal set of generators of this
group (whitch further is simply called a base).
It is known that
Pn(p) ∼= Cp ≀ Cp ≀ . . . ≀ Cp
︸ ︷︷ ︸
n
,
2010 MSC: 20B35, 20D20, 20E22, 05C25.
Key words and phrases: Sylow p-subgroup, group base, wreath product of
groups, Cayley graphs.
B. Pawlik 265
where Cp is a cyclic permutation group of order p. For every finite p-
group G the following equality holds:
Φ(G) = G′ · Gp,
where Φ(G) is a Frattini subgroup of G (see e.g. [2]). If G = Pn(p) then
G′ = Gp, thus
Φ(Pn(p)) = (Pn(p))′.
So
Pn(p)/(Pn(p))′ ∼= Z
n
p ,
but Z
n
p is a vector space over Zp and every basis of Zn
p over Zp induces
a base of Pn(p). Thus every base of Pn(p) has exactly n elements. The
group Pn(p) acts on the set of bases of Pn(p) by inner automorphisms.
The purpose of this article is to investigate orbits of this action and
the respective Cayley graphs of Pn(p). We will consider the case p = 2,
because group Pn(2) is of particular interest. Namely group Pn(2) is the
full group of automorphisms of 2-adic rooted tree of height n (see eg. [3])
and the inverse limit of such groups is a group of automorphisms of 2-adic
rooted tree, which is widely investigated because of its properties (for the
survey, see e.g. [1]). On the other hand, p = 2 is also the only case for
which considered diagonal bases generate undirected Cayley graphs.
In Section 2 we recall basic facts about Sylow p-subgroups of symmetric
groups and the polynomial (Kaluzhnin) representation of such subgroups.
Section 3 shows a special type of bases of Sylow 2-subgroups of S2n called
diagonal bases and some of their properties (an exemplary construction
of a diagonal base is presented in [5]). Also in this section we present
some further investigations of these bases, which lead us to the definition
of primal diagonal bases and characterize the orbits of the action of Pn(2)
by inner automorphisms on the set of all diagonal bases. In Section 4 we
present a recursive algorithm for construction of Cayley graphs of Pn(2)
on diagonal bases. In Section 5 we give some examples of Cayley graphs
constructed with the proposed algorithm and present two non-isomorphic
Cayley graphs of P3(n).
1. Preliminaries
Let Xi be the vector of variables x1, x2, . . . , xi. Polynomial representa-
tion of group Pn(p) (see e.g. [4], [6]) states that every element f ∈ Pn(p)
can be written in form
f = [f1, f2(X1), f3(X2), . . . , fn(Xn−1)], (1)
266 The action of Sylow 2-subgroups. . .
where f1 ∈ Zp and fi : Zi−1
p → Zp for i = 2, . . . , n are reduced polynomials
from the quotient ring Zp[Xi]/〈xp
1 −x1, . . . , xp
i −xi〉. Following the original
paper of L. Kaluzhnin ([4]) we call such element f a tableau. By [f ]i we
denote the i-th coordinate of tableau f and by f(i) we denote the table
f(i) = [f1, f2(X1), . . . , fi(Xi−1)] ∈ Pi(p),
where i 6 n.
For tableaux f, g ∈ Pn(p), where f has the form (1) and
g = [g1, g2(X1), g3(X2), . . . , gn(Xn−1)]
the product fg has the form
fg =
[
f1 + g1, f2(X1) + g2(x1 + f1), . . . ,
fn(Xn−1) + gn(x1 + f1, x2 + f2(X1), . . . , xn−1 + fn−1(Xn−2))
]
,
and the inverse
f−1 =
[
− f1, −f2(x1 − f1), . . . ,
− fn
(
x1 − f1, x2 − f2(x1 − f1), . . . , xn−1 − fn−1(x1 − f1, . . .)
)]
.
Let B be the set of all bases of Pn(p). Pn(p) acts on the set B by
conjugation:
Bu = 〈u−1B1u, u−1B2u, . . . , u−1Bnu〉 (2)
for all B = {B1, . . . , Bn} ∈ B.
Lemma 1. The center of group Pn(p) has the form
Z(Pn(p)) = {[0, . . . , 0, α] : α ∈ Zp}.
Proof. See [4].
Proposition 1. The action (2) of Pn(p) on the set B is semi-regular.
The length of every orbit of this action is equal to p
pn
−1
p−1
−1
.
Proof. An action of a group G on a set X is semi-regular, iff every orbit
of G on X has the same length. Let B = {B1, B2, . . . , Bn} be a base of
Pn(p). For any u ∈ Pn(p) we have Bu = B if and only if u−1Biu = Bi for
every i = 1, . . . , n. Since 〈B1, . . . , Bn〉 = Pn(p), it follows that for every
B. Pawlik 267
g ∈ Pn(2), equality u−1gu = g holds if and only if u ∈ Z(Pn(2)). But
following Lemma 1:
|Z(Pn(p))| = p,
hence the length of orbit containing B is equal to |Pn(p)|
p
. Thus the length
of every orbit is the same regardless of the choice of base B. Hence
the action (2) is semi-regular. The length of every orbit is equal to
|Pn(p)|
p
= p
pn
−1
p−1
−1
.
2. Diagonal bases of Pn(2)
From now on we assume that p = 2.
2.1. Definitions and basic facts
Let xn be the monomial x1 ·x2 · . . . ·xn and let xn/xi be the monomial
x1x2 . . . xi−1xi+1 . . . xn for i = 1, . . . , n.
In [6] the authors defined so-called triangular bases of group Pn(p). In
the following article we consider a special type of triangular bases, which
we call diagonal. However, the notion of diagonal bases can be formulated
independently of triangularity.
Definition 1. Base B = {B1, . . . , Bn} ∈ B is called diagonal if for any i,
1 6 i 6 n, the table Bi is i-th coordinative, i.e. [Bi]j = 0 for j 6= i.
It is well known that in every base B of Pn(2) for every i there
exists a tableaux B′ ∈ B which contains a monomial xi−1 on i-th co-
ordinate. Thus, the nonzero coordinates of elements of diagonal base
B = {B1, . . . , Bn} have form [B1]1 = 1 and [Bi]i = bi(Xi−1), where bi
contains monomial xi−1 for every i = 2, . . . , n.
Diagonal bases B = {B1, . . . , Bn} and C = {C1, . . . , Cn} of Pn(2) are
conjugate if there exists element u ∈ Pn(2) such that u−1Bu = C, i.e.
u−1Biu = Ci (3)
for every i = 1, . . . , n.
Definition 2. The length l(m) of a nonzero monomial m = xi1
. . . xik
is
the number of variables of this monomial. We assume that l(0) = −1 and
l(1) = 0. The length of the reduced polynomial is equal to the maximal
length of its monomials.
268 The action of Sylow 2-subgroups. . .
For every polynomials f and g the following inequality holds:
l(f + g) 6 max{l(f), l(g)}.
Definition 3. Reduced polynomial fn : Zn−1
2 → Z2 is called primal if
fn = xn−1 + βn(Xn−1),
where l(βn) 6 n − 3.
Diagonal base B = {B1, . . . , Bn} is called primal if [Bn]n is primal
polynomial.
Let δ(Pn(2)) and δ′(Pn(2)) be the numbers of different diagonal bases
and different primal diagonal bases of Pn(2), respectively.
Theorem 1. The following equalities holds:
δ(Pn(2)) = 22n−(n+1) and δ′(Pn(2)) = 22n−2n.
Proof. Let B = {B1, . . . , Bn} be a diagonal base of Pn(2), i.e. every
tableau Bi has on i-th coordinate a polynomial of length i−1 for 1 6 i 6 n.
Every polynomial [Bi]i contains monomial xi−1. There are 2i−1 monomials
on variables x1, . . . , xi−1. Thus there are 22i−1−1 polynomials on (i − 1)
variables, which length equal to i − 1. So the number of diagonal bases of
Pn(2) is equal to
n−1∏
i=0
22i−1 = 2γ ,
where γ =
∑n−1
i=0 (2i − 1) = 2n − (n + 1).
Let B be a primal diagonal base, i.e. [Bn]n be the primal polynomial.
There are 22n−1−n primal polynomials on (n−1) variables. So the number
of different primal diagonal bases of Pn(2) is equal to
(
n−2∏
i=0
22i−1
)
· 22n−1−n = 2γ′
,
where γ′ =
(
∑n−2
i=0 (2i − 1)
)
+ 2n−1 − n = 2n−1 − n + 2n−1 − n = 2n − 2n.
B. Pawlik 269
2.2. Properties of diagonal bases
Let
Λ = {[λ1, . . . , λn] : λi ∈ Z2, 1 6 i 6 n}
be an maximal elementary abelian 2-subgroup of group Pn(2). For any
λ = [λ1, . . . , λn] ∈ Λ and vector Xn−1 we denote
Xn−1 + λ = (x1 + λ1, . . . , xn−1 + λn−1).
We can define the left and right actions of group Λ on the set of
reduced polynomial on (n − 1) variables in the following way. For a
reduced polynomial f : Zn−1
2 → Z2 and λ = [λ1, . . . , λn] ∈ Λ let
λ ⋆ f(Xn−1) = f(Xn−1 + λ) + λn and f(Xn−1) ⋆ λ = f(Xn−1) + λn.
As we can can see, this actions resemble the multiplication of tables
in Pn(p).
Lemma 2. Let λ = [λ1, . . . , λn] ∈ Λ and let f(Xn−1) = xn−1. Then
λ−1 ⋆ f(Xn−1) ⋆ λ = xn−1 +
n−1∑
i=1
λi(xn−1/xi) + h(Xn−1),
where h is some reduced polynomial such that l(h) 6 n − 3.
Proof. We have
λ−1 ⋆ f(Xn−1) = (x1 + λ1)(x2 + λ2) . . . (xn−1 + λn−1) + λn
= x1x2. . .xn−1+(λ1x2. . .xn−1+λ2x1x3. . .xn−1+. . .+λn−1x1. . .xn−2)
+ . . . + λ1λ2 . . . λn−1 + λn
= xn−1 +
n−1∑
i=1
λi(xn−1/xi) + h(Xn−1) + λn,
where h is some reduced polynomial such that l(h) 6 n − 3. Thus
λ−1 ⋆ f(Xn−1) ⋆ λ = xn−1 +
n−1∑
i=1
λi(xn−1/xi) + h(Xn−1) + λn + λn
= xn−1 +
n−1∑
i=1
λi(xn−1/xi) + h(Xn−1).
There is also an important relation between polynomials of maximal
length and the primal polynomials.
270 The action of Sylow 2-subgroups. . .
Lemma 3. For every reduced polynomial f : Z
n−1
2 → Z2 such that
l(f) = n − 1, there exists a tableau λ ∈ Λ such that λ−1 ⋆ f ⋆ λ is the
primal polynomial.
Proof. Every polynomial f(Xn−1) such that l(f) = n − 1 can be written
in the form
f(Xn−1) = xn−1 +
n−1∑
i=1
αi(xn−1/xi) + h(Xn−1),
where αi ∈ Z2 for i = 1, . . . , n − 1 and l(h) 6 n − 3.
Let f1(Xn−1) = xn−1 and f
(i)
2 (Xn−1) = αi(xn−1/xi) for every i =
1, . . . , n − 1. Then
f = f1 +
n−1∑
i=1
f
(i)
2 + h
and
λ−1 ⋆ f ⋆ λ = λ−1 ⋆ f1 ⋆ λ +
n−1∑
i=1
(λ−1 ⋆ f
(i)
2 ⋆ λ) + λ−1 ⋆ h ⋆ λ. (4)
We construct the tableau λ using coefficients αi from the polynomial f in
form λ = [α1, . . . , αn−1, un], where un ∈ Z2 is fixed. Let us investigate
the form of sum (4). From Lemma 2 we have
λ−1 ⋆ f1(Xn−1) ⋆ λ = xn−1 +
n−1∑
i=1
αi(xn−1/xi) + h′(Xn−1)
where h′ is some reduced polynomial such that l(h′) 6 n − 3, and
λ−1 ⋆ f
(i)
2 (Xn−1) ⋆ λ =αi(xn−1/xi)
+ αi
n−1∑
j=1,j 6=i
βj
(
(xn−1/xi)/xj
)
+ αik
(i)(Xn−1),
where βj ∈ Z2 and k(i) is some reduced polynomial such that l(k(i)) 6 n−4.
Thus
n−1∑
i=1
(
λ−1 ⋆ f
(i)
2 (Xn−1) ⋆ λ
)
=
n−1∑
i=1
αi
xn−1/xi +
n−1∑
j=1,j 6=i
βj
(
(xn−1/xi)/xj
)
+ k(i)(Xn−1)
B. Pawlik 271
=
n−1∑
i=1
αi(xn−1/xi) + h′′(Xn−1),
where h′′ is some reduced polynomial such that l(h′′) 6 n − 3.
The last element in sum (4) has the form
λ−1 ⋆ h(Xn−1) ⋆ λ = h′′′
n (Xn−1),
where h′′′ is some reduced polynomial such that l(h′′′) 6 n − 3. Thus
finally
λ−1 ⋆ f(Xn−1) ⋆ λ = xn−1 +
n−1∑
i=1
αi(xn−1/xi) + h′(Xn−1)
+
n−1∑
i=1
αi(xn−1/xi) + h′′(Xn−1) + h′′′(Xn−1)
= xn−1 + h′(Xn−1) + h′′(Xn−1) + h′′′(Xn−1)
= xn−1 + b(Xn−1),
where b = h′ + h′′ + h′′′ and l(b) 6 n − 3. So λ−1 ⋆ f ⋆ λ is a primal
polynomial.
Theorem 2. Every
f = [0, 0, . . . , 0, fn(Xn−1)] ∈ Pn(2)
where l(fn) = n − 1, is conjugate to a tableau
b = [0, 0, . . . , 0, bn(Xn−1)],
where bn is the primal polynomial.
Proof. Similarly like in the proof of Lemma 3, tableau f can be written
in form
f =
[
0, . . . , 0, xn−1 +
n−1∑
i=1
αi(xn−1/xi) + hn(Xn−1)
]
,
where αi ∈ Z2 for i = 1, . . . , n − 1 and l(hn) 6 n − 3.
Let us construct the tableau u using coefficients αi from tableau f .
Let u = [α1, . . . , αn−1, un], where un ∈ Z2 is fixed. Notice that u ∈ Λ. Of
course the equality
[u−1fu]j = 0
holds for every j = 1, . . . , n − 1. From Lemma 3 we get that [u−1fu]n is
the primal polynomial.
272 The action of Sylow 2-subgroups. . .
Let us denote the set of all diagonal bases of Pn(2) by D. Now we
describe stabilizer of the set D in the group Pn(2) with respect to the
action (2).
Theorem 3. The stabilizer of the subset D ⊂ B in the group Pn(2) acting
on the set B according to (2) is equal to Λ. The kernel of this action
coincide with the center of Pn(2).
Proof. To show that Λ is the stabilizer of D we have to prove the following.
1) If B = {B1, . . . , Bn} is a diagonal base of Pn(2) and λ ∈ Λ, then
λ−1Bλ is a diagonal base of Pn(2).
2) For every diagonal bases B = {B1, . . . , Bn} and C = {C1, . . . , Cn}
of Pn(2) if there exists u ∈ Pn(2) such that u−1Bu = C, then u ∈ Λ.
A set conjugate to a base is always a base. Let 1 6 s 6 n and let Bs ∈ Pn(2)
be a tableau with the only nonzero element on its s-th coordinate. Let
j 6= s. Then
[λ−1Bsλ]j = 0.
Thus the first condition is proved.
We now prove the second condition. Let [B1]1 = 1 and [Bi]i = bi(Xi−1)
for i = 2, . . . , n. Base B is diagonal, so bi(Xi−1) 6= 0 for every i = 2, . . . , n.
Let
u = [α1, u2(X1), . . . , un(Xn)].
We will show that for every s = 1, . . . , n − 1, the reduced polynomial ui
for i = 2, . . . , n does not contain variable xs. Variable xs can be contained
only in polynomials ui for which i > s. Every such polynomial can be
described as
ui(Xi−1) = u′
i(Xi−1) · xs + u′′
i (Xi−1),
where polynomials u′
i and u′′
i do not contain variable xs. Equality
u−1Bsu = Cs can be written in form Bsu = uCs. Thus
[Bsu]k = [uCs]k (5)
for every k = 1, . . . , n. For k > s we have [Bs]k = [Cs]k = 0, so in this
case
[Bsu]k = 0 + u′
i(Xi−1) · (xs + bi(Xi−1)) + u′′
i (Xi−1)
= u′
i(Xi−1) · xs + u′
i(Xi−1) · bi(Xi−1) + u′′
i (Xi−1)
and
[uCs]k = u′
i(Xi−1) · xs + u′′
i (Xi−1) + 0 = u′
i(Xi−1) · xs + u′′
i (Xi−1).
B. Pawlik 273
Thus
[Bsu]k = [uCs]k,
u′
i(Xi−1) xs + u′
i(Xi−1) bi(Xi−1) + u′′
i (Xi−1) = u′
i(Xi−1) xs + u′′
i (Xi−1),
u′
i(Xi−1) bi(Xi−1) = 0.
We know that bi(Xi−1) 6= 0, so u′
i(Xi−1) = 0 and hence
ui = 0 · xs + u′′
i (Xi−1) = u′′
i (Xi−1),
where u′′
i does not contain variable xs.
We have shown that any variable xs for 1 6 s 6 n is not contained in
polynomials ui for i = 2, . . . , n, so ui(Xi−1) = αi, where αi is constant
and hence u = [α1, α2, . . . , αn] ∈ Λ. Thus indeed Λ is the stabilizer of
σ on D. Lemma 1 implies that the center of Pn(2) contains only the
tableaux [0, . . . , 0, 0] and [0, . . . , 0, 1].
Let
bn(Xn−1) = xn−1 +
n−1∑
i=1
αi(xn−1/xi) + βn(Xn−1),
where βn is some reduced polynomial such that l(βn) 6 n − 3. Thus
bn(x1 +λ1, . . . , xn−1 +λn−1) = xn−1 +
n−1∑
i=1
(αi +λi)(xn−1/xi)+βn(Xn−1),
where βn is a reduced polynomial such that l(βn) 6 n−3. So the necessary
condition for the equality λ−1Bnλ = Bn to hold is
αi = αi + λi
for all i = 1, . . . , n − 1. So λi = 0 for all such i. It follows that βn = βn.
Hence
λ−1Bnλ = Bn
if and only if λ1 = . . . = λn−1 = 0.
Corollary 1. If B and C are two conjugated diagonal bases of Pn(2)
such that for tableaux u, v ∈ Λ the following equalities hold:
u−1Bu = C and v−1Bv = C,
then
u = v + [0, . . . , 0, α],
where α ∈ Z2.
274 The action of Sylow 2-subgroups. . .
2.3. Properties of primal diagonal bases
Let B = {B1, . . . , Bn} be a diagonal base of Pn(2). Theorem 2 implies
that tableau Bn is conjugate with some tableau Cn = [0, . . . , 0, cn(Xn−1)],
where cn is the primal polynomial. As we could see in the proof of
Theorem 2, the tableau u which conjugate tableaux Bn and Cn belongs
to the subgroup Λ. Thus, by Theorem 3 we can formulate
Corollary 2. Every diagonal base of Pn(2) is conjugate to some primal
diagonal base.
Primal diagonal bases have another important property.
Theorem 4. If B and C are different primal diagonal bases of Pn(2),
then B and C are not conjugated.
Proof. Let us assume that bases
B = {B1, . . . , Bn} and C = {C1, . . . , Cn}
are conjugated. Then according to Theorem 3 there exists tableau u ∈ Λ
such that
u−1Bu = C. (6)
Let
Bn = [0, . . . , 0, xn−1 + βn(Xn−1)], where l(βn) 6 n − 3,
and
Cn = [0, . . . , 0, xn−1 + γn(Xn−1)], where l(γn) 6 n − 3.
From (6) we get the equality
[u−1Bnu]n = [Cn]n. (7)
By Lemma 2, we have
[u−1Bnu]n = xn−1 +
n−1∑
i=1
ui(xn−1/xi) + h(Xn−1),
where l(h) 6 n − 2. So equation (7) implies that
xn−1 +
n−1∑
i=1
ui(xn−1/xi) + h(Xn−1) = xn−1 + γn(Xn−1).
B. Pawlik 275
Thus h(Xn−1) = γn(Xn−1) and ui(xn−1/xi) = 0 for every i = 1, . . . , n−1,
so ui = 0 for every i = 1, . . . , n − 1, that is, u = [0, . . . , 0, un]. But if
u = [0, . . . , 0, un] then u−1Bu = B and from (6) we get that B = C, which
contradicts the assumption that B and C are different primal diagonal
bases.
The orbit of Pn(2) on B by action (2) which contains a diagonal base
is called D-orbit. Summing up previous results we can formulate following
Theorem 5. The following statement holds:
1) every D-orbit contains exactly one primal diagonal base;
2) every D-orbit contains exactly 2n−1 diagonal bases and 22n−2 bases
at all;
3) the number of different D-orbits is equal to 22n−2n.
Proof. 1) Corollary 2 states that every diagonal base is conjugate with
some primal diagonal base. Thus every D-orbit contains a primal diagonal
base. From Theorem 4 we get that this primal diagonal base is unique in
every D-orbit.
2) From Theorem 3 we know that the elements which conjugate
diagonal bases are of form u = [u1, . . . , un−1, un], where ui ∈ Z2 for
i = 1, . . . , n. Theorem 3 also states that conjugation does not depend
on un, so the number of conjugated diagonal bases is equal to the number
of different tableaux of the form [u1, . . . , un−1, 0]. There are 2n−1 such
tableaux. The number of all bases in single D-orbit is determined by
Theorem 1.
3) Every D-orbit contains exactly one primal diagonal base, so the
number of D-orbits is equal to the number of different primal diagonal
bases, which is equal to 22n
− 2n by Theorem 1.
3. Cayley graphs of Pn(2) on diagonal bases
We recall the definition of Cayley graphs.
Definition 4. Let G be a group and S be a set of generators of G. The
Cayley graph of group G on set S is a graph Cay(G, S) in which vertex
set is equal to G and two vertices u, v are connected by an edge iff there
exists s ∈ S such that u = v · s. Such edge will be denoted as uv.
If S = S−1, then Cay(G, S) is undirected. Thus Cayley graphs of Pn(2)
on diagonal bases are undirected.
From now on in this section we assume that n > 2.
276 The action of Sylow 2-subgroups. . .
Let B = {B1, . . . , Bn} be a diagonal base of Pn(2). By Theorem 5 base
B is in the same orbit with some primal diagonal base D = {D1, . . . , Dn},
so
Cay(Pn(2), B) ∼= Cay(Pn(2), D).
Thus investigation of Cayley graphs of P2(n) on diagonal bases is equiva-
lent with investigation of Cayley graphs only on primal diagonal bases.
Let B′ = {(B1)(n−1), . . . , (Bn−1)(n−1)}. Set B′ is a diagonal base of
group Pn−1(2).
Theorem 6. Let D = {D1, . . . , Dn−1, Dn} be a diagonal base of Pn(2)
and let D′ = {(D1)(n−1), . . . , (Dn−1)(n−1)} be a diagonal base of Pn−1(2).
Let Γ be a graph obtained from Cay(Pn(2), D) by removing edges of form
uDn for every u ∈ Pn(2). Then
1) Γ is not connected;
2) Γ contains 22n−1
connected components;
3) every connected component of Γ is isomorphic to the Cayley graph
Cay(Pn−1(2), D′).
Proof. Let (Dj1
, Dj2
, . . . , Djl
) be a tuple of (not necessarily different)
elements of D\{Dn}, i.e. Djk
∈ {D1, . . . , Dn−1} for every k = 1, . . . , l.
Thus
[
l∏
k=1
Dik
]
n
= 0. (8)
We now prove stated properties.
1) Consider vertices f1 = [0, . . . , 0] and f2 = [0, . . . , 0, 1] of graph Γ.
Equality (8) implies that
[
f1 ·
l∏
k=1
Dik
]
n
= 0.
Thus in Γ there is no path from vertex f1 to vertex f2, which implies that
Γ is not connected.
2) Let f = [0, . . . , 0, fn(Xn−1)]. Equality (8) implies that
[
f ·
l∏
k=1
Dik
]
n
= fn(Xn−1).
Thus if g = [0, . . . , 0, gn(Xn−1)] and gn 6= fn, then vertices f and g are
contained in different connected components of Γ.
B. Pawlik 277
Let f ′ be a tableau for which [f ′]n = [f ]n. Set D′ is a base of Pn−1(2),
and there exists a set {Dj1
, Dj2
, . . . , Djl
} of elements of D\{Dn} such
that
f ′ ·
l∏
k=1
Dik
= f.
Thus every vertex
f ′ = [f1, . . . , fn(Xn−1)]
of Γ is contained in the same connected component of Γ as vertices of the
form
[0, . . . , 0, fn(Xn−1)], (9)
and different vertices of form (9) lays in different connected components
of Γ, so the number of connected component of Γ is equal to the number
of different reduced polynomials fn : Zn−1
2 → Z2, which is equal to 22n−1
.
3) We have shown that every connected component of Γ contains
a vertex made of tableaux with fixed last coordinate. Let Vfn
be the
subgroup of Pn(2) such that if g ∈ Vfn
iff [gn] = fn. Thus Vfn
∼= Pn−1(2),
hence
Cay(Vfn
, D′) ∼= Cay(Pn−1(2), D′).
Theorem 6 implies the recurrent construction of Cayley graphs of Pn(2)
on primal diagonal bases. Let D = {D1, . . . , Dn} be a primal diagonal
base of Pn(2). Graph Cay(Pn(2), D) can be constructed in following way.
1) We construct 22n−1
Cayley graphs Cay(Pn−1(2), D′), where
D′ = {(D1)(n−1), . . . , (Dn−1)(n−1)}.
Every such Cayley graph may be labeled with a different reduced poly-
nomial fn : Z
n−1
2 → Z2. Denote the Cayley graph corresponding to
polynomial fn by Cayfn
.
2) In every graph Cayfn
we replace the set of vertices V (Cayfn
) =
Pn−1(2) by the set of vertices V ′ ⊂ Pn(2) in following way: we replace
u = [u1, . . . , un−1(Xn−2)] by
u′ = [u1, . . . , un−1(Xn−2), fn(Xn−1)]
for every u ∈ V (Cayfn
).
3) For every pair of vertices u′, v′ of obtained graph, if u′Bn = v′,
then we add an edge u′v′.
So in the construction we need to start with the case n = 2, which is
presented in the next section.
278 The action of Sylow 2-subgroups. . .
Above construction suggests the dependence between Cayley graphs
and Schreier coset graphs on diagonal bases of Pn(2).
Let us recall the definition of the latter graphs.
Definition 5. Let G be a group, S be a set of generators of G and H
be a subgroup of finite index in G. The Schreier coset graph Sch(G, S, H)
is a graph whose vertices are the right cosets of H in G and two vertices
Hu and Hv are connected by an edge iff there exists s ∈ S such that
Hu = Hv · s.
Let us notice that every Cayley graph of group G is a Schreier coset
graph of G in which H is a trivial subgroup.
We consider a subgroup P n(2) of group Pn(2) in which in every
tableuax the last coordinate is equal to 0, i.e. if f ∈ P n(2),then
f = [f1, f2(X1), . . . , fn−1(Xn−2), 0].
Of course P n(2) ∼= Pn−1(2).
Theorem 7. Let D = {D1, . . . , Dn} be a diagonal base of Pn(2). Then
the following conditions hold.
1) Two vertices P n(2)u and P n(2)v of graph Sch(Pn(2), D, P n(2)) are
connected by an edge, iff
P n(2)u = P n(2)v · Dn.
2) Graph Sch(Pn(2), D, P n(2)) is bipartite.
Proof. If i = 1, . . . , n − 1, then [Di]n = 0. Thus in this case
P n(2)u · Di = P n(2)u,
so elements D1, . . . , Dn−1 do not generate edges of Sch(Pn(2), D, P n(2)).
We now prove the second statement.
Vertex set V (Sch) can be described as a sum of sets V1 and V2, where
V1 is made of cosets in which the last coordinate in all tableaux in this
coset is a polynomial which contains a monomial xn−1 and V2 is made of
cosets in which the last coordinate in all tableaux are polynomials which
do not contain such a monomial. [Dn]n contains a monomial xn−1, thus
for every P n(2)v1 ∈ V1 and P n(2)v2 ∈ V2:
P n(2)v1 · Dn ∈ V2 and P n(2)v2 · Dn ∈ V1.
B. Pawlik 279
Hence for diagonal base D = {D1, . . . , Dn} we can obtain a Cayley
graph Cay(Pn(2)) from a graph Sch(Pn(2), D, P n(2)) by replacing every
vertex of Sch(Pn(2), D, P n(2)) by a graph Cay(Pn−1(2), D′) and replacing
every edge of Sch(Pn(2), D, P n(2)) by a set of corresponding edges between
elements Pn(2) due to generator Dn (see point 3 of above construction).
4. Cayley graphs of Pn(2) for small n
4.1. The case n = 2
Group P2(2) is isomorphic with the dihedral group D4. It has two
different diagonal bases and 12 different bases at all. The list of bases is
as follows:
B1 = D1 = {[1, 0], [0, x1]}, B2 = D2 = {[1, 0], [0, x1 + 1]},
B3 = {[1, 1], [0, x1]}, B4 = {[1, 1], [0, x1 + 1]},
B5 = {[1, 0], [1, x1]}, B6 = {[1, 0], [1, x1 + 1]},
B7 = {[1, 1], [1, x1]}, B8 = {[1, 1], [1, x1 + 1]},
B9 = {[0, x1], [1, x1]}, B10 = {[0, x1], [1, x1 + 1]},
B11 = {[0, x1 + 1], [1, x1]}, B12 = {[0, x1 + 1], [1, x1 + 1]}.
The only primal diagonal base in Pn(2) is B1. The action on the set of
all bases has 3 different orbits of length 4:
O1 = {D1, D2, B3, B4}, O2 = {B5, B6, B7, B8},
O3 = {B9, B10, B11, B12}.
The orbit O1 is the only D-orbit. Cayley graphs of P2(2) on bases from
O2 and O3 are isomorphic (Fig. 1).
Figure 1. Cayley graphs of P2(2) in bases from respective orbits.
280 The action of Sylow 2-subgroups. . .
4.2. The case n = 3
There are four different primal diagonal bases of P3(2):
D1 = {[1, 0, 0], [0, x1, 0], [0, 0, x1x2]},
D2 = {[1, 0, 0], [0, x1, 0], [0, 0, x1x2 + 1]},
D3 = {[1, 0, 0], [0, x1 + 1, 0], [0, 0, x1x2]},
D4 = {[1, 0, 0], [0, x1 + 1, 0], [0, 0, x1x2 + 1]},
Thus there are four different D-orbits and every such orbit contains exactly
four diagonal bases and exactly 60 bases, which are not diagonal. Schreier
coset graph Sch(P3(2), D, P 3(2)) on bases from orbits D-orbits have form
presented in Figure 2.
0 x1 x2 x1+x2+1 x1+x2 x2+1 x1+1 1
x1x2 x1x2+x1 x1x2+x2
x1x2+x1+x2+1
x1x2+x1+x2
x1x2+x2+1
x1x2+x1+1
x1x2+1
Figure 2. Sch(P3(2), D, P 3(2)), where D is a diagonal base (vertex indexed
by polynomials on last coordinate).
As we can see, Sch(P3(2), D, P 3(2)) is a 4-regular bipartite graph.
Every edge of this graph corresponds to connections with subgraphs
isomorphic to Cay(P2(2), D′) (i.e. undirected cycle on 8 vertices, see 5.1).
Every such connected cycles in Cay(P3(2), D) are connected by two edges
and form of connection depends of bases (Fig. 3)
Thus the length of the shortest cycle in graphs on bases D1 and D2 is
equal to 8, and length of the shortest cycle in graphs on bases D3 and D4
is equal to 4. This means that these Cayley graphs of P3(2) on diagonal
bases are not isomorphic.
B. Pawlik 281
Figure 3. Connections between subgraphs of Cay(P3(2), D) isomorphic with
Cay(P2(2), D′) for different diagonal bases.
References
[1] A. Bier, V. Sushchansky Kaluzhnin’s representations of Sylow p-subgroups of au-
tomorphism groups of p-adic rooted trees Algebra Discrete Math., 19:1 (2015),
19-38.
[2] D. Gorenstein, Finite Groups, Harper’s series in modern mathematics, Now York,
Harper & Row, 1968.
[3] R. I. Grigorchuk, V. V. Nekrashevych, V. I. Sushchanskii, Automata, Dynamical
Systems, and Groups, Proc. Steklov Inst. Math. v.231 (2000), 134-214
[4] L. Kaluzhnin, La structure des p-groupes de Sylow des groupes symetriques finis,
Ann. Sci. l’Ecole Norm. Sup. 65 (1948), 239–272.
[5] B. Pawlik, Involutive bases of Sylow 2-subgroups of symmetric and alternating
groups, Zesz. Nauk. Pol. Sl., Mat. Stos. 5 (2015), 35–42.
[6] V. Sushchansky, A. Słupik, Minimal generating sets and Cayley graphs of Sylow
p-subgroups of finite symmetric groups, Algebra Discrete Math., no. 4, (2009),
167–184.
Contact information
B. Pawlik Institute of Mathematics
Silesian University of Technology
ul. Kaszubska 23, 44-100 Gliwice, Poland
E-Mail(s): bartlomiej.pawlik@polsl.pl
Received by the editors: 10.04.2016
and in final form 30.05.2016.
|
| id | nasplib_isofts_kiev_ua-123456789-155248 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-12-07T18:55:30Z |
| publishDate | 2016 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Pawlik, B.T. 2019-06-16T14:38:23Z 2019-06-16T14:38:23Z 2016 The action of Sylow 2-subgroups of symmetric groups on the set of bases and the problem of isomorphism of their Cayley graphs / B.T. Pawlik // Algebra and Discrete Mathematics. — 2016. — Vol. 21, № 2. — С. 264–281. — Бібліогр.: 6 назв. — англ. 1726-3255 2010 MSC:20B35, 20D20, 20E22, 05C25. https://nasplib.isofts.kiev.ua/handle/123456789/155248 Base (minimal generating set) of the Sylow 2-subgroup of S₂n is called diagonal if every element of this set acts non-trivially only on one coordinate, and different elements act on different coordinates. The Sylow 2-subgroup Pn(2) of S₂n acts by conjugation on the set of all bases. In presented paper the~stabilizer of the set of all diagonal bases in Sn(2) is characterized and the orbits of the action are determined. It is shown that every orbit contains exactly 2n−1 diagonal bases and 2²n−²n bases at all. Recursive construction of Cayley graphs of Pn(2) on diagonal bases (n≥2) is proposed. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics The action of Sylow 2-subgroups of symmetric groups on the set of bases and the problem of isomorphism of their Cayley graphs Article published earlier |
| spellingShingle | The action of Sylow 2-subgroups of symmetric groups on the set of bases and the problem of isomorphism of their Cayley graphs Pawlik, B.T. |
| title | The action of Sylow 2-subgroups of symmetric groups on the set of bases and the problem of isomorphism of their Cayley graphs |
| title_full | The action of Sylow 2-subgroups of symmetric groups on the set of bases and the problem of isomorphism of their Cayley graphs |
| title_fullStr | The action of Sylow 2-subgroups of symmetric groups on the set of bases and the problem of isomorphism of their Cayley graphs |
| title_full_unstemmed | The action of Sylow 2-subgroups of symmetric groups on the set of bases and the problem of isomorphism of their Cayley graphs |
| title_short | The action of Sylow 2-subgroups of symmetric groups on the set of bases and the problem of isomorphism of their Cayley graphs |
| title_sort | action of sylow 2-subgroups of symmetric groups on the set of bases and the problem of isomorphism of their cayley graphs |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/155248 |
| work_keys_str_mv | AT pawlikbt theactionofsylow2subgroupsofsymmetricgroupsonthesetofbasesandtheproblemofisomorphismoftheircayleygraphs AT pawlikbt actionofsylow2subgroupsofsymmetricgroupsonthesetofbasesandtheproblemofisomorphismoftheircayleygraphs |