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