Information Technology Reference
In-Depth Information
The main idea behind the proof is the following: Consider an instances of graph
isomorphism where we want to check whether the graphs
X
and
Y
are isomorphic.
We assume they are connected and have
n
vertices. For a prime
p
, consider the graph
Z
which is the disjoint union of
p
−
1 copies of
X
and 1 copy of
Y
. Suppose that
has a
p
-cycle say
g
. Consider any vertex
u
of
Z
such that
u
g
⃒=
the group Aut
u
.
It is easy to see that the orbit of
u
under the cyclic group generated by
g
has to
have
p
-elements. Furthermore, if any two of the elements in this orbit is in the same
connected component of
Z
then the entire orbit is. If the prime
p
is chosen to be
greater than
n
then such a
p
-cycle necessarily has to permutes the components as
each of the connected components of
Z
are of cardinality at most
n
(
Z
)
p
.Thisis
only possible if some copy of
X
in
Z
is mapped to the copy of
Y
and hence
X
and
Y
have to be isomorphic. Conversely, for any prime
p
,if
X
and
Y
are isomorphic, then
the group Aut
<
has a
p
-cycle. Thus, to decide whether
X
and
Y
are isomorphic,
we need to check the group representability of the additive group of
(
Z
)
,onthe
graph
Z
for some prime
p
greater than the number of vertices in
X
. By Bertrand's
postulate (it is actually a theorem but the name seems to be stuck) there is always a
prime
p
between
n
and 2
n
which we chose for this purpose.
Notice that for the previous lemma, all we needed is to pick a prime
p
such that
Aut
Z
/
p
Z
does not have
p
-cycle. Recall that tournaments have odd order automor-
phism group and hence we have the following result.
(
X
)
Z
/
Z
Theorem 7.4
Tournament isomorphism is reducible to
2
representability.
In this context, we have the following open problem.
Open problem 7.5
Is graph isomorphism reducible to
Z
/
2
Z
-representability (or
for that matter any fixed group representability).
What about the other direction, i.e. reduction from representability to isomor-
phism? Dutta and Kurur [
DK09
] prove the following result for solvable group rep-
resentability.
Lemma 7.6
(Dutta and Kurur)
The representability problem for solvable groups is
polynomial-time Turing reducible to graph isomorphism.
For a group
G
,let
G
be the commutator subgroup. The main idea is the following
group theoretic fact.
Lemma 7.7
A solvable group G is representable on X if and only if there is a prime
p that divides both the orders G
G
and
#Aut
/
(
X
)
.
From the above lemma it follows that to check representability for solvable groups,
all we need is a way to compute the orders #
G
G
and that of #Aut
. Clearly
the former can be computed easily as the group is presented as a multiplication
table and the latter using an oracle to the automorphism problem (or equivalently the
graph isomorphism problem). We can even assume that the group is presented as a
permutation group because there are efficient algorithms to compute the commutator
subgroup of a permutation group [
FHL80
, Theorem 4].
/
(
X
)
