[GAP Forum] DigraphsHomomorphisms

[James Mitchell]

Dear Gordon,

The short answer is: yes, you can ignore the trailing fixed values, they do not relate to the homomorphism that Digraphs has found. 

The longer answer is that transformations are defined on the entire natural numbers in GAP (much like permutations are), and are taken to fix all values larger than their degree. The degree is defined to be the largest value such that n ^ f <> n or i ^ f = n for some i <> n. So, the reason that the fixed values [17 .. 32] are included in the display of the transformation found by Digraphs is that 10 is mapped to 32.

Probably we should improve the part of the Digraphs manual describing DigraphHomomorphism to include a more accurate description of what the function returns.

Best wishes,

James


> On 5 Apr 2018, at 13:23, Gordon Royle <gordon.royle at uwa.edu.au> wrote:
> 
> 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?
> 
> 
> Thanks
> 
> Gordon
> 
> 
> 
> 
> 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 ] ] )
> _______________________________________________
> Forum mailing list
> Forum at gap-system.org
> https://mail.gap-system.org/mailman/listinfo/forum