Information Technology Reference
In-Depth Information
ʲ
ʲ 1 ʲ 2 both of which are H -stable then
3.
Suppose
is the disjoint union
(
H g,ʲ) =
(
(
H g,ʲ 1 ) ,ʲ 2 )
CP
CP
CP
.
is a coset (item 2 in the above lemma) because we
can then succinctly represent the set by giving a generating set of CP
It is crucial that CP
(
H g,ʲ)
(
H
,ʲ)
and the
coset representative.
We are now ready to give the outline of the divide and conquer algorithm for
computing CP
(
H g,ʲ)
.
ʲ
Reduction to transitive case Let
ʲ
be any H -orbit. We first compute the
group CP H g,ʲ which is the transitive case of the above problem. Let
ʲ =
CP CP H g,ʲ .
Transitive case For this case H acts transitively on
ʲ ʲ . We use the fact that CP
(
H g,ʲ) =
ʲ
.Let
be a maximal H -block of
H and let
be the associated block system. Let N be the normal
subgroup of H that fixes all the blocks
B() ={ 1 ,..., k }
B()
setwise. Then we have H
=∧ x Nx as
a disjoint union of cosets of N . We can then compute the set CP
(
H g,ʲ)
by taking
the union of all the cosets CP
(
Nx g,ʲ)
which are not empty.
If the number of cosets Nx are polynomially bounded then we can compute a
generating set for N using Lemma 11.3.5. It then amounts to recursively computing
the polynomially many cosets CP
and combining the nonempty ones. The
number of cosets Nx that is considered in the transitive case is the same as the order
of the quotient group H
(
Nx g,ʲ)
/
N . Since the block
that we choose is the maximal block,
the quotient group H
, is a primitive group
(See Sect. 2.1 ) . Thus, we need a bound on the size of a primitive permutation group.
While the order of a primitive permutation group on n elements can be exponential
in n , consider the case of the primitive group S n for example, for solvable primitive
permutation groups, a result by Pálfy [ Pál82 , Theorem 1] gives us the polynomial
bound we are looking for.
/
N , as a permutation group on the set
B()
Theorem 4.3 (pálfy) There are absolute constants C and c such that any solvable
primitive permutation group on
c .
ˇ
·
ˇ
is of size less than C
#
The above bound has a generalisation to groups with bounded non-abelian compo-
sition factors: Let
d denote the class of groups such that each composition factor is
either abelian or is isomorphic to a subgroup of S d . Babai et al. [ BCP82 ] generalised
the Pálfy's bound to the class
d .
Theorem 4.4 (Babai, Cameron and pálfy) There are absolute constants C and c
such that for any positive integer d, any primitive permutation group on
ˇ
in the
cd .
class
d is of size less than C #
ˇ
As a result, the colour preserving subgroup problem is solvable in polynomial-
time for groups that are in the class
d .
Lemma 4.5 Colour preserving subgroup problem is solvable in polynomial-time for
the class of solvable groups and the class of groups in the family
d for constant d.
Search WWH ::




Custom Search