Information Technology Reference
In-Depth Information
3
Complementary Variable Symmetries
We say that a group G is generated by a set X if every element of G can
be written as product of elements of X and their inverses. For a great many
CSPs, each element of the symmetry group can be uniquely written as a single
value symmetry followed by a single variable symmetry. In this case we say that
the variable symmetries form a complement to the value symmetries in the full
symmetry group. Formally, a subgroup H 1 of a group H
is a complement to a
subgroup H 2 of H
if the following conditions hold:
1.
H 2 is a normal subgroup of H : this means that for all elements h ∈ H
the
set
{hh 2 :
h 2 ∈ H 2 }
is equal to the set
{h 2 h
:
h 2 ∈ H 2 }
.
2.
|H 1 ∩ H 2 |
=1.
3. The set
{h 1 h 2 : h 1 ∈ H 1 ,h 2 ∈ H 2 }
contains all elements of G .
Var
If this is true for a CSP with symmetry group G
when
H 1 is
G
and H 2 is
Val then the CSP has complementary variable symmetry .
This holds, for instance, for any CSP where G is generated by pure value
symmetries and pure variable symmetries. For example, in a graph colouring
problem, the symmetries are generated by relabelling of the colours (pure value
symmetries) and the automorphism group of the graph (pure variable symme-
tries).
Before going further, we collect a few facts describing the way in which the
variable and value symmetries interact.
G
Lemma 1. If G is generated by a collection of pure variable symmetries and
some value symmetries, then G
Val
is a normal subgroup of G .
Proof. To show that G
Val
is a normal subgroup of G , we show that for all g ∈ G
and all h ∈ G
Val , the symmetry g 1
hg ∈ G
Val .
Val and let g ∈ G .Then g is a product of variable and value
symmetries. Consider the literal ( X i = α ij ) g 1
Let
h ∈ G
hg . The image of a literal ( X k =
α kl ) under each variable symmetry in g depends only on k , not on l ,andeach
value symmetry fixes the variables in each literal. Therefore as we move through
the symmetries that make up g 1 , we will map X i to various other variables,
but each of these mappings will be inverted as we apply each of the symmetries
that make up g .Thus( X i = α ij ) g 1
hg =( X i = α ij )forsome j ,andso g 1
hg
is a value symmetry.
Val
We note that if
G contains any non-pure variable symmetries then G
is
Var
not, in general, a normal subgroup. Suppose that g ∈ G
maps ( X i = α ij )
Val
( X k
=
α kj ), and also maps ( X i
=
α ij 1 )
( X l
=
α lj 1 ). Let
g ∈ G
map
( X i = α ij )
( X i = α ij 1 ). Then
( X k = α kj ) g 1
hg =( X i = α ij ) hg
=( X i = α ij 1 ) g
=( X l = α lj 1 ) ,
but the map ( X k = α kj )
( X l = α lj 1 ) is clearly not a value symmetry.
Search WWH ::




Custom Search