Information Technology Reference
In-Depth Information
ˇ
1
to be less than that of
ˇ
2
above chosen order, then we set every element of
⃐
under the new ordering
. The motivation of this reordering is the following: Let
ˇ
=
ˇ
1
∧
ˇ
2
then computing the lexicographically least element with respect to
the new ordering
can be done by first computing the lexicographically minimal
elements with respect to the restriction of
⃐
ˇ
1
and then from them picking the
lexicographically least element with respect to the restriction of
⃐
on
ˇ
2
.
Ordering within orbits
When
G
is transitive, we do the reordering with respect to
the blocks. We pick a maximal
G
-block
⃐
on
in a canonical way. The
block system
partition the set
ˇ
so reorder it pretty much the same way as in the previous case
using the
block system instead. If
N
denotes the normal subgroup of
G
that fixes
all the blocks in the
block system, we can recursively find the lex-least elements
in double cosets
N
g
xH
and find the minimal ones out of it. If
G
is in the class
d
,
the number of subproblems are polynomially bounded by Theorem 11.4.4.
The above reordering can be formalised in terms of the
structure forest
of the group
G
. The structure forest is the collection of
structure trees
one for each
G
-orbit. For an
orbit
ʲ
, the structure tree is a tree where the leaves are elements of
ʲ
. Each internal
node
v
is associated with a
G
-block
v
with the following properties.
1. For any child
u
of
v
,the
G
-block
u
is a maximal block contained in
v
.
2. If
{
u
1
,...,
u
k
}
are the set of children of
v
then the blocks
u
i
's are all conjugates
v
.
This structure forest captures the divide and conquer on
G
. The elements of
of each other and partition the parent block
ˇ
can be reordered once we compute the structure forest of
G
: The structure trees
are ordered in the order of the least element in them. For each internal node
v
and
children
u
1
and
u
2
,
u
1
u
2
if the least element of the associated block in
u
1
is
smaller than that of
u
2
according to the original ordering
⃐
<
. This will finally give an
ordering
. Thus, we have the following theorem (See the survey
article by Luks [
Luk93
] for details).
⃐
on the entire set
ˇ
Theorem 5.7
Given a totally ordered set
ˇ
, permutation groups G and H on
ˇ
and a permutation x on
ˇ
. Suppose G is in the class
d
then in time polynomial in
n we can compute a new ordering
∃
G
such that computing the lex-least element of
the double coset G x H can be done in n
O
(
d
)
.
Notice that we do not have any restriction whatsoever on the group
H
.
11.6 Structure of Primitive Groups
In the last two sections, we saw how bounds on the order of primitive permutation
group can be crucial in the runtime analysis of various divide and conquer algo-
rithms for permutation groups. We now mention how knowing the actual structure
of primitive groups are computationally useful. This section is mainly motivated by
the study of
bounded colour class graph isomorphism problem
.
