gap> # gap> # ===================================================================== gap> # gap> # gap> # Libraries of groups in GAP gap> # -------------------------- gap> # gap> # gap> # GAP provides many built-in functions (such as MathieuGroup) and gap> # extensive data libraries to provide groups of many different types, gap> # such as groups of "small" order, currently all transitive permutation gap> # groups of degree < 32, and currently all primitive permutation groups gap> # of degree < 4096. gap> # gap> # gap> # See ?Group Libraries and related documentation for full details. gap> # gap> # gap> # (Recall that if G is a permutation group on [1..n], then G gap> # is *transitive* if it has just one orbit on [1..n], and G gap> # is *primitive* if n>1, G is transitive, and G fixes no partition gap> # of [1..n] other than those consisting of just one part or of gap> # n parts.) gap> # gap> # gap> # Examples gap> # -------- gap> # gap> G:=AllSmallGroups(Size,20,IsAbelian,false); [ , , ] gap> G:=AllTransitiveGroups(NrMovedPoints,[11,12],Size,[60..6000],IsSolvable,false); [ L(11)=PSL(2,11)(11), A_5(12), S_5(12), L(6)[x]2, [2]L(6)_6, L(6):2[x]2, [2]L(6):2_12, L(2,11), A(6)[x]2, M_10(12)=[A_6[1/360]{M_10}A_6]2_2, PGL(2,9)(12)=[A_6[1/360]{M_10}A_6]2, S_6(12), PGL(2,11), S(6)[x]2, M_10.2(12)=A_6.E_4(12)=[S_6[1/720]{M_10}S_6]2, [2^5]L(6), [2^6]L(6)=2wrL(6), 1/2[2^6]L(6):2, [2^5]L(6):2 ] gap> G:=OnePrimitiveGroup(NrMovedPoints,100,IsSimple,true); J_2 gap> Size(G); 604800 gap> G:=CyclicGroup(20); gap> IsPermGroup(G); false gap> G:=CyclicGroup(IsPermGroup,20); Group([ (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) ]) gap> IsPermGroup(G); true gap> G:=SymmetricGroup([1..7]); Sym( [ 1 .. 7 ] ) gap> H:=AlternatingGroup([1..7]); Alt( [ 1 .. 7 ] ) gap> IsSubgroup(G,H); true gap> # gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # List, Filtered, First, Number, ForAll, ForAny gap> # --------------------------------------------- gap> # gap> # gap> # Let L be a (dense) list, and let f be a one-argument function, gap> # defined on the elements of L. gap> # gap> # Then List(L, f) returns a new list, obtained by applying f to gap> # each element of L. gap> # gap> # gap> # Now suppose f is a boolean function (so returns true or false). gap> # gap> # Then: gap> # gap> # Filtered(L, f) returns a new list, whose elements are those gap> # of L on which f returns true (in the same order as in L). gap> # gap> # First(L, f) returns the first element of L on which f returns gap> # true. If there is no such element, then First(L, f) returns fail. gap> # gap> # Number(L, f) returns the number of elements of L on which f gap> # returns true. gap> # gap> # ForAll(L, f) returns true iff f returns true on every gap> # element of L. gap> # gap> # ForAny(L, f) returns true iff f returns true on some gap> # element of L. gap> # gap> # gap> # Examples gap> # -------- gap> # gap> L:=[4,-3,0,1,4,2,-2]; [ 4, -3, 0, 1, 4, 2, -2 ] gap> A:=List(L,increment); [ 5, -2, 1, 2, 5, 3, -1 ] gap> ForAll(A,x->x > -1); false gap> ForAll(A,x->x <= 5); true gap> Number(A,x->x = 5); 2 gap> Number(A,IsPosInt); 5 gap> ForAny(A,x->x = 0); false gap> ForAny(L,x->x = 0); true gap> F:=Filtered(L,x->x >= 2); [ 4, 4, 2 ] gap> First(L,x->x < 0); -3 gap> First(L,x->x > 4); fail gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Some functions for Schreier vectors gap> # ----------------------------------- gap> # gap> # gap> # Here we present some user-defined functions to create and make gap> # use of Schreier vectors. Schreier vectors are fundamental to gap> # the data structure used by the GRAPE package to store graphs. gap> # gap> # gap> # For our purposes, a *Schreier vector* sch with respect to gap> # a generating list gens for a permutation group G on [1..n] gap> # is a length n list of non-zero integers, specifying a list of gap> # rooted spanning trees (called *Schreier trees*) corresponding gap> # to the orbits of G on [1..n], as follows: gap> # gap> # - if sch[i] = -k < 0, then i the root of the k-th spanning tree gap> # and is the chosen representative for the k-th orbit of G gap> # gap> # - if sch[i] = k > 0 then i = j^gens[k], where j is the gap> # parent of i in its spanning tree. gap> # gap> # gap> SchreierVector := function(gens,n) > # > # Suppose gens is a list of permutations of [1..n], and > # let G be the (permutation) group generated by gens. > # Then this function returns a Schreier vector for the orbits > # of G on [1..n], with respect to the generating list gens. > # > local sch,orb,orbnum,i,j,k,im; > if not IsList(gens) or not IsInt(n) then > Error("usage: SchreierVector( , )"); > fi; > if LargestMovedPoint(gens)>n then > Error(" must be a list of permutations of [1..]"); > fi; > sch:=[]; > for i in [1..n] do > sch[i]:=0; > od; > orbnum:=0; # number of orbits found so far > for i in [1..n] do > if sch[i]=0 then > # new orbit > orbnum:=orbnum+1; > sch[i] := -orbnum; > # This signifies that i is the root of the > # Schreier tree for the orbnum-th orbit. > # > # Now make the orbit of i and its Schreier vector entries. > # > orb:=[i]; > for j in orb do > for k in [1..Length(gens)] do > im:=j^gens[k]; > if sch[im]=0 then > # new point im in the orbit of i, obtained > # by appyling the k-th generator to j. > sch[im]:=k; > Add(orb,im); > fi; > od; > od; > fi; > od; > return sch; > end; function( gens, n ) ... end gap> gap> RepWord := function(gens,sch,r) > # > # Given a list gens of permutation group generators, > # and a Schreier vector sch made made w.r.t. gens, > # this function returns a record containing the representative > # for the orbit containing r (w.r.t. sch), and a "word" in > # gens taking this representative to r. > # > # We assume that r <= Length(sch). > # > local word,w; > word:=[]; > w:=sch[r]; > # > # Now trace back to the root of the spanning tree containing r. > # > while w > 0 do > Add(word,w); > r:=r/gens[w]; # efficient way of obtaining r^(gens[w]^(-1)) > w:=sch[r]; > od; > return rec(word:=Reversed(word), representative:=r); > end; function( gens, sch, r ) ... end gap> gap> GG; gap> n:=LargestMovedPoint(GG); 51 gap> gens:=GeneratorsOfGroup(GG); [ (1,17,4)(2,37,10,3,36,11)(5,19,23,6,18,24)(7,40,30,9,38,32)(8,39,31)(12,22, 43,14,20,45)(13,21,44)(15,42,49,16,41,50)(25,27)(28,47,33,29,46,34)(35,48, 51), (1,36,41,22)(2,37,20,40)(3,17,38,42)(4,43,48,9)(5,44,28,27)(6,23,46, 29)(7,45)(8,24,25,47)(10,49,35,14)(11,30,51,16)(12,50,15,32)(13,31,33, 34)(18,39,21,19) ] gap> sch:=SchreierVector(gens,n); [ -1, 1, 2, 1, -2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, -3, 2, 2, 2, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 2, 1, 1, 2 ] gap> RepWord(gens,sch,16); rec( representative := 1, word := [ 1, 2, 2, 1, 1 ] ) gap> RepWord(gens,sch,26); rec( representative := 26, word := [ ] ) gap> RepWord(gens,sch,36); rec( representative := 1, word := [ 2 ] ) gap> RepWord(gens,sch,46); rec( representative := 5, word := [ 1, 1, 2 ] ) gap> gap> # gap> # ===================================================================== gap> # gap> # gap> # The GRAPE package gap> # ----------------- gap> # gap> LoadPackage("grape"); ───────────────────────────────────────────────────────────────────────────── Loading GRAPE 4.8.3 (GRaph Algorithms using PErmutation groups) by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~lsoicher/). Homepage: https://gap-packages.github.io/grape Report issues at https://github.com/gap-packages/grape/issues ───────────────────────────────────────────────────────────────────────────── true gap> # gap> # The GRAPE package for GAP provides functionality for graphs, and gap> # is designed primarily for applications in algebraic graph theory, gap> # permutation group theory, design theory, and finite geometry. gap> # gap> # In general, GRAPE deals with finite directed graphs, which may gap> # have loops, but have no multiple edges. gap> # gap> # For the mathematical purposes of GRAPE, a *graph* consists of gap> # a finite set of *vertices*, together with a set of ordered pairs gap> # of vertices called *edges*. gap> # gap> # An edge [x,y] in a graph is a *loop* if x=y. gap> # gap> # A graph is *simple* if it has no loops and whenever [x,y] gap> # is an edge, then so is [y,x]. A simple graph can thus be gap> # considered to be a finite undirected graph having no loops gap> # and no multiple edges. gap> # gap> # Many (of the most important) GRAPE functions only work for simple gap> # graphs, but these functions will check if an input graph is simple. gap> # gap> # Graphs gamma and delta are *isomorphic* if there is an gap> # *isomorphism* from gamma to delta, that is, a bijection phi gap> # from the vertex-set of gamma to that of delta, such that, gap> # if v,w are vertices of gamma then [v,w] is an edge gap> # of gamma iff [v^phi,w^phi] is an edge of delta. gap> # gap> # An *automorphism* of a graph gamma is an isomorphism gap> # from gamma to itself. The set of all automorphisms of gap> # gamma forms a group of permutations of the vertices of gap> # gamma, called the *automorphism group* of gamma. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # In GRAPE, a graph always comes with an associated group gap> # ------------------------------------------------------- gap> # gap> # This is an important and fundamental feature of GRAPE. gap> # gap> # Part of the (record) structure of a graph gamma in GRAPE is gap> # a subgroup gamma.group of the automorphism group of gamma. gap> # This group is usually set by GRAPE when the graph is constructed, gap> # but may also be specified by the user. The group gamma.group gap> # is used by GRAPE to store the graph gamma compactly, to gap> # speed up computations with gamma, and can affect the output gap> # of certain GRAPE functions. gap> # gap> # Often, but not always, gamma.group is the full automorphism gap> # group of gamma. To change the group associated with a graph gap> # in GRAPE, it is required to construct a new graph (using the gap> # function NewGroupGraph). gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The structure of a graph in GRAPE gap> # --------------------------------- gap> # gap> # gap> # In GRAPE, a graph gamma is stored as a record, with mandatory gap> # components isGraph, order, group, schreierVector, gap> # representatives, and adjacencies. Usually, the user need not be gap> # aware of this record structure, and is strongly advised only to use gap> # GRAPE functions to construct and modify graphs. gap> # gap> # The isGraph component is set to true to specify that the record gap> # is a GRAPE graph. gap> # gap> # The order component contains the number of vertices of gamma. gap> # The vertices of gamma are always 1,2,...,gamma.order, but they gap> # may also be given names, either by a user (using AssignVertexNames) gap> # or by a function constructing a graph (e.g. Graph, InducedSubgraph, gap> # BipartiteDouble, QuotientGraph). The names component, if present, gap> # records these names, with gamma.names[i] the name of vertex i. gap> # If the names component is not present, then the names are taken to gap> # be 1,2,...,gamma.order. gap> # gap> # The group component records the GAP permutation group associated with gap> # gamma. This group must be a subgroup of the automorphism group of gamma. gap> # gap> # The representatives component records a set of orbit representatives gap> # for the action of gamma.group on the vertices of gamma, with gap> # gamma.adjacencies[i] being the set of vertices (out)adjacent to gap> # gamma.representatives[i]. gap> # gap> # GeneratorsOfGroup(gamma.group) and the schreierVector component gap> # are used to compute the (out)adjacency-set of a given vertex gap> # of gamma. (If x is a vertex of gamma and g is in gamma.group, gap> # such that x = gamma.representatives[i]^g, then the set of vertices gap> # (out)adjacent to x is the g-image of gamma.adjacencies[i].) gap> # gap> # The only mandatory component which may change once a graph is initially gap> # constructed is adjacencies (when an edge-orbit of gamma.group is gap> # added to, or removed from, gamma). gap> # gap> # A graph record may also have some of the optional components gap> # isSimple, autGroup, maximumClique, minimumVertexColouring, and gap> # canonicalLabelling, which record information about that graph. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Simple GRAPE example gap> # -------------------- gap> # gap> # gap> Petersen := Graph( SymmetricGroup([1..5]), > Combinations([1..5],2), OnSets, > function(x,y) return Intersection(x,y)=[]; end, > true ); rec( adjacencies := [ [ 8, 9, 10 ] ], group := Group([ (1,5,8,10,4)(2,6,9,3,7), (2,5)(3,6)(4,7) ]), isGraph := true, names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10, representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 ] ) gap> Vertices(Petersen); [ 1 .. 10 ] gap> VertexNames(Petersen); [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ] gap> DirectedEdges(Petersen); [ [ 1, 8 ], [ 1, 9 ], [ 1, 10 ], [ 2, 6 ], [ 2, 7 ], [ 2, 10 ], [ 3, 5 ], [ 3, 7 ], [ 3, 9 ], [ 4, 5 ], [ 4, 6 ], [ 4, 8 ], [ 5, 3 ], [ 5, 4 ], [ 5, 10 ], [ 6, 2 ], [ 6, 4 ], [ 6, 9 ], [ 7, 2 ], [ 7, 3 ], [ 7, 8 ], [ 8, 1 ], [ 8, 4 ], [ 8, 7 ], [ 9, 1 ], [ 9, 3 ], [ 9, 6 ], [ 10, 1 ], [ 10, 2 ], [ 10, 5 ] ] gap> UndirectedEdges(Petersen); [ [ 1, 8 ], [ 1, 9 ], [ 1, 10 ], [ 2, 6 ], [ 2, 7 ], [ 2, 10 ], [ 3, 5 ], [ 3, 7 ], [ 3, 9 ], [ 4, 5 ], [ 4, 6 ], [ 4, 8 ], [ 5, 10 ], [ 6, 9 ], [ 7, 8 ] ] gap> Adjacency(Petersen,5); [ 3, 4, 10 ] gap> Diameter(Petersen); 2 gap> Girth(Petersen); 5 gap> GlobalParameters(Petersen); [ [ 0, 0, 3 ], [ 1, 0, 2 ], [ 1, 2, 0 ] ] gap> autgrp:=AutomorphismGroup(Petersen); Group([ (2,5)(3,6)(4,7), (2,3)(5,6)(9,10), (3,4)(6,7)(8,9), (1,2)(6,8)(7,9) ]) gap> Size(autgrp); 120 gap> CliqueNumber(Petersen); 2 gap> CliqueNumber(ComplementGraph(Petersen)); 4 gap> ChromaticNumber(Petersen); 3 gap> Petersen; rec( adjacencies := [ [ 8, 9, 10 ] ], autGroup := Group([ (2,5)(3,6)(4,7), (2,3)(5,6)(9,10), (3,4)(6,7)(8,9), (1,2)(6,8)(7,9) ]), group := Group([ (1,5,8,10,4)(2,6,9,3,7), (2,5)(3,6)(4,7) ]), isGraph := true, isSimple := true, maximumClique := [ 1, 8 ], minimumVertexColouring := [ 1, 1, 2, 3, 1, 2, 3, 2, 3, 2 ], names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], order := 10, representatives := [ 1 ], schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 ] ) gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The function Graph in GRAPE gap> # ----------------------------- gap> # gap> # This is the most general and useful way of constructing a graph gap> # in GRAPE. gap> # gap> # If you learn just one GRAPE function to construct graphs, this is it! gap> # gap> # A call to this function has the form gap> # gap> # Graph( G, L, act, rel ) gap> # gap> # The parameter L should be a list of elements of a set S on which gap> # the group G acts, with the action given by the function act. gap> # The parameter rel should be a boolean function defining a gap> # G-invariant relation on S (so that for g in G, x,y in S, gap> # rel(x,y) if and only if rel(act(x,g),act(y,g))). gap> # gap> # Then the function Graph returns a graph gamma which has as gap> # vertex-names (an immutable copy of) gap> # gap> # Concatenation( Orbits( G, L, act ) ), gap> # gap> # and for vertices v,w of gamma, [v,w] is a (directed) edge gap> # if and only if gap> # gap> # rel( VertexName( gamma, v ), VertexName( gamma, w ) ). gap> # gap> # There is an additional optional (boolean) parameter, invt gap> # (default: false), which if set to true asserts that gap> # L is invariant under G with respect to action act, and gap> # then the function Graph behaves as above, except that gap> # the vertex-names of gamma become (an immutable copy of) L. gap> # gap> # The group associated with the graph gamma returned is the gap> # image of the action homomorphism for G acting via act on gap> # VertexNames(gamma). gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Peter Cameron's construction of the Hoffman-Singleton graph gap> # ----------------------------------------------------------- gap> # gap> # See [PJC, Section 3.6]. gap> # gap> projectiveplane:=Set(Orbit(Group((1,2,3,4,5,6,7)),[1,2,4],OnSets)); [ [ 1, 2, 4 ], [ 1, 3, 7 ], [ 1, 5, 6 ], [ 2, 3, 5 ], [ 2, 6, 7 ], [ 3, 4, 6 ], [ 4, 5, 7 ] ] gap> gap> OnSetsRecursive:=function(x,g) > if not IsList(x) then > return x^g; > else > return Set(List(x,y->OnSetsRecursive(y,g))); > fi; > end;; gap> gap> HoffmanSingletonAdjacency := function(x,y) > # > # This boolean function returns true iff vertices x and y > # are adjacent in the Hoffman-Singleton graph, in Peter Cameron's > # construction. > # > if Size(x)=3 then # x is a 3-set > if Size(y)=3 then # y is a 3-set > return Intersection(x,y)=[]; > else # y is a projective plane > return x in y; # join iff x is a line of y > fi; > else # x is a projective plane > if Size(y)=3 then # y is a 3-set > return y in x; # join iff y is a line of x > else # y is a projective plane > return false; # don't join > fi; > fi; > end;; gap> gap> HoffmanSingleton := Graph( AlternatingGroup([1..7]), > [[1,2,3], projectiveplane], > OnSetsRecursive, > HoffmanSingletonAdjacency);; gap> gap> Diameter(HoffmanSingleton); 2 gap> Girth(HoffmanSingleton); 5 gap> Size(HoffmanSingleton.group); 2520 gap> autgrp := AutomorphismGroup(HoffmanSingleton);; gap> Size(autgrp); 252000 gap> HoffmanSingleton := NewGroupGraph(autgrp,HoffmanSingleton);; gap> Size(HoffmanSingleton.group); 252000 gap> DisplayCompositionSeries(HoffmanSingleton.group); G (7 gens, size 252000) | Z(2) S (3 gens, size 126000) | 2A(2,5) = U(3,5) 1 (0 gens, size 1) gap> CliqueNumber(HoffmanSingleton); 2 gap> CliqueNumber(ComplementGraph(HoffmanSingleton)); 15 gap> ChromaticNumber(HoffmanSingleton); 4 gap> # gap> # ===================================================================== gap> # gap> # EdgeOrbitsGraph gap> # --------------- gap> # gap> # A common way to construct a graph in GRAPE is via the gap> # function EdgeOrbitsGraph. gap> # gap> # Where n is a non-negative integer, G is a permutation group on gap> # [1..n], and edges is a list of ordered pairs of elements of gap> # [1..n], the function call gap> # gap> # EdgeOrbitsGraph( G, edges, n ) gap> # gap> # gap> # returns the (directed) graph with vertex-set [1..n], and gap> # edge-set the union of the G-orbits of the ordered pairs in edges gap> # The group associated with the returned graph is G. gap> # gap> # The parameter n may be omitted, in which case n is taken gap> # to be the largest point moved by G. gap> # gap> # Note also that G may be the trivial permutation group Group( () ), gap> # in which case the (directed) edges of the returned gap> # graph are precisely those in the list edges. gap> # gap> # gap> # Example gap> # ------- gap> # gap> C:=EdgeOrbitsGraph(Group((1,2,3,4,5)),[[1,2]]); rec( adjacencies := [ [ 2 ] ], group := Group([ (1,2,3,4,5) ]), isGraph := true, isSimple := false, order := 5, representatives := [ 1 ], schreierVector := [ -1, 1, 1, 1, 1 ] ) gap> IsSimpleGraph(C); false gap> C:=EdgeOrbitsGraph(Group((1,2,3,4,5)),[[1,2],[2,1]]); rec( adjacencies := [ [ 2, 5 ] ], group := Group([ (1,2,3,4,5) ]), isGraph := true, order := 5, representatives := [ 1 ], schreierVector := [ -1, 1, 1, 1, 1 ] ) gap> IsSimpleGraph(C); true gap> C:=EdgeOrbitsGraph(Group((1,2,3,4,5)),[[1,2],[2,1],[2,2]]); rec( adjacencies := [ [ 1, 2, 5 ] ], group := Group([ (1,2,3,4,5) ]), isGraph := true, isSimple := false, order := 5, representatives := [ 1 ], schreierVector := [ -1, 1, 1, 1, 1 ] ) gap> IsSimpleGraph(C); false gap> G:=AllPrimitiveGroups(NrMovedPoints,275,Size,2025*443520*2); [ McL:2 ] gap> G:=G[1]; McL:2 gap> H:=Stabilizer(G,1); gap> orbs:=List(Orbits(H,[1..275]),Set);; gap> List(orbs,Length); [ 1, 112, 162 ] gap> y:=First(orbs,x->Length(x)=112)[1]; 2 gap> McLaughlin:=EdgeOrbitsGraph(G,[[1,y]]);; # the McLaughlin graph gap> VertexDegrees(McLaughlin); [ 112 ] gap> IsSimpleGraph(McLaughlin); true gap> # gap> # gap> # For some other useful GRAPE functions to construct graphs, see gap> # ?CayleyGraph, ?JohnsonGraph, and ?HammingGraph. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Automorphism groups and isomorphism testing in GRAPE gap> # ---------------------------------------------------- gap> # gap> # gap> # GRAPE contains functionality to test graph isomorphism and to gap> # calculate the automorphism group of a graph. This functionality gap> # can also be applied to graphs with colour classes gap> # (see ?Graphs with colour classes). gap> # gap> # gap> # To do all this, by default GRAPE uses its included version of gap> # B.D. McKay's nauty package. A user may instead choose to have gap> # GRAPE use their own installed copy of T. Juntilla's and P. Kaski's gap> # bliss package. The GRAPE interfaces to these packages are seamless gap> # and transparent to the user. gap> # gap> # gap> # As we have seen, where gamma is a graph in GRAPE, the function call gap> # gap> # AutomorphismGroupGraph( gamma ) gap> # gap> # returns the automorphism group of gamma, which can then be gap> # studied using the permutation group functionality in GAP. gap> # gap> # gap> # Where gamma and delta are graphs in GRAPE, the function call gap> # gap> # GraphIsomorphism( gamma, delta ) gap> # gap> # returns a permutation giving an isomorphism from gamma to delta gap> # if these graphs are isomorphic, and returns the special boolean gap> # value fail if the graphs are not isomorphic, whereas gap> # gap> # IsIsomorphicGraph( gamma, delta ) gap> # gap> # returns true if the graphs are isomorphic, and false otherwise. gap> # gap> # gap> # When comparing more than two graphs for pairwise isomorphism, gap> # you should use the function GraphIsomorhismClassRepresentatives. gap> # gap> # Where L is a list of graphs in GRAPE, the function call gap> # gap> # GraphIsomorphismClassRepresentatives( L ) gap> # gap> # returns a list consisting of pairwise non-isomorphic elements gap> # of L (in some order), representing all the isomorphism classes gap> # of elements of L. gap> # gap> # gap> # Examples gap> # -------- gap> # gap> J:=JohnsonGraph(7,3); rec( adjacencies := [ [ 2, 3, 4, 5, 6, 7, 8, 9, 16, 17, 18, 19 ] ], group := Group([ (1,16,26,32,35,15,5)(2,17,27,33,13,25,9)(3,18,28,10,23,31, 12)(4,19,6,20,29,34,14)(7,21,30,11,24,8,22), (6,16)(7,17)(8,18)(9,19) (10,20)(11,21)(12,22)(13,23)(14,24)(15,25) ]), isGraph := true, isSimple := true, names := [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 2, 6 ], [ 1, 2, 7 ], [ 1, 3, 4 ], [ 1, 3, 5 ], [ 1, 3, 6 ], [ 1, 3, 7 ], [ 1, 4, 5 ], [ 1, 4, 6 ], [ 1, 4, 7 ], [ 1, 5, 6 ], [ 1, 5, 7 ], [ 1, 6, 7 ], [ 2, 3, 4 ], [ 2, 3, 5 ], [ 2, 3, 6 ], [ 2, 3, 7 ], [ 2, 4, 5 ], [ 2, 4, 6 ], [ 2, 4, 7 ], [ 2, 5, 6 ], [ 2, 5, 7 ], [ 2, 6, 7 ], [ 3, 4, 5 ], [ 3, 4, 6 ], [ 3, 4, 7 ], [ 3, 5, 6 ], [ 3, 5, 7 ], [ 3, 6, 7 ], [ 4, 5, 6 ], [ 4, 5, 7 ], [ 4, 6, 7 ], [ 5, 6, 7 ] ], order := 35, representatives := [ 1 ], schreierVector := [ -1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ) gap> Size(AutomorphismGroup(J)); 5040 gap> IsIsomorphicGraph(J,JohnsonGraph(7,4)); true gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Local and global (regularity) parameters in GRAPE gap> # ------------------------------------------------- gap> # gap> # Let gamma be a simple connected graph, and let V be a singleton gap> # vertex or set of vertices of gamma. gap> # gap> # We say that gamma has the *local parameter* c_i(V) (respectively gap> # a_i(V), b_i(V)), with respect to V, if the number of vertices at gap> # distance i-1 (respectively i, i+1) from V that are adjacent gap> # to a vertex w at distance i from V (see ?grape:Distance) is gap> # the constant c_i(V) (respectively a_i(V), b_i(V)) depending only gap> # on i and V (and not the choice of w). gap> # gap> # We say that gamma has the *global parameter* c_i (respectively gap> # a_i, b_i) if the number of vertices at distance i-1 (respectively gap> # i, i+1) from a vertex v that are adjacent to a vertex w at gap> # distance i from v is the constant c_i (respectively a_i, b_i) gap> # depending only on i (and not the choice of v or w). gap> # gap> # In GRAPE, the function call gap> # gap> # LocalParameters(gamma, V) gap> # gap> # returns a list whose i-th element is the list gap> # gap> # [c_{i-1}(V), a_{i-1}(V), b_{i-1}(V)], gap> # gap> # except that if some local parameter does not exist then -1 is gap> # put in its place. gap> # gap> # The function call gap> # gap> # LocalParameters(gamma, V, G) gap> # gap> # does the same, except that the additional parameter G is assumed gap> # to be a subgroup of the automorphism group of gamma fixing V gap> # setwise. Including such a G can result in a performance gain. gap> # gap> # gap> # The function call gap> # gap> # GlobalParameters( gamma ) gap> # gap> # returns a list of length Diameter(gamma)+1 (see ?grape:Diameter), gap> # whose i-th element is the list gap> # gap> # [c_{i-1}, a_{i-1}, b_{i-1}], gap> # gap> # except that if some global parameter does not exist then -1 is put gap> # in its place. gap> # gap> # Note that gamma is *distance-regular* if and only if this function gap> # returns no -1 in place of a global parameter. gap> # gap> # See also ?IsDistanceRegular and ?CollapsedAdjacencyMat . gap> # gap> # Examples gap> # -------- gap> # gap> GlobalParameters(HoffmanSingleton); [ [ 0, 0, 7 ], [ 1, 0, 6 ], [ 1, 6, 0 ] ] gap> IsDistanceRegular(HoffmanSingleton); true gap> edge := [1,Adjacency(HoffmanSingleton,1)[1]]; [ 1, 4 ] gap> edge_stab:=Stabilizer(HoffmanSingleton.group,edge,OnSets); gap> LocalParameters(HoffmanSingleton,edge,edge_stab); [ [ 0, 1, 6 ], [ 1, 0, 6 ], [ 2, 5, 0 ] ] gap> GlobalParameters(McLaughlin); [ [ 0, 0, 112 ], [ 1, 30, 81 ], [ 56, 56, 0 ] ] gap> GlobalParameters(EdgeGraph(McLaughlin)); [ [ 0, 0, 222 ], [ 1, -1, -1 ], [ -1, -1, -1 ], [ 184, 38, 0 ] ] gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The Sylvester graph gap> # ------------------- gap> # gap> # We now use the Hoffman-Singleton graph to construct the gap> # *Sylvester graph*, the unique distance-regular graph with gap> # intersection array {5,4,2; 1,1,4}, that is, with global gap> # parameters: [ [0,0,5],[1,0,4],[1,2,2],[4,1,0] ]. gap> # gap> # The Sylvester graph is the induced subgraph on the 36 vertices gap> # at distance 2 from a fixed edge in the Hoffman-Singleton graph. gap> # gap> # See https://www.win.tue.nl/~aeb/graphs/Sylvester.html gap> # gap> Sylvester := DistanceSetInduced(HoffmanSingleton,2,edge,edge_stab); rec( adjacencies := [ [ 5, 6, 7, 32, 35 ] ], group := , isGraph := true, isSimple := true, names := [ [ 2, 3, 4 ], [ 3, 4, 5 ], [ 3, 4, 6 ], [ 3, 4, 7 ], [ 1, 6, 7 ], [ 1, 5, 7 ], [ 1, 5, 6 ], [ 1, 4, 5 ], [ 1, 2, 6 ], [ 2, 6, 7 ], [ 2, 5, 6 ], [ 1, 4, 6 ], [ 1, 2, 5 ], [ 2, 5, 7 ], [ 3, 6, 7 ], [ 1, 4, 7 ], [ 2, 3, 6 ], [ 1, 3, 4 ], [ 2, 3, 5 ], [ 1, 2, 4 ], [ 1, 3, 5 ], [ 1, 3, 6 ], [ 3, 5, 7 ], [ 2, 4, 5 ], [ 2, 4, 6 ], [ 2, 4, 7 ], [ 3, 5, 6 ], [ [ 1, 2, 4 ], [ 1, 3, 7 ], [ 1, 5, 6 ], [ 2, 3, 5 ], [ 2, 6, 7 ], [ 3, 4, 6 ], [ 4, 5, 7 ] ], [ [ 1, 2, 7 ], [ 1, 3, 6 ], [ 1, 4, 5 ], [ 2, 3, 5 ], [ 2, 4, 6 ], [ 3, 4, 7 ], [ 5, 6, 7 ] ], [ [ 1, 2, 4 ], [ 1, 3, 6 ], [ 1, 5, 7 ], [ 2, 3, 7 ], [ 2, 5, 6 ], [ 3, 4, 5 ], [ 4, 6, 7 ] ], [ [ 1, 2, 5 ], [ 1, 3, 7 ], [ 1, 4, 6 ], [ 2, 3, 6 ], [ 2, 4, 7 ], [ 3, 4, 5 ], [ 5, 6, 7 ] ], [ [ 1, 2, 7 ], [ 1, 3, 5 ], [ 1, 4, 6 ], [ 2, 3, 4 ], [ 2, 5, 6 ], [ 3, 6, 7 ], [ 4, 5, 7 ] ], [ [ 1, 2, 6 ], [ 1, 3, 5 ], [ 1, 4, 7 ], [ 2, 3, 7 ], [ 2, 4, 5 ], [ 3, 4, 6 ], [ 5, 6, 7 ] ], [ [ 1, 2, 7 ], [ 1, 3, 4 ], [ 1, 5, 6 ], [ 2, 3, 6 ], [ 2, 4, 5 ], [ 3, 5, 7 ], [ 4, 6, 7 ] ], [ [ 1, 2, 6 ], [ 1, 3, 7 ], [ 1, 4, 5 ], [ 2, 3, 4 ], [ 2, 5, 7 ], [ 3, 5, 6 ], [ 4, 6, 7 ] ], [ [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 6, 7 ], [ 2, 3, 7 ], [ 2, 4, 6 ], [ 3, 5, 6 ], [ 4, 5, 7 ] ] ], order := 36, representatives := [ 1 ], schreierVector := [ -1, 2, 3, 6, 6, 1, 3, 4, 3, 6, 5, 3, 6, 6, 1, 6, 3, 1, 5, 3, 5, 6, 6, 5, 5, 1, 2, 3, 2, 4, 2, 3, 3, 5, 5, 3 ] ) gap> GlobalParameters(Sylvester); [ [ 0, 0, 5 ], [ 1, 0, 4 ], [ 1, 2, 2 ], [ 4, 1, 0 ] ] gap> # gap> # Confirms that Sylvester is indeed the Sylvester graph. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Construction of a distance-regular graph from a transitive group gap> # ---------------------------------------------------------------- gap> # gap> # gap> # Let G be a transitive permutation group on [1..n]. gap> # A *generalized orbital graph* for G is a simple graph gap> # with vertex-set [1..n] on which G acts naturally as gap> # a (vertex-transitive) group of automorphisms. gap> # gap> # Here we construct the (non-null) generalized orbital graphs for gap> # the group M_{22}:2 in its primitive action on 672 points. gap> # gap> # This includes the distance-regular so-called Moscow-Soicher gap> # graph of degree 110 on 672 vertices. gap> # gap> n := 672; 672 gap> G := AllPrimitiveGroups(NrMovedPoints,n,Size,443520*2); [ M_22.2 ] gap> G := G[1]; M_22.2 gap> RankAction(G,[1..n]); 6 gap> L := GeneralizedOrbitalGraphs(G);; gap> Length(L); 31 gap> List(L,VertexDegrees); [ [ 55 ], [ 385 ], [ 440 ], [ 605 ], [ 671 ], [ 506 ], [ 550 ], [ 616 ], [ 451 ], [ 110 ], [ 275 ], [ 341 ], [ 176 ], [ 220 ], [ 286 ], [ 121 ], [ 330 ], [ 385 ], [ 550 ], [ 616 ], [ 451 ], [ 495 ], [ 561 ], [ 396 ], [ 55 ], [ 220 ], [ 286 ], [ 121 ], [ 165 ], [ 231 ], [ 66 ] ] gap> List(L,GlobalParameters); [ [ [ 0, 0, 55 ], [ 1, 8, 46 ], [ -1, -1, -1 ], [ 45, 10, 0 ] ], [ [ 0, 0, 385 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 440 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 605 ], [ 1, -1, -1 ], [ 540, 65, 0 ] ], [ [ 0, 0, 671 ], [ 1, 670, 0 ] ], [ [ 0, 0, 506 ], [ 1, -1, -1 ], [ 398, 108, 0 ] ], [ [ 0, 0, 550 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 616 ], [ 1, -1, -1 ], [ 562, 54, 0 ] ], [ [ 0, 0, 451 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 110 ], [ 1, 28, 81 ], [ 18, 80, 12 ], [ 90, 20, 0 ] ], [ [ 0, 0, 275 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 341 ], [ 1, -1, -1 ], [ 170, 171, 0 ] ], [ [ 0, 0, 176 ], [ 1, 40, 135 ], [ 48, 128, 0 ] ], [ [ 0, 0, 220 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 286 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 121 ], [ 1, 20, 100 ], [ -1, -1, 0 ] ], [ [ 0, 0, 330 ], [ 1, 158, 171 ], [ -1, -1, 0 ] ], [ [ 0, 0, 385 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 550 ], [ 1, -1, -1 ], [ 450, 100, 0 ] ], [ [ 0, 0, 616 ], [ 1, -1, -1 ], [ 570, 46, 0 ] ], [ [ 0, 0, 451 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 495 ], [ 1, 366, 128 ], [ 360, 135, 0 ] ], [ [ 0, 0, 561 ], [ 1, -1, -1 ], [ 480, 81, 0 ] ], [ [ 0, 0, 396 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 55 ], [ 1, 0, 54 ], [ -1, -1, -1 ], [ 45, 10, 0 ] ], [ [ 0, 0, 220 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 286 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 121 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 165 ], [ 1, 56, 108 ], [ -1, -1, 0 ] ], [ [ 0, 0, 231 ], [ 1, -1, -1 ], [ -1, -1, 0 ] ], [ [ 0, 0, 66 ], [ 1, 0, 65 ], [ -1, -1, 0 ] ] ] gap> MoscowSoicher := First(L,x->VertexDegrees(x)=[110]);; gap> GlobalParameters(MoscowSoicher); [ [ 0, 0, 110 ], [ 1, 28, 81 ], [ 18, 80, 12 ], [ 90, 20, 0 ] ] gap> IsDistanceRegular(MoscowSoicher); true gap> AutomorphismGroup(MoscowSoicher)=G; true gap> # gap> # gap> # See also ?VertexTransitiveDRGs and ?OrbitalGraphColadjMats gap> # for further study of vertex-transitive graphs and the gap> # coherent configurations associated to transitive permutation gap> # groups. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Cliques and co-cliques in GRAPE gap> # ------------------------------- gap> # gap> # gap> # GRAPE contains extensive functionality for the classification of gap> # cliques satisfying a range of user-specified properties. gap> # gap> # gap> # Let gamma be a simple graph. gap> # gap> # A *clique* of gamma is a set of pairwise adjacent vertices. gap> # gap> # A *maximal* clique of gamma is a clique which is not properly gap> # contained in any clique of gamma, while a *maximum* clique of gap> # gamma is a clique of largest size in gamma. The *clique number* gap> # of gamma is the size of a maximum clique of gamma. gap> # gap> # A *co-clique* (or *independent set*) of gamma is a set of gap> # pairwise non-adjacent vertices. Clearly, the co-cliques of gap> # gamma are precisely the cliques of the complement of gamma. gap> # gap> # The *independence number* of gamma is the size of a largest gap> # co-clique of gamma. gap> # gap> # ===================================================================== gap> # gap> # gap> # Computing cliques in GRAPE gap> # -------------------------- gap> # gap> # gap> # Let gamma be a simple graph in GRAPE, with associated group gap> # G:=gamma.group. gap> # gap> # gap> # GRAPE functions can compute the the maximal cliques of gap> # gamma or the cliques of given size or vertex-weight sum gap> # in gamma, or the maximal cliques of given size or vertex-weight sum gap> # in gamma, such that at most one such clique is determined or it is gap> # determined that no such cliques exist, or G-orbit generators of all gap> # such cliques are determined, or G-orbit representatives of all such gap> # cliques are determined. gap> # gap> # There is also the functionality to determine a maximum clique, gap> # and hence to determine the clique number of gamma. gap> # gap> # gap> # These are computationally HARD problems! gap> # gap> # ===================================================================== gap> # gap> # gap> # CompleteSubgraphsOfGivenSize gap> # ---------------------------- gap> # gap> # gap> # This is the main function for clique classification in GRAPE. gap> # gap> # We shall now describe this function for non-weighted cliques, gap> # but for a detailed specification, see ?CompleteSubgraphsOfGivenSize. gap> # Also see ?CompleteSubgraphs and ?MaximumClique. gap> # gap> # gap> # In GRAPE, where gamma is a simple graph, k is a gap> # non-negative integer, allsubs in [0,1,2], and maxi gap> # is a boolean, the function call gap> # gap> # CompleteSubgraphsOfGivenSize(gamma, k, alls, maxi) gap> # gap> # returns a set K of cliques of size k of gamma. These are all gap> # maximal cliques if maxi=true, and not necessarily maximal cliques gap> # if maxi=false. gap> # gap> # The parameter alls should be 0, 1, or 2, and gap> # controls how many cliques are returned. gap> # gap> # First, suppose alls=0. Then K will contain at most one element. gap> # If maxi=false then K will contain a clique of size k iff gap> # gamma has such a clique, and if maxi=true then K will gap> # contain a maximal clique of size k iff gamma has a maximal gap> # clique of that size. gap> # gap> # ***Helpful hint*** In the above function call with alls=0, gap> # if gamma.group is not the full automorphism group of gamma, gap> # it may be (much) more efficient to replace gamma by a copy gap> # whose associated group is its full automorphism group, gap> # as shown below: gap> # gap> # autgrp:=AutomorphismGroup(gamma); gap> # if Size(gamma.group) < Size(autgrp) then gap> # delta:=NewGroupGraph(autgrp,gamma); gap> # else gap> # delta:=gamma; gap> # fi; gap> # CompleteSubgraphsOfGivenSize( delta, k, 0, maxi); gap> # gap> # ***End of helpful hint*** gap> # gap> # If alls=1 and maxi=false, then K will contain (perhaps properly) gap> # a set of gamma.group orbit-representatives of the size k cliques gap> # of gamma. If alls=1 and maxi=true, then K will contain gap> # (perhaps properly) a set of gamma.group orbit-representatives of the gap> # size k maximal cliques of gamma. gap> # gap> # If alls=2 and maxi=false, then K will be a set of gap> # gamma.group orbit-representatives of all the size k cliques gap> # of gamma. If alls=2 and maxi=true, then K will be a set gap> # of gamma.group orbit-representatives of the size k maximal gap> # cliques of gamma. gap> # gap> # gap> # Examples gap> # -------- gap> # gap> gamma:=MoscowSoicher;; gap> G:=gamma.group;; gap> G=AutomorphismGroup(gamma); true gap> CompleteSubgraphsOfGivenSize(gamma,5,0,true); [ [ 1, 2, 80, 124, 455 ] ] gap> CompleteSubgraphsOfGivenSize(gamma,5,0,false); [ [ 1, 2, 18, 35, 41 ] ] gap> CompleteSubgraphsOfGivenSize(gamma,5,1,true); [ [ 1, 2, 80, 124, 455 ] ] gap> CompleteSubgraphsOfGivenSize(gamma,5,1,false); [ [ 1, 2, 18, 35, 41 ], [ 1, 2, 18, 35, 377 ], [ 1, 2, 18, 119, 161 ], [ 1, 2, 18, 119, 277 ], [ 1, 2, 18, 161, 277 ], [ 1, 2, 18, 281, 287 ], [ 1, 2, 18, 281, 366 ], [ 1, 2, 80, 124, 455 ], [ 1, 2, 124, 183, 461 ] ] gap> CompleteSubgraphsOfGivenSize(gamma,5,2,true); [ [ 1, 2, 80, 124, 455 ] ] gap> CompleteSubgraphsOfGivenSize(gamma,5,2,false); [ [ 1, 2, 18, 35, 41 ], [ 1, 2, 18, 119, 161 ], [ 1, 2, 18, 281, 287 ], [ 1, 2, 80, 124, 455 ] ] gap> CompleteSubgraphsOfGivenSize(gamma,7,0); [ ] gap> C:=CompleteSubgraphsOfGivenSize(gamma,6,2,true); [ [ 1, 2, 18, 35, 41, 377 ], [ 1, 2, 18, 119, 161, 277 ], [ 1, 2, 18, 281, 287, 366 ] ] gap> List(C,clique->Size(Stabilizer(G,clique,OnSets))); [ 360, 144, 36 ] gap> C:=CompleteSubgraphsOfGivenSize(gamma,6,2,false); [ [ 1, 2, 18, 35, 41, 377 ], [ 1, 2, 18, 119, 161, 277 ], [ 1, 2, 18, 281, 287, 366 ] ] gap> List(C,clique->Size(Stabilizer(G,clique,OnSets))); [ 360, 144, 36 ] gap> # gap> CliqueNumber(McLaughlin); # the size of a largest clique 5 gap> MaximumClique(McLaughlin); # a clique of largest size [ 1, 2, 17, 45, 193 ] gap> # gap> CliqueNumber(ComplementGraph(McLaughlin)); 22 gap> # This is the independence number of the McLaughlin graph, the gap> # size of a largest co-clique. gap> # gap> # ===================================================================== gap> # gap> # gap> # Cliques in vertex-weighted graphs gap> # --------------------------------- gap> # gap> # See ?CompleteSubgraphsOfGivenSize for the GRAPE functionality gap> # to compute and classify cliques with given vertex-weight sum in a gap> # vertex-weighted graph, where the weights can be positive integers gap> # or non-zero d-vectors of non-negative integers (satisfying certain gap> # conditions w.r.t. the group associated with the graph). gap> # gap> # gap> # This type of clique functionality in GRAPE is used by the DESIGN package gap> # for GAP, for functionality to construct and classify block designs gap> # of many types (including those invariant under a specified gap> # group), as well as to construct and classify parallel classes gap> # and resolutions of block designs. We will see some of this gap> # DESIGN package functionality later in this minicourse. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Proper vertex-colourings gap> # ------------------------ gap> # gap> # gap> # Let gamma be a simple graph. gap> # gap> # A *proper vertex-colouring* of gamma is a labelling of its gap> # vertices by elements from a set of *colours*, such that adjacent gap> # vertices are labelled with different colours. gap> # gap> # Where k is a non-negative integer, a *vertex k-colouring* of gamma gap> # is a proper vertex-colouring using at most k colours. gap> # gap> # A *minimum vertex-colouring* of gamma is a vertex k-colouring gap> # with k as small as possible, and the *chromatic number* of gamma gap> # is the number of colours used in a minimum vertex-colouring of gamma. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The GRAPE function VertexColouring gap> # ---------------------------------- gap> # gap> # gap> # In GRAPE, a proper vertex-colouring of a graph is given as a list gap> # of positive integers (the *colours*), indexed by the vertices of gap> # the graph, such that the i-th list element is the colour of vertex i. gap> # gap> # gap> # In GRAPE, where gamma is a simple graph and k is a non-negative integer, gap> # the function call gap> # gap> # VertexColouring(gamma, k) gap> # gap> # returns a vertex k-colouring of gamma if such a colouring exists; gap> # otherwise, the special value fail is returned. gap> # gap> # In general, this is a computationally (very) HARD problem. gap> # gap> # gap> # Example gap> # ------- gap> # gap> # We first make the induced subgraph in the McLaughlin graph on the gap> # vertices at distance 1 from a fixed vertex (here the vertex 1). gap> # This is the so-called first subconstituent of the McLaughlin graph. gap> # gap> McLaughlin_1:=DistanceSetInduced(McLaughlin,1,1);; gap> GlobalParameters(McLaughlin_1); [ [ 0, 0, 30 ], [ 1, 2, 27 ], [ 10, 20, 0 ] ] gap> ChromaticNumber(McLaughlin_1); 8 gap> # gap> # We next make the induced subgraph in the McLaughlin graph on the gap> # vertices at distance 2 from a fixed vertex (here the vertex 1). gap> # This is the so-called second subconstituent of the McLaughlin graph. gap> # gap> McLaughlin_2:=DistanceSetInduced(McLaughlin,2,1);; gap> GlobalParameters(McLaughlin_2); [ [ 0, 0, 56 ], [ 1, 10, 45 ], [ 24, 32, 0 ] ] gap> VertexColouring(McLaughlin_2,9); fail gap> Collected(VertexColouring(McLaughlin_2,10)); [ [ 1, 21 ], [ 2, 21 ], [ 3, 19 ], [ 4, 19 ], [ 5, 15 ], [ 6, 12 ], [ 7, 16 ], [ 8, 15 ], [ 9, 12 ], [ 10, 12 ] ] gap> # gap> # Thus, McLaughlin_2 has chromatic number 10. gap> # gap> # gap> # See also ?MinimumVertexColouring and ?ChromaticNumber. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # A challenge problem gap> # ------------------- gap> # gap> # gap> # The previous computation shows that that the first subconstituent gap> # of the McLaughlin graph has chromatic number 8, and the second gap> # subconstituent has chromatic number 10. gap> # gap> # It follows that the chromatic number of the McLaughlin graph gap> # is at most 18. gap> # gap> # In fact, using an eigenvalue-based lower bound and gap> # ``ant colony optimization" for establishing an upper bound, gap> # I can show that this chromatic number is 15 or 16. gap> # gap> # The problem is to either find a vertex 15-colouring of the gap> # McLaughlin graph or to show there is no such colouring. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # A major application of the GRAPE colouring functions gap> # ---------------------------------------------------- gap> # gap> # gap> # A simple graph is said to be *nonsynchronizing* if it is gap> # non-complete and non-null and its clique number is equal to gap> # its chromatic number. gap> # gap> # A permutation group on [1..n] is *nonsynchronizing* if it is gap> # a group of automorphisms of a nonsynchronizing graph with vertex gap> # set [1..n]. gap> # gap> # It is easy to see that if n>2 then every non-transitive and gap> # every transitive but non-primitive permutation group is gap> # nonsynchronizing. gap> # gap> # It is of interest in both the theory of permutation groups gap> # and the theory of automata to determine the nonsynchronizing gap> # primitive permutation groups. gap> # gap> # I have used GAP and GRAPE (together with DESIGN, FinInG, theory, gap> # and some high-performance computing) for the determination of the gap> # nonsynchronizing primitive permutation groups of degree at most 464. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # An approach for low degrees gap> # --------------------------- gap> gap> IsNonsynchronizingGraph := function(gamma) > # > # This function returns true if the simple graph gamma > # is nonsynchronizing. Otherwise, false is returned. > # > local n,autgrp,omega,delta; > if not IsSimpleGraph(gamma) then > Error(" must be a simple graph"); > fi; > if IsNullGraph(gamma) or IsCompleteGraph(gamma) then > return false; > fi; > n:=gamma.order; > autgrp:=AutomorphismGroup(gamma); > omega:=CliqueNumber(gamma); > if IsTransitive(autgrp,[1..n]) then > # > # gamma is a vertex-transitive graph, so its clique number > # times its independence number is <= its order. > # If gamma is nonsynchronizing, then this inequality must > # hold with equality. > # > if n mod omega <> 0 then > return false; > fi; > # > # Now let's see whether gamma has a co-clique of size n/omega. > # > delta:=ComplementGraph(gamma); > if Size(delta.group) < Size(autgrp) then > delta:=NewGroupGraph(autgrp,delta); > fi; > if CompleteSubgraphsOfGivenSize(delta,n/omega,0)=[] then > # gamma has no co-clique of size n/omega > return false; > fi; > fi; > return VertexColouring(gamma,omega)<>fail; > end; function( gamma ) ... end gap> gap> n:=63; 63 gap> # gap> # For each primitive group of degree n, we determine whether gap> # this group is nonsynchronizing. gap> # gap> P:=AllPrimitiveGroups(NrMovedPoints,n); [ PSU(3, 3), PSU(3, 3).2, PSU(3, 3), PSU(3, 3).2, PSp(6, 2), PSL(6, 2), A(63), S(63) ] gap> for i in [1..Length(P)] do > Print("\n",P[i]); > L:=GeneralizedOrbitalGraphs(P[i]); > Print(" is nonsynchronizing is: ",ForAny(L,IsNonsynchronizingGraph),"\n"); > od; PSU(3, 3) is nonsynchronizing is: true PSU(3, 3).2 is nonsynchronizing is: true PSU(3, 3) is nonsynchronizing is: false PSU(3, 3).2 is nonsynchronizing is: false PSp(6, 2) is nonsynchronizing is: false PSL(6, 2) is nonsynchronizing is: false A(63) is nonsynchronizing is: false S(63) is nonsynchronizing is: false gap> gap> # gap> # gap> # ===================================================================== gap> #