digraphs
Lack of detail in `DigraphHomomorphism` documentation
From Gordon Royle via the GAP forum:
I am using the GAP package “digraphs” to determine whether or not there is a homomorphism from a digraph d1 to a digraph d2 (in fact they are graphs, but that does not matter).
The actual two graphs that I am using are included at the bottom of this message for anyone wishing to replicate this behaviour, but the key point is that d1 has 16 vertices and d2 has 32.
When I issue the command
gap> DigraphHomomorphism(d1,d2);
Transformation( [ 1, 2, 3, 9, 7, 8, 4, 19, 6, 32, 30, 5, 18, 31, 29, 20, 17,
18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 ] )
the output is a Transformation, indicating that there is indeed a homomorphism from d1 to d2.
But why does the transformation have 32 entries, when d1 is a digraph with only 16 vertices?
Do I just take the first 16 entries as the actual transformation, and ignore the rest?
gap> Print(d1);
Digraph( [ [ 12, 2, 13, 3, 4, 5, 6, 7, 8, 9 ], [ 11, 1, 12, 13, 3, 14, 15, 5,
7, 9 ], [ 11, 1, 12, 2, 15, 6, 7, 8, 9, 10 ], [ 1, 12, 13, 14, 5, 16, 6, 7, 8,
10 ], [ 1, 2, 13, 14, 4, 15, 16, 7, 8, 9 ], [ 11, 1, 12, 13, 3, 4, 16, 8, 9,
10 ], [ 1, 2, 3, 4, 5, 8, 10, 12, 14, 15 ], [ 1, 3, 4, 15, 5, 16, 6, 7, 9, 10
], [ 11, 1, 2, 13, 3, 15, 5, 16, 6, 8 ], [ 11, 12, 3, 14, 4, 15, 16, 6, 7, 8 ]
, [ 12, 2, 13, 3, 14, 15, 16, 6, 9, 10 ], [ 11, 1, 2, 13, 3, 14, 4, 6, 7, 10 ]
, [ 11, 1, 12, 2, 14, 4, 5, 16, 6, 9 ], [ 2, 4, 5, 7, 10, 11, 12, 13, 15, 16 ]
, [ 11, 2, 3, 14, 5, 16, 7, 8, 9, 10 ], [ 11, 13, 14, 4, 15, 5, 6, 8, 9, 10 ]
] )
gap> Print(d2);
Digraph( [ [ 17, 18, 2, 19, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ],
[ 29, 1, 30, 31, 3, 4, 5, 6, 7, 10, 11, 12, 13, 18, 21, 22, 23, 24 ], [ 29, 1
, 30, 2, 32, 4, 5, 6, 8, 10, 11, 14, 15, 19, 21, 22, 25, 26 ], [ 17, 1, 2, 19,
3, 5, 23, 7, 24, 9, 27, 28, 12, 29, 13, 31, 32, 16 ], [ 1, 30, 2, 31, 3, 32,
4, 8, 9, 14, 15, 16, 17, 18, 25, 26, 27, 28 ], [ 17, 1, 18, 2, 19, 3, 20, 23,
7, 24, 8, 25, 26, 10, 11, 29, 30, 16 ], [ 29, 1, 2, 31, 4, 6, 9, 12, 13, 14, 1
5, 18, 19, 20, 21, 22, 27, 28 ], [ 1, 30, 3, 32, 5, 6, 9, 12, 13, 14, 15, 18,
19, 20, 21, 22, 27, 28 ], [ 17, 1, 18, 19, 20, 4, 5, 23, 7, 24, 8, 25, 26, 10,
11, 31, 32, 16 ], [ 17, 1, 2, 3, 20, 21, 22, 6, 23, 25, 9, 27, 28, 12, 14, 31
, 32, 16 ], [ 17, 1, 2, 3, 20, 21, 22, 6, 24, 9, 26, 27, 28, 13, 31, 15, 32, 1
6 ], [ 1, 30, 2, 32, 4, 7, 8, 10, 14, 15, 16, 20, 21, 23, 24, 25, 26, 28 ], [
17, 1, 2, 20, 4, 22, 23, 7, 24, 8, 25, 26, 27, 11, 30, 14, 15, 32 ], [ 29, 1,
31, 3, 5, 7, 8, 10, 12, 13, 16, 20, 22, 23, 24, 25, 26, 27 ], [ 29, 1, 31, 3,
5, 7, 8, 11, 12, 13, 17, 20, 21, 23, 24, 25, 26, 28 ], [ 29, 1, 30, 4, 5, 6, 9
, 10, 11, 12, 14, 20, 21, 22, 24, 26, 27, 28 ], [ 29, 1, 30, 4, 5, 6, 9, 10, 1
1, 13, 15, 20, 21, 22, 23, 25, 27, 28 ], [ 1, 30, 2, 31, 5, 6, 7, 8, 9, 20, 21
, 22, 23, 24, 25, 26, 27, 28 ], [ 1, 3, 20, 4, 21, 22, 23, 6, 24, 7, 8, 25, 9,
26, 27, 28, 29, 32 ], [ 29, 30, 31, 32, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1
6, 17, 18, 19 ], [ 2, 31, 3, 32, 7, 8, 10, 11, 12, 15, 16, 17, 18, 19, 23, 26,
27, 28 ], [ 2, 31, 3, 32, 7, 8, 10, 11, 13, 14, 16, 17, 18, 19, 24, 25, 27, 2
8 ], [ 30, 2, 32, 4, 6, 9, 10, 12, 13, 14, 15, 17, 18, 19, 21, 25, 26, 27 ], [
30, 2, 32, 4, 6, 9, 11, 12, 13, 14, 15, 16, 18, 19, 22, 25, 26, 28 ], [ 29, 3
1, 3, 5, 6, 9, 10, 12, 13, 14, 15, 17, 18, 19, 22, 23, 24, 28 ], [ 18, 19, 3,
21, 5, 6, 23, 24, 9, 27, 11, 12, 29, 13, 14, 31, 15, 16 ], [ 17, 18, 19, 4, 21
, 5, 22, 23, 7, 8, 26, 10, 11, 29, 13, 30, 14, 16 ], [ 29, 30, 4, 5, 7, 8, 10,
11, 12, 15, 16, 17, 18, 19, 21, 22, 24, 25 ], [ 30, 2, 31, 3, 32, 4, 6, 7, 14
, 15, 16, 17, 19, 20, 25, 26, 27, 28 ], [ 17, 18, 2, 3, 20, 5, 6, 23, 24, 8, 2
7, 28, 12, 29, 13, 31, 32, 16 ], [ 29, 30, 2, 32, 4, 5, 7, 9, 10, 11, 14, 15,
18, 20, 21, 22, 25, 26 ], [ 29, 30, 31, 3, 4, 5, 8, 9, 10, 11, 12, 13, 19, 20,
21, 22, 23, 24 ] ] )
Thankfully the transformation is a homomorphism. The problem is a misunderstanding about the way that transformations are displayed in GAP.
gap> d1 := DigraphFromGraph6String("O{uvt~lLrH}rvJUfl^Gzv");
gap> d2 := DigraphFromGraph6String(
> "_~~elYZxNHYYsqittXsxyfMjN_Dn??N~|b[}Wuvahn\\Id}qJLzfJJ|jBZZvGux|k\\_]o|lE\\KytrJeXr{Fw[");
gap> t := DigraphHomomorphism(d1, d2);;
Transformation( [ 1, 2, 3, 9, 7, 8, 4, 19, 6, 32, 30, 5, 18, 31, 29, 20, 17,
18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 ] )
gap> ForAll(DigraphEdges(d1), e -> IsDigraphEdge(d2, [e[1] ^ t, e[2] ^ t]));
true
gap> ForAll([17 .. 32], i -> i ^ t = i);
true
The transformation t is indeed a homomorphism, as shown by the first ForAll statement. However, since t maps 10 to 32, GAP displays t as a transformation of degree 32, even though it fixes the points 17, ..., 32, as shown by the second ForAll statement.
Yes, I replied to Gordon with this, I think it's a bug in the documentation of DigraphHomomorphism which doesn't really explain what the output is.