%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % %A consmod.tex GRAPE documentation Leonard Soicher % % % \Chapter{Functions to construct and modify graphs} This chapter describes the functions used to construct and modify graphs. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Graph} \>Graph( <G>, <L>, <act>, <rel> ) \>Graph( <G>, <L>, <act>, <rel>, <invt> ) This is the most general and useful way of constructing a graph in {\GRAPE}. First suppose that the optional boolean parameter <invt> is unbound or has value `false'. Then <L> should be a list of elements of a set $S$ on which the group <G> acts, with the action given by the function <act>. The parameter <rel> should be a boolean function defining a <G>-invariant relation on $S$ (so that for $g$ in <G>, $x,y$ in $S$, $<rel>(x,y)$ if and only if $<rel>(<act>(x,g),<act>(y,g))$). Then the function `Graph' returns a graph <gamma> which has as vertex-names (an immutable copy of) \centerline{`Concatenation( Orbits( <G>, <L>, <act> ) )'} (the concatenation of the distinct orbits of the elements in <L> under <G>), and for vertices $v,w$ of <gamma>, $[v,w]$ is an edge if and only if \centerline{`<rel>( VertexName( <gamma>, <v> ), VertexName( <gamma>, <w> ) )'.} Now if the parameter <invt> exists and has value `true', then it is assumed that <L> is invariant under <G> with respect to action <act>. Then the function `Graph' behaves as above, except that the vertex-names of <gamma> become (an immutable copy of) <L>. The group associated with the graph <gamma> returned is the image of <G> acting via <act> on `<gamma>.names'. For example, suppose you have an $n$ by $n$ adjacency matrix $A$ for a graph $X$, so that the vertex-set of $X$ is $\{1,\ldots, n\}$, and $[i,j]$ is an edge of $X$ if and only if $A[i][j]=1$. Suppose also that $G\le \Aut (X)$ ($G$ may be trivial). Then you can make a {\GRAPE} graph isomorphic to $X$ via `Graph( G, [1..n], OnPoints, function(x,y) return A[x][y]=1; end, true );' \beginexample gap> A := [[0,1,0],[1,0,0],[0,0,1]]; [ [ 0, 1, 0 ], [ 1, 0, 0 ], [ 0, 0, 1 ] ] gap> G := Group( (1,2) ); Group([ (1,2) ]) gap> Graph( G, [1..3], OnPoints, > function(x,y) return A[x][y]=1; end, > true ); rec( isGraph := true, order := 3, group := Group( [ (1,2) ] ), schreierVector := [ -1, 1, -2 ], adjacencies := [ [ 2 ], [ 3 ] ], representatives := [ 1, 3 ], names := [ 1, 2, 3 ] ) \endexample We now use `Graph' to construct the Petersen graph. \beginexample gap> Petersen := Graph( SymmetricGroup(5), [[1,2]], OnSets, > function(x,y) return Intersection(x,y)=[]; end ); rec( isGraph := true, order := 10, group := Group( [ ( 1, 2, 3, 5, 7)( 4, 6, 8, 9,10), ( 2, 4)( 6, 9)( 7,10) ] ), schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 1, 2, 2 ], adjacencies := [ [ 3, 5, 8 ] ], representatives := [ 1 ], names := [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 1, 3 ], [ 4, 5 ], [ 2, 4 ], [ 1, 5 ], [ 3, 5 ], [ 1, 4 ], [ 2, 5 ] ] ) \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{EdgeOrbitsGraph} \>EdgeOrbitsGraph( <G>, <edges> ) \>EdgeOrbitsGraph( <G>, <edges>, <n> ) This is a common way of constructing a graph in {\GRAPE}. This function returns the (directed) graph with vertex-set $\{1,\ldots, <n>\}$, edge-set $\cup_{e\in <edges>}\, e^<G>$, and associated (permutation) group <G>, which must act naturally on $\{1,\ldots,<n>\}$. The parameter <edges> should be a list of edges (lists of length 2 of vertices), although a singleton edge will be understood as an edge-list of length 1. The parameter <n> may be omitted, in which case <n> is taken to be the largest point moved by <G>. Note that <G> may be the trivial permutation group (`Group( () )' in {\GAP} notation), in which case the (directed) edges of <gamma> are simply those in the list <edges>. \beginexample gap> EdgeOrbitsGraph( Group((1,3),(1,2)(3,4)), [[1,2],[4,5]], 5 ); rec( isGraph := true, order := 5, group := Group( [ (1,3), (1,2)(3,4) ] ), schreierVector := [ -1, 2, 1, 2, -2 ], adjacencies := [ [ 2, 4, 5 ], [ ] ], representatives := [ 1, 5 ], isSimple := false ) \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{NullGraph} \>NullGraph( <G> ) \>NullGraph( <G>, <n> ) This function returns the null graph (graph with no edges) with vertex-set $\{1,\ldots,<n>\}$, and associated (permutation) group <G>. The parameter <n> may be omitted, in which case <n> is taken to be the largest point moved by <G>. See also "IsNullGraph". \beginexample gap> NullGraph( Group( (1,2,3) ), 4 ); rec( isGraph := true, order := 4, group := Group( [ (1,2,3) ] ), schreierVector := [ -1, 1, 1, -2 ], adjacencies := [ [ ], [ ] ], representatives := [ 1, 4 ], isSimple := true ) \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{CompleteGraph} \>CompleteGraph( <G> ) \>CompleteGraph( <G>, <n> ) \>CompleteGraph( <G>, <n>, <mustloops> ) This function returns the complete graph with vertex-set $\{1,\ldots,<n>\}$ and associated (permutation) group <G>. The parameter <n> may be omitted, in which case <n> is taken to be the largest point moved by <G>. The optional boolean parameter <mustloops> determines whether the complete graph has all loops present or no loops (default: `false' (no loops)). See also "IsCompleteGraph". \beginexample gap> CompleteGraph( Group( (1,2,3), (1,2) ) ); rec( isGraph := true, order := 3, group := Group( [ (1,2,3), (1,2) ] ), schreierVector := [ -1, 1, 1 ], adjacencies := [ [ 2, 3 ] ], representatives := [ 1 ], isSimple := true ) \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{JohnsonGraph} \>JohnsonGraph( <n>, <e> ) Let <n> and <e> be integers, with $<n>\ge <e>\ge 0$. Then this function returns a graph <gamma> isomorphic to the Johnson graph $J(<n>,<e>)$. The vertices (actually the vertex-names) of <gamma> are the <e>-subsets of $\{1,\ldots, <n>\}$, with $x$ joined to $y$ if and only if $|x \cap y| = <e>-1$. The group associated with <gamma> is the image of the symmetric group $S_<n>$ acting on the <e>-subsets of $\{1,\ldots,<n>\}$. \beginexample gap> JohnsonGraph(5,3); rec( isGraph := true, order := 10, group := Group( [ ( 1, 7,10, 6, 3)( 2, 8, 4, 9, 5), ( 4, 7)( 5, 8)( 6, 9) ] ), schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 2, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5, 7, 8 ] ], representatives := [ 1 ], names := [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 3, 5 ], [ 1, 4, 5 ], [ 2, 3, 4 ], [ 2, 3, 5 ], [ 2, 4, 5 ], [ 3, 4, 5 ] ], isSimple := true ) \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{CayleyGraph} \>CayleyGraph( <G> ) \>CayleyGraph( <G>, <gens> ) \>CayleyGraph( <G>, <gens>, <undirected> ) Given a group <G> and a generating list <gens> for <G>, `CayleyGraph( <G>, <gens> )' returns a Cayley graph for <G> with respect to <gens>. The generating list <gens> is optional, and if omitted, then <gens> is taken to be `GeneratorsOfGroup( <G> )'. The boolean argument <undirected> is also optional, and if <undirected>=`true' (the default), then the returned graph is undirected (as if <gens> was closed under inversion, whether or not it is). The Cayley graph <caygraph> which is returned is defined as follows: the vertices (actually the vertex-names) of <caygraph> are the elements of <G>; if <undirected>=`true' (the default) then vertices $x,y$ are joined by an edge if and only if there is a $g$ in the list <gens> with $y=gx$ or $y=g^{-1}x$; if <undirected>=`false' then $[x,y]$ is an edge if and only if there is a $g$ in <gens> with $y=gx$. The permutation group `<caygraph>.group' associated with <caygraph> is the image of <G> acting in its right regular representation. *Note* It is not checked whether <G> is actually generated by <gens>. However, even if <G> is not generated by <gens>, the function still works as described above (as long as <gens> is contained in <G>), but returns a ``Cayley graph'' which is not connected. \beginexample gap> C:=CayleyGraph(SymmetricGroup(4),[(1,2),(2,3),(3,4)]); rec( isGraph := true, order := 24, group := Group( [ ( 1,10,17,19)( 2, 9,18,20)( 3,12,14,21)( 4,11,13,22)( 5, 7,16,23) ( 6, 8,15,24), ( 1, 7)( 2, 8)( 3, 9)( 4,10)( 5,11)( 6,12)(13,15) (14,16)(17,18)(19,21)(20,22)(23,24) ] ), schreierVector := [ -1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2 ], adjacencies := [ [ 2, 3, 7 ] ], representatives := [ 1 ], names := [ (), (3,4), (2,3), (2,3,4), (2,4,3), (2,4), (1,2), (1,2)(3,4), (1,2,3), (1,2,3,4), (1,2,4,3), (1,2,4), (1,3,2), (1,3,4,2), (1,3), (1,3,4), (1,3)(2,4), (1,3,2,4), (1,4,3,2), (1,4,2), (1,4,3), (1,4), (1,4,2,3), (1,4)(2,3) ], isSimple := true ) gap> Girth(C); 4 gap> Diameter(C); 6 \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{AddEdgeOrbit} \>AddEdgeOrbit( <gamma>, <e> ) \>AddEdgeOrbit( <gamma>, <e>, <H> ) This procedure adds the orbit of <e> under `<gamma>.group' to the edge-set of the graph <gamma>. The parameter <e> must be a sequence of length 2 of vertices of <gamma>. If the optional third parameter <H> is given then it is assumed that `<e>[2]' has the same orbit under <H> as it does under the stabilizer in `<gamma>.group' of `<e>[1]', and this knowledge can speed up the procedure. Note that if `<gamma>.group' is trivial then this procedure simply adds the single (directed) edge <e> to <gamma>. See also "RemoveEdgeOrbit". \beginexample gap> gamma := NullGraph( Group( (1,3), (1,2)(3,4) ) );; gap> AddEdgeOrbit( gamma, [4,3] ); gap> gamma; rec( isGraph := true, order := 4, group := Group( [ (1,3), (1,2)(3,4) ] ), schreierVector := [ -1, 2, 1, 2 ], adjacencies := [ [ 2, 4 ] ], representatives := [ 1 ], isSimple := true ) gap> GlobalParameters(gamma); [ [ 0, 0, 2 ], [ 1, 0, 1 ], [ 2, 0, 0 ] ] \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{RemoveEdgeOrbit} \>RemoveEdgeOrbit( <gamma>, <e> ) \>RemoveEdgeOrbit( <gamma>, <e>, <H> ) This procedure removes the orbit of <e> under `<gamma>.group' from the edge-set of the graph <gamma>. The parameter <e> must be a sequence of length 2 of vertices of <gamma>, but if <e> is not an edge of <gamma> then this procedure has no effect. If the optional third parameter <H> is given then it is assumed that `<e>[2]' has the same orbit under <H> as it does under the stabilizer in `<gamma>.group' of `<e>[1]', and this knowledge can speed up the procedure. See also "AddEdgeOrbit". \beginexample gap> gamma := CompleteGraph( Group( (1,3), (1,2)(3,4) ) );; gap> RemoveEdgeOrbit( gamma, [1,3] ); gap> gamma; rec( isGraph := true, order := 4, group := Group( [ (1,3), (1,2)(3,4) ] ), schreierVector := [ -1, 2, 1, 2 ], adjacencies := [ [ 2, 4 ] ], representatives := [ 1 ], isSimple := true ) gap> GlobalParameters(gamma); [ [ 0, 0, 2 ], [ 1, 0, 1 ], [ 2, 0, 0 ] ] \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{AssignVertexNames} \>AssignVertexNames( <gamma>, <names> ) This procedure allows the user to give new names for the vertices of <gamma>, by specifying a list <names> (of length `<gamma>.order') of vertex-names for the vertices of <gamma>, such that `<names>[<i>]' contains the user{\pif}s name for the <i>-th vertex of <gamma>. An immutable copy of <names> is assigned to `<gamma>.names'. See also "VertexNames" and "VertexName". \beginexample gap> gamma := NullGraph( Group(()), 3 ); rec( isGraph := true, order := 3, group := Group( [ () ] ), schreierVector := [ -1, -2, -3 ], adjacencies := [ [ ], [ ], [ ] ], representatives := [ 1, 2, 3 ], isSimple := true ) gap> AssignVertexNames( gamma, ["a","b","c"] ); gap> gamma; rec( isGraph := true, order := 3, group := Group( [ () ] ), schreierVector := [ -1, -2, -3 ], adjacencies := [ [ ], [ ], [ ] ], representatives := [ 1, 2, 3 ], isSimple := true, names := [ "a", "b", "c" ] ) \endexample