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> #