gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Partial linear spaces and partial geometries gap> # -------------------------------------------- gap> # gap> # gap> # Where s and t are positive integers, a *partial linear space* gap> # with *parameters* (s,t) consists of a finite set of *points*, gap> # together with a set of (s+1)-subsets of the points, called *lines*, gap> # such that every point is on exactly t+1 lines, and any two distinct gap> # points lie on (i.e. are contained in) at most one line gap> # (equivalently, any two distinct lines meet in at most one point). gap> # gap> # gap> # Two partial linear spaces are *isomorphic* if there is a gap> # bijection from the point-set of the first to that of the second gap> # which applied to the set of lines of the first yields the set of gap> # lines of the second. gap> # gap> # gap> # The *point graph* (or *collinearity graph*) of a partial linear gap> # space is the graph whose vertices are the points of the space, gap> # with two distinct vertices joined by an edge exactly when they gap> # lie on a common line. gap> # gap> # gap> # A *partial geometry* is a partial linear space with parameters (s,t), gap> # for which there is an additional constant alpha>0, such gap> # that, for every line L and every point p not on L, gap> # there are exactly alpha lines through p meeting L in some point. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The GRAPE function PartialLinearSpaces gap> # --------------------------------------- gap> # gap> # gap> # Let gamma be a simple graph, and s and t positive integers. gap> # gap> # Then gap> # gap> # PartialLinearSpaces( gamma, s, t ) gap> # gap> # returns a list of representatives of the distinct isomorphism classes gap> # of partial linear spaces with parameters (s,t) and point graph gamma. gap> # (This may take a (very) long time.) gap> # gap> # In the output of this function, a partial linear space S is given gap> # by its incidence graph delta, such that the group delta.group associated gap> # with delta is the automorphism group of the space S acting on gap> # point-vertices and line-vertices, and preserving both sets. gap> # gap> # See ?PartialLinearSpaces for more information. gap> # gap> # gap> K7:=CompleteGraph(SymmetricGroup([1..7]));; gap> P:=PartialLinearSpaces(K7,2,2); [ rec( adjacencies := [ [ 8, 9, 10 ], [ 1, 2, 3 ] ], group := Group([ (1,2)(5,6)(9,11)(10,12), (1,2,3)(5,6,7)(9,11,13) (10,12,14), (1,2,3)(4,7,6)(9,12,14)(10,11,13), (1,4,7,6,2,5,3) (8,9,13,10,11,12,14) ]), isGraph := true, isSimple := true, names := [ 1, 2, 3, 4, 5, 6, 7, [ 1, 2, 3 ], [ 1, 4, 5 ], [ 1, 6, 7 ], [ 2, 4, 6 ], [ 2, 5, 7 ], [ 3, 4, 7 ], [ 3, 5, 6 ] ], order := 14, representatives := [ 1, 8 ], schreierVector := [ -1, 1, 2, 4, 4, 1, 3, -2, 4, 1, 1, 3, 4, 2 ] ) ] gap> GlobalParameters(P[1]); [ [ 0, 0, 3 ], [ 1, 0, 2 ], [ 1, 0, 2 ], [ 3, 0, 0 ] ] gap> Size(P[1].group); 168 gap> T:=ComplementGraph(JohnsonGraph(10,2));; gap> P:=PartialLinearSpaces(T,4,6);; gap> List(P,x->Size(x.group)); [ 216, 1512 ] gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The Haemers partial geometry gap> # ---------------------------- gap> # gap> # gap> # The Haemers partial geometry is a partial geometry with parameters gap> # s=4, t=17, alpha=2 and point graph the distance-2 graph gap> # of the edge graph of the Hoffman-Singleton graph. See: gap> # gap> # W. Haemers, A new partial geometry constructed from the gap> # Hoffman-Singleton graph, in "Finite Geometries and Designs: gap> # Proceedings of the Second Isle of Thorns Conference 1980", gap> # P.J. Cameron et al. (eds), LMS Lecture Note Series 49, gap> # Cambridge University Press, 1981, pp. 119-127. gap> # gap> # gap> # Here we use the GRAPE function PartialLinearSpaces to construct gap> # the Haemers partial geometry and its dual, prove that they are gap> # determined up to isomorphism (as partial linear spaces) gap> # by their respective point graphs and parameters, and gap> # determine their full automorphism groups. gap> # gap> pointgraph:=DistanceGraph( EdgeGraph(HoffmanSingleton), 2);; gap> GlobalParameters(pointgraph); [ [ 0, 0, 72 ], [ 1, 20, 51 ], [ 36, 36, 0 ] ] gap> VertexName(pointgraph,1); [ [ 1, 2, 3 ], [ 4, 5, 6 ] ] gap> spaces:=PartialLinearSpaces(pointgraph,4,17);; gap> Length(spaces); 1 gap> HaemersGeometry:=spaces[1];; gap> # gap> # Now HaemersGeometry is the incidence graph of the Haemers gap> # partial geometry. gap> # gap> DisplayCompositionSeries(HaemersGeometry.group); G (2 gens, size 2520) | A(7) 1 (0 gens, size 1) gap> linegraph:=PointGraph(HaemersGeometry,Adjacency(HaemersGeometry,1)[1]);; gap> GlobalParameters(linegraph); [ [ 0, 0, 85 ], [ 1, 20, 64 ], [ 10, 75, 0 ] ] gap> spaces:=PartialLinearSpaces(linegraph,17,4);; gap> Length(spaces); 1 gap> DualHaemersGeometry:=spaces[1];; gap> DisplayCompositionSeries(DualHaemersGeometry.group); G (4 gens, size 2520) | A(7) 1 (0 gens, size 1) gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # SmallestImageSet gap> # ---------------- gap> # gap> # gap> # An important behind-the-scenes workhorse included in GRAPE is gap> # Steve Linton's function SmallestImageSet. gap> # gap> # This function is used in GRAPE in the classification of cliques and gap> # the classification of partial linear spaces, and in the DESIGN package gap> # in the classification of block designs. gap> # gap> # The function is of use in many other situations when classifying gap> # objects up to the action of a given permutation group on [1..n], gap> # when the objects can be represented as subsets of [1..n]. gap> # gap> # gap> # Let G be a permutation group on [1..n] and let S be a gap> # subset of [1..n]. Then the function call gap> # gap> # SmallestImageSet(G, S) gap> # gap> # returns the lexicographically least set in Orbit(G,S,OnSets), gap> # without explicitly computing this (possibly huge) orbit. gap> # Thus, if T is any subset of [1..n], then gap> # gap> # SmallestImageSet(G,S) = SmallestImageSet(G,T) gap> # gap> # iff S and T are equivalent under the action of G. gap> # gap> # Typically, we set things up so that certain subsets of [1..n] gap> # represent the objects we are classifying, with two objects gap> # equivalent iff their representing sets are in the same G-orbit gap> # of sets. Then, if C is a list of subsets of [1..n] gap> # (say certain cliques of a given size in a graph), and we want to gap> # determine a set of (canonical) representatives for the distinct gap> # G-orbits of the elements of C, we can do this via: gap> # gap> # representatives := Set( List(C,c->SmallestImageSet(G,c) ); gap> # gap> # gap> # Steve Linton's algorithm for SmallestImageSet is given in: gap> # gap> # S. Linton, Finding the smallest image of a set, in "ISSAC '04: gap> # Proceedings of the 2004 International Symposium on Symbolic and gap> # Algebraic Computation", 2004, ACM Press, pp. 229–234. gap> # gap> # Further developments in the computation of minimal and canonical gap> # images w.r.t. a group action are given in: gap> # gap> # C. Jefferson, M. Pfeiffer, R. Waldecker and E. Jonauskyte, gap> # GAP Package images, version 1.3.0, 2019, gap> # https://gap-packages.github.io/images gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The Digraphs package gap> # -------------------- gap> # gap> LoadPackage("digraphs"); ───────────────────────────────────────────────────────────────────────────── Loading datastructures 0.2.5 (datastructures - GAP Data Structures) by Markus Pfeiffer (http://www.morphism.de/~markusp), Max Horn (https://www.quendi.de/math), Christopher Jefferson (http://caj.host.cs.st-andrews.ac.uk/), and Steve Linton (http://sl4.host.cs.st-andrews.ac.uk/). Homepage: https://gap-packages.github.io/datastructures Report issues at https://github.com/gap-packages/datastructures/issues ───────────────────────────────────────────────────────────────────────────── ───────────────────────────────────────────────────────────────────────────── Loading Digraphs 1.3.1 (Digraphs - Methods for digraphs) by Jan De Beule (http://homepages.vub.ac.be/~jdbeule/), Julius Jonusas (http://julius.jonusas.work), James Mitchell (https://jdbm.me), Michael Torpey (https://mtorpey.github.io), Maria Tsalakou (https://mariatsalakou.github.io/), and Wilf A. Wilson (https://wilf.me). with contributions by: Stuart Burrell (sb235@st-andrews.ac.uk), Reinis Cirpons (rc234@st-andrews.ac.uk), Luke Elliott (le27@st-andrews.ac.uk), Max Horn (https://www.quendi.de/math), Christopher Jefferson (http://caj.host.cs.st-andrews.ac.uk), Markus Pfeiffer (https://www.morphism.de/~markusp), Christopher Russell (cr66@st-andrews.ac.uk), Finn Smith (fls3@st-andrews.ac.uk), and Murray Whyte (mw231@st-andrews.ac.uk). maintained by: James Mitchell (https://jdbm.me) and Wilf A. Wilson (https://wilf.me). Homepage: https://digraphs.github.io/Digraphs Report issues at https://github.com/digraphs/Digraphs/issues ───────────────────────────────────────────────────────────────────────────── true gap> # gap> # Digraphs is a modern GAP package that in many ways complements and gap> # extends the GRAPE package. While GRAPE is designed for the construction gap> # and study of (usually simple and sometimes very large) graphs gap> # related to groups, designs, and finite geometries, the Digraphs gap> # package focuses on directed graphs, and provides a very extensive gap> # range of constructions and graph-theoretic functionality gap> # for graphs, digraphs, and (at present) multigraphs. gap> # gap> # The Digraphs package was designed to include many functions analogous to gap> # those in GRAPE (see Appendix A of the Digraphs manual), and in addition gap> # to provide modern GAP data structures and extensive efficient gap> # functionality for: gap> # gap> # - digraphs, including those related to semigroups gap> # gap> # - digraph homomorphisms gap> # gap> # - digraph drawing gap> # gap> # - I/O facilities for large collections of digraphs gap> # gap> # - and more. gap> # gap> # gap> # The Digraphs package includes the bliss tool for computing gap> # digraph automorphism groups and testing digraph isomorphism. gap> # gap> # We will look at examples of some of the functionality provided by gap> # Digraphs, illustrating much which is not readily available gap> # in GRAPE. However, we shall not discuss any multigraph functionality gap> # in this minicourse. For our purposes, a digraph in the gap> # Digraphs package is mathematically the same as a (not necessarily gap> # simple) graph in GRAPE. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Digraph homomorphisms gap> # --------------------- gap> # gap> # gap> # One very important part of the Digraphs package is its functionality gap> # for digraph homomorphisms. gap> # gap> # gap> # Where gamma and delta are digraphs, a *homomorphism* phi from gap> # gamma to delta is a mapping from the vertices of gamma to gap> # those of delta, such that, if [i,j] is a directed edge gap> # of gamma then [i^phi,j^phi] is a directed edge of delta. gap> # gap> # An *endomorphism* of a digraph gamma is a homomorphism from gamma gap> # to itself, and gamma is called a *core* if all its endomorphisms gap> # are automorphisms. gap> # gap> # An *embedding* of a digraph gamma in a digraph delta is gap> # an injective homomorphism phi from gamma to delta, such that, gap> # if i and j are vertices of gamma such that [i,j] is not an gap> # edge, then [i^phi,j^phi] is not an edge of delta. gap> # gap> # A *core* of a digraph gamma is a minimal induced subdigraph gap> # of gamma, subject to being a homomorphic image of gamma. gap> # (A core of a digraph is itself a core and is unique up to isomorphism.) gap> # gap> # Suppose now gamma is a simple (di)graph, and let K be the gap> # complete digraph on k vertices (having no loops). gap> # gap> # There is a homomorphism from K to gamma if and only if gap> # gamma has a clique of size k. (But note that Digraphs has gap> # specialized functionality for cliques.) gap> # gap> # There is a homomorphism from gamma to K if and only if gamma gap> # has a vertex k-colouring. gap> # gap> # Note that if gamma is non-null and non-complete then gamma is gap> # nonsynchronizing if and only if its core is a complete (di)graph. gap> # gap> gap> R:=RandomDigraph(10,0.5); gap> DigraphVertices(R); [ 1 .. 10 ] gap> DigraphEdges(R); [ [ 1, 2 ], [ 1, 3 ], [ 1, 8 ], [ 1, 10 ], [ 2, 1 ], [ 2, 2 ], [ 2, 4 ], [ 2, 6 ], [ 2, 7 ], [ 2, 8 ], [ 3, 3 ], [ 3, 6 ], [ 3, 7 ], [ 3, 9 ], [ 3, 10 ], [ 4, 1 ], [ 4, 3 ], [ 4, 4 ], [ 4, 5 ], [ 4, 7 ], [ 5, 3 ], [ 5, 4 ], [ 5, 5 ], [ 5, 8 ], [ 5, 10 ], [ 6, 2 ], [ 6, 6 ], [ 7, 1 ], [ 7, 2 ], [ 7, 5 ], [ 7, 7 ], [ 7, 8 ], [ 7, 9 ], [ 8, 2 ], [ 8, 4 ], [ 8, 6 ], [ 8, 8 ], [ 8, 9 ], [ 8, 10 ], [ 9, 1 ], [ 9, 6 ], [ 9, 8 ], [ 9, 9 ], [ 9, 10 ], [ 10, 4 ], [ 10, 6 ] ] gap> OutDegrees(R); [ 4, 6, 5, 5, 5, 2, 6, 6, 5, 2 ] gap> InDegrees(R); [ 4, 5, 4, 5, 3, 6, 4, 6, 4, 5 ] gap> # We display a picture of R, making use of GraphViz and pdflatex. gap> Splash(DotDigraph(R), > rec( directory:="g2g2", filename:="randomdigraph")); gap> AdjacencyMatrix(R); [ [ 0, 1, 1, 0, 0, 0, 0, 1, 0, 1 ], [ 1, 1, 0, 1, 0, 1, 1, 1, 0, 0 ], [ 0, 0, 1, 0, 0, 1, 1, 0, 1, 1 ], [ 1, 0, 1, 1, 1, 0, 1, 0, 0, 0 ], [ 0, 0, 1, 1, 1, 0, 0, 1, 0, 1 ], [ 0, 1, 0, 0, 0, 1, 0, 0, 0, 0 ], [ 1, 1, 0, 0, 1, 0, 1, 1, 1, 0 ], [ 0, 1, 0, 1, 0, 1, 0, 1, 1, 1 ], [ 1, 0, 0, 0, 0, 1, 0, 1, 1, 1 ], [ 0, 0, 0, 1, 0, 1, 0, 0, 0, 0 ] ] gap> CharacteristicPolynomial(R); x_1^10-8*x_1^9+22*x_1^8-36*x_1^7+41*x_1^6-36*x_1^5+11*x_1^4+32*x_1^3-57*x_1^2+\ 19*x_1+5 gap> IsEulerianDigraph(R); false gap> HamiltonianPath(R); [ 1, 3, 7, 9, 8, 4, 5, 10, 6, 2 ] gap> DigraphGirth(R); 1 gap> DigraphOddGirth(R); 1 gap> C:=DigraphAllSimpleCircuits(R);; gap> Length(C); 799 gap> F:=Filtered(C,x->Length(x)>2);; gap> Length(F); 785 gap> F[1]; [ 1, 2, 4 ] gap> IsPlanarDigraph(R); false gap> IsDigraphCore(R); false gap> DigraphCore(R); [ 2 ] gap> gens:=GeneratorsOfEndomorphismMonoid(R);; gap> Length(gens); 8716 gap> Size(Monoid(gens)); 8716 gap> Size(AutomorphismGroup(R)); 1 gap> Graph(R); # converts from Digraphs to GRAPE format rec( adjacencies := [ [ 2, 3, 8, 10 ], [ 1, 2, 4, 6, 7, 8 ], [ 3, 6, 7, 9, 10 ], [ 1, 3, 4, 5, 7 ], [ 3, 4, 5, 8, 10 ], [ 2, 6 ], [ 1, 2, 5, 7, 8, 9 ], [ 2, 4, 6, 8, 9, 10 ], [ 1, 6, 8, 9, 10 ], [ 4, 6 ] ], group := Group(()), isGraph := true, names := [ 1 .. 10 ], order := 10, representatives := [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ], schreierVector := [ -1, -2, -3, -4, -5, -6, -7, -8, -9, -10 ] ) gap> gap> P:=PetersenGraph(); # built-in Digraphs function gap> DigraphVertices(P); [ 1 .. 10 ] gap> DigraphEdges(P); [ [ 1, 2 ], [ 1, 5 ], [ 1, 6 ], [ 2, 1 ], [ 2, 3 ], [ 2, 7 ], [ 3, 2 ], [ 3, 4 ], [ 3, 8 ], [ 4, 3 ], [ 4, 5 ], [ 4, 9 ], [ 5, 1 ], [ 5, 4 ], [ 5, 10 ], [ 6, 1 ], [ 6, 8 ], [ 6, 9 ], [ 7, 2 ], [ 7, 9 ], [ 7, 10 ], [ 8, 3 ], [ 8, 6 ], [ 8, 10 ], [ 9, 4 ], [ 9, 6 ], [ 9, 7 ], [ 10, 5 ], [ 10, 7 ], [ 10, 8 ] ] gap> Splash(DotDigraph(P), > rec( directory:="g2g2", filename:="petersendigraph")); gap> Splash(DotSymmetricDigraph(P), > rec(directory:="g2g2", filename:="petersengraph")); gap> AdjacencyMatrix(P); [ [ 0, 1, 0, 0, 1, 1, 0, 0, 0, 0 ], [ 1, 0, 1, 0, 0, 0, 1, 0, 0, 0 ], [ 0, 1, 0, 1, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 1, 0, 1, 0, 0, 0, 1, 0 ], [ 1, 0, 0, 1, 0, 0, 0, 0, 0, 1 ], [ 1, 0, 0, 0, 0, 0, 0, 1, 1, 0 ], [ 0, 1, 0, 0, 0, 0, 0, 0, 1, 1 ], [ 0, 0, 1, 0, 0, 1, 0, 0, 0, 1 ], [ 0, 0, 0, 1, 0, 1, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 1, 1, 0, 0 ] ] gap> CharacteristicPolynomial(P); x_1^10-15*x_1^8+75*x_1^6-24*x_1^5-165*x_1^4+120*x_1^3+120*x_1^2-160*x_1+48 gap> IsEulerianDigraph(P); true gap> HamiltonianPath(P); fail gap> DigraphGirth(P); 2 gap> DigraphOddGirth(P); 5 gap> DigraphUndirectedGirth(P); 5 gap> C:=DigraphAllSimpleCircuits(P);; gap> Length(C); 129 gap> C[1]; [ 1, 2 ] gap> F:=Filtered(C,x->Length(x)>2);; gap> Length(F); 114 gap> F[1]; [ 1, 2, 3, 4, 5 ] gap> DigraphMaximalMatching(P); [ [ 1, 2 ], [ 3, 4 ], [ 5, 10 ], [ 6, 8 ], [ 7, 9 ] ] gap> DigraphMaximumMatching(P); [ [ 1, 2 ], [ 3, 4 ], [ 5, 10 ], [ 6, 8 ], [ 7, 9 ] ] gap> IsPlanarDigraph(P); false gap> IsDigraphCore(P); true gap> gens:=GeneratorsOfEndomorphismMonoid(P);; gap> Size(Monoid(gens)); 120 gap> Size(AutomorphismGroup(P)); 120 gap> Length(HomomorphismsDigraphs(P,CompleteDigraph(2))); 0 gap> DigraphColouring(P,3); Transformation( [ 1, 2, 3, 1, 2, 3, 3, 2, 2, 1 ] ) gap> Length(HomomorphismsDigraphs(P,CompleteDigraph(3))); 120 gap> Length(HomomorphismsDigraphsRepresentatives(P,CompleteDigraph(3))); 20 gap> C:=CycleDigraph(5); gap> Length(EmbeddingsDigraphs(C,P)); 0 gap> Length(EmbeddingsDigraphs(DigraphSymmetricClosure(C),P)); 120 gap> Length(EmbeddingsDigraphsRepresentatives(DigraphSymmetricClosure(C),P)); 1 gap> Graph(P); rec( adjacencies := [ [ 2, 5, 6 ] ], group := Group([ (4,8)(5,6)(9,10), (2,5,6)(3,4,9,7,10,8), (1,2,3,4,9,6) (5,7,8) ]), isGraph := true, names := [ 1 .. 10 ], order := 10, representatives := [ 1 ], schreierVector := [ -1, 3, 3, 2, 2, 1, 3, 3, 2, 2 ] ) gap> gap> H:=HammingGraph(3,2); # 1-skeleton of a cube using GRAPE rec( adjacencies := [ [ 2, 3, 5 ] ], group := Group([ (1,5)(2,6)(3,7)(4,8), (1,3)(2,4)(5,7)(6,8), (1,2)(3,4)(5,6) (7,8), (2,5,3)(4,6,7), (3,5)(4,6) ]), isGraph := true, names := [ [ 1, 1, 1 ], [ 1, 1, 2 ], [ 1, 2, 1 ], [ 1, 2, 2 ], [ 2, 1, 1 ], [ 2, 1, 2 ], [ 2, 2, 1 ], [ 2, 2, 2 ] ], order := 8, representatives := [ 1 ], schreierVector := [ -1, 3, 2, 3, 1, 3, 2, 3 ] ) gap> cube:=Digraph(H); gap> # gap> # The Digraph function provides various ways to construct gap> # a digraph in the Digraphs package. Where gamma is a graph in gap> # GRAPE format, the function call Digraph(gamma) returns this gap> # graph in Digraphs format. gap> # gap> Print(cube); DigraphFromGraph6String("Gr`HOk") gap> DigraphVertices(cube); [ 1 .. 8 ] gap> HamiltonianPath(cube); [ 1, 2, 4, 3, 7, 8, 6, 5 ] gap> DigraphGirth(cube); 2 gap> DigraphOddGirth(cube); infinity gap> DigraphUndirectedGirth(cube); 4 gap> IsPlanarDigraph(cube); true gap> IsDigraphCore(cube); false gap> DigraphCore(cube); [ 1, 2 ] gap> gens:=GeneratorsOfEndomorphismMonoid(cube);; gap> Length(gens); 114 gap> Size(Monoid(gens)); 5304 gap> homs:=HomomorphismsDigraphs(cube,CompleteDigraph(2)); [ Transformation( [ 1, 2, 2, 1, 2, 1, 1, 2 ] ), Transformation( [ 2, 1, 1, 2, 1, 2, 2, 1 ] ) ] gap> List(DigraphVertices(cube),x->x^homs[1]); [ 1, 2, 2, 1, 2, 1, 1, 2 ] gap> Length(HomomorphismsDigraphs(CompleteDigraph(2),cube)); 48 gap> Length(HomomorphismsDigraphs(cube,CompleteDigraph(3))); 114 gap> Length(HomomorphismsDigraphs(CompleteDigraph(3),cube)); 0 gap> gap> D:=Digraph(HoffmanSingleton); gap> Length(HomomorphismsDigraphs(P,D)); 252000 gap> Length(EmbeddingsDigraphs(P,D)); 252000 gap> Length(EmbeddingsDigraphsRepresentatives(P,D)); 1 gap> HamiltonianPath(D); [ 9, 12, 20, 13, 16, 26, 6, 2, 10, 3, 14, 4, 1, 7, 19, 5, 11, 25, 8, 15, 31, 46, 32, 44, 18, 41, 21, 36, 27, 38, 33, 50, 35, 49, 22, 47, 23, 42, 34, 40, 17, 43, 29, 45, 24, 48, 30, 39, 28, 37 ] gap> IsPlanarDigraph(D); false gap> IsDigraphCore(D); true gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The AGT package gap> # --------------- gap> # gap> # You should also be aware of the AGT package for Algebraic Graph Theory. gap> # gap> LoadPackage("agt"); ───────────────────────────────────────────────────────────────────────────── Loading DESIGN 1.7 (The Design Package for GAP) by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~lsoicher/). Homepage: https://gap-packages.github.io/design Report issues at https://github.com/gap-packages/design/issues ───────────────────────────────────────────────────────────────────────────── ───────────────────────────────────────────────────────────────────────────── Loading AGT 0.2 (Algebraic Graph Theory) by Rhys J. Evans (https://www.qmul.ac.uk/maths/profiles/evansr.html). Homepage: https://gap-packages.github.io/agt Report issues at https://github.com/gap-packages/AGT/issues ───────────────────────────────────────────────────────────────────────────── true gap> # gap> # From the AGT manual: gap> # gap> # "The AGT package contains methods used for the determination gap> # of various algebraic and regularity properties of graphs, as well gap> # as certain substructures of graphs. gap> # gap> # The package also contains a library of strongly regular graphs, gap> # intended to be a useful resource for computational experiments. gap> # gap> # All of the functions in this package deal with finite simple graphs gap> # in GRAPE format. Behind the scenes, we also use the Digraphs package gap> # to format and efficiently store and access the graphs in the gap> # strongly regular graph library." gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The DESIGN package gap> # ------------------ gap> # gap> LoadPackage("design"); true gap> # gap> # The DESIGN package provides functionality for constructing, gap> # classifying, partitioning and studying block designs, and gap> # makes use of the GRAPE package. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Block designs gap> # ------------- gap> # gap> # A *block design* is an ordered pair (P,B), where P is a gap> # non-empty finite set whose elements are called *points*, and B gap> # is a non-empty finite multiset whose elements are called *blocks*, gap> # such that each block is a non-empty finite multiset of points. gap> # gap> # A *parallel class* (or *spread*) of a block design D = (P,B) gap> # is a sub(multi)set of B forming a partition of P, and a gap> # *resolution* of D is a partition of B into paralllel classes. gap> # We say that a block design is *resolvable* if it has a resolution. gap> # gap> # The DESIGN package deals with arbitrary block designs, but gap> # some DESIGN functions only work for *binary* block designs gap> # (i.e. those with no repeated element in any block of the design), gap> # but these functions will check if an input block design is binary. gap> # gap> # gap> # ===================================================================== gap> # gap> # t-designs gap> # --------- gap> # gap> # An important class of binary block designs are t-designs. gap> # gap> # For t a non-negative integer and v, k, lambda positive integers gap> # with t <= k <= v, a *t-design* with *parameters* gap> # t, v, k, lambda, or a t-(v,k,lambda) design, is a binary block gap> # design with exactly v points, such that each block has size k and gap> # each t-subset of the points is contained in exactly lambda blocks. gap> # gap> # A t-(v,k,lambda) design is also an s-(v,k,lambda_s) design for gap> # 0 <= s <= t, where gap> # gap> # lambda_s = lambda(v-s choose t-s)/(k-s choose t-s). gap> # gap> # For example, we compute these lambda_s for a 5-(24,8,1) design. gap> # gap> TDesignLambdas(5,24,8,1); [ 759, 253, 77, 21, 5, 1 ] gap> # gap> # The DESIGN package has extensive functionality for t-designs gap> # and their parameters. gap> # gap> # For example, you can compute a (quite good) upper bound on the gap> # multiplicity of a block in any t-design with given parameters gap> # (t,v,k,lamba) or in any resolvable such t-design. gap> # See ?design:Information from $t$-design parameters gap> # gap> TDesignLambdaMin(2,12,4); 3 gap> TDesignLambdas(2,12,4,3); [ 33, 11, 3 ] gap> TDesignBlockMultiplicityBound(2,12,4,3); 2 gap> ResolvableTDesignBlockMultiplicityBound(2,12,4,3); 1 gap> TDesignLambdas(2,43,7,1); [ 43, 7, 1 ] gap> TDesignBlockMultiplicityBound(2,43,7,1); 0 gap> # The DESIGN package knows the Bruck-Ryser-Chowla Theorem. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The structure of a block design in the DESIGN package gap> # ----------------------------------------------------- gap> # gap> # In DESIGN, a block design D is stored as a record, with gap> # mandatory components isBlockDesign, v, and blocks. gap> # gap> # The isBlockDesign component is set to true to specify that gap> # the record is a DESIGN package block design. gap> # gap> # The component v is the number of points of D. gap> # gap> # The points of D are 1,2,...,D.v, but they may also be given gap> # *names* in the optional component pointNames, with D.pointNames[i] gap> # the name of point i. gap> # gap> # The blocks component must be a sorted list of the blocks of D gap> # (including any repeats), with each block being a sorted list of gap> # points (including any repeats). gap> # gap> # A block design record may also have some optional components which gap> # store information about the design. gap> # gap> # A non-expert user should only use functions in the DESIGN package to gap> # create block design records and their components. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Simple DESIGN example gap> # --------------------- gap> # gap> A:=AGPointFlatBlockDesign(2,3,1); # affine plane of order 3 rec( autSubgroup := Group([ (4,7)(5,8)(6,9), (2,7,6)(3,4,8), (1,4,7)(2,5,8) (3,6,9) ]), blocks := [ [ 1, 2, 3 ], [ 1, 4, 7 ], [ 1, 5, 9 ], [ 1, 6, 8 ], [ 2, 4, 9 ], [ 2, 5, 8 ], [ 2, 6, 7 ], [ 3, 4, 8 ], [ 3, 5, 7 ], [ 3, 6, 9 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ], isBlockDesign := true, pointNames := [ [ 0*Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0 ], [ 0*Z(3), Z(3) ], [ Z(3)^0, 0*Z(3) ], [ Z(3)^0, Z(3)^0 ], [ Z(3)^0, Z(3) ], [ Z(3), 0*Z(3) ], [ Z(3), Z(3)^0 ], [ Z(3), Z(3) ] ], v := 9 ) gap> AllTDesignLambdas(A); [ 12, 4, 1 ] gap> # gap> # Given a block design D the function call gap> # gap> # AllTDesignLambdas( D ) gap> # gap> # returns the empty list if D is not a t-design. gap> # Otherwise, D is a binary block design with constant block size k, gap> # say, and this function returns an immutable list L of length T+1, gap> # where T is the maximum t <= k such that D is a t-design, and, for gap> # i=1,...,T+1, L[i] is equal to the (constant) number of blocks of gap> # D containing an (i-1)-subset of the point-set of D. gap> # gap> Size(AutomorphismGroup(A)); 432 gap> MakeResolutionsComponent(A); gap> A; rec( allTDesignLambdas := [ 12, 4, 1 ], autGroup := Group([ (1,2)(5,6)(7,9), (2,3)(5,6)(8,9), (2,4)(3,7)(6,8), (4,5,6)(7,9,8), (4,7)(5,8)(6,9) ]), autSubgroup := Group([ (4,7)(5,8)(6,9), (2,7,6)(3,4,8), (1,4,7)(2,5,8) (3,6,9) ]), blockSizes := [ 3 ], blocks := [ [ 1, 2, 3 ], [ 1, 4, 7 ], [ 1, 5, 9 ], [ 1, 6, 8 ], [ 2, 4, 9 ], [ 2, 5, 8 ], [ 2, 6, 7 ], [ 3, 4, 8 ], [ 3, 5, 7 ], [ 3, 6, 9 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ], isBinary := true, isBlockDesign := true, isSimple := true, pointNames := [ [ 0*Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0 ], [ 0*Z(3), Z(3) ], [ Z(3)^0, 0*Z(3) ], [ Z(3)^0, Z(3)^0 ], [ Z(3)^0, Z(3) ], [ Z(3), 0*Z(3) ], [ Z(3), Z(3)^0 ], [ Z(3), Z(3) ] ], r := 4, resolutions := rec( allClassesRepresented := true, list := [ rec( autGroup := Group([ (1,2)(5,6)(7,9), (2,3)(5,6)(8,9), (2,4)(3,7) (6,8), (1,3,2)(7,8,9), (2,3)(5,6)(8,9), (1,2,3)(4,5,6) (7,8,9) ]), partition := [ rec( blocks := [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ], isBlockDesign := true, pointNames := [ [ 0*Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0 ], [ 0*Z(3), Z(3) ], [ Z(3)^0, 0*Z(3) ], [ Z(3)^0, Z(3)^0 ], [ Z(3)^0, Z(3) ], [ Z(3), 0*Z(3) ], [ Z(3), Z(3)^0 ], [ Z(3), Z(3) ] ] , v := 9 ), rec( blocks := [ [ 1, 4, 7 ], [ 2, 5, 8 ], [ 3, 6, 9 ] ], isBlockDesign := true, pointNames := [ [ 0*Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0 ], [ 0*Z(3), Z(3) ], [ Z(3)^0, 0*Z(3) ], [ Z(3)^0, Z(3)^0 ], [ Z(3)^0, Z(3) ], [ Z(3), 0*Z(3) ], [ Z(3), Z(3)^0 ], [ Z(3), Z(3) ] ] , v := 9 ), rec( blocks := [ [ 1, 5, 9 ], [ 2, 6, 7 ], [ 3, 4, 8 ] ], isBlockDesign := true, pointNames := [ [ 0*Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0 ], [ 0*Z(3), Z(3) ], [ Z(3)^0, 0*Z(3) ], [ Z(3)^0, Z(3)^0 ], [ Z(3)^0, Z(3) ], [ Z(3), 0*Z(3) ], [ Z(3), Z(3)^0 ], [ Z(3), Z(3) ] ] , v := 9 ), rec( blocks := [ [ 1, 6, 8 ], [ 2, 4, 9 ], [ 3, 5, 7 ] ], isBlockDesign := true, pointNames := [ [ 0*Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0 ], [ 0*Z(3), Z(3) ], [ Z(3)^0, 0*Z(3) ], [ Z(3)^0, Z(3)^0 ], [ Z(3)^0, Z(3) ], [ Z(3), 0*Z(3) ], [ Z(3), Z(3)^0 ], [ Z(3), Z(3) ] ] , v := 9 ) ] ) ], pairwiseNonisomorphic := true ), v := 9 ) gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The function BlockDesign gap> # ------------------------ gap> # gap> # gap> # The DESIGN package function BlockDesign gives a straightforward gap> # way of constructing a block design. gap> # gap> # gap> # Let v be a positive integer and B be a non-empty list of non-empty gap> # sorted lists of elements of [1..v]. gap> # gap> # Then gap> # gap> # BlockDesign( v, B ) gap> # gap> # returns the block design with point-set [1..v] and block multiset C, gap> # where C is SortedList(B). gap> # gap> # Where G is a group of permutations of [1..v], the function call gap> # gap> # BlockDesign(v, B, G) gap> # gap> # returns the block design with point-set [1..v] and block multiset C, gap> # where C is the sorted list of the concatenation of the G-orbits of the gap> # elements of B. gap> # gap> # gap> # Example gap> # ------- gap> # gap> v:=5; 5 gap> D:=BlockDesign(v,[[1,2,3],[1,2,3]],SymmetricGroup([1..v])); rec( autSubgroup := Sym( [ 1 .. 5 ] ), blocks := [ [ 1, 2, 3 ], [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 3, 4 ], [ 1, 3, 5 ], [ 1, 3, 5 ], [ 1, 4, 5 ], [ 1, 4, 5 ], [ 2, 3, 4 ], [ 2, 3, 4 ], [ 2, 3, 5 ], [ 2, 3, 5 ], [ 2, 4, 5 ], [ 2, 4, 5 ], [ 3, 4, 5 ], [ 3, 4, 5 ] ], isBlockDesign := true, v := 5 ) gap> Size(AutomorphismGroup(D)); 120 gap> AllTDesignLambdas(D); [ 20, 12, 6, 2 ] gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Automorphism groups and isomorphism testing in DESIGN gap> # ----------------------------------------------------- gap> # gap> # gap> # Let A and B be block designs. gap> # gap> # Then A and B are *isomorphic* if there is an *isomorphism* gap> # from A to B, that is, a bijection from the points of A gap> # to those of B which applied to the block multiset of gap> # A yields the block multiset of B. gap> # gap> # An *automorphism* of A is an isomorphism from A to gap> # itself. The set of all automorphisms of A forms a group, gap> # the *automorphism group* of A. gap> # gap> # gap> # The DESIGN package contains functionality to test block design gap> # isomorphism and to calculate the automorphism group of a block gap> # design, for binary block designs (equivalently, block designs gap> # where every block is a set). gap> # gap> # To do this, the DESIGN package uses the graph automorphism group gap> # and isomorphism testing functionality in GRAPE. gap> # gap> # gap> # Now suppose that A and B are binary block designs in the DESIGN gap> # package. gap> # gap> # Then the function call gap> # gap> # AutomorphismGroup( A ) gap> # gap> # returns the automorphism group of A, which can then be gap> # studied using the permutation group functionality in GAP. gap> # gap> # gap> # The function call gap> # gap> # IsIsomorphicBlockDesign( A, B ) gap> # gap> # returns returns true if the block designs are isomorphic, gap> # and false otherwise. gap> # gap> # gap> # When comparing more than two binary block designs for pairwise isomorphism, gap> # you should use the function BlockDesignIsomorhismClassRepresentatives. gap> # gap> # Where L is a list of binary block designs in DESIGN package format, gap> # the function call gap> # gap> # BlockDesignIsomorphismClassRepresentatives( L ) gap> # gap> # returns a list consisting of pairwise non-isomorphic elements of L, gap> # representing all the isomorphism classes of elements of L. gap> # gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # The function BlockDesigns gap> # ------------------------- gap> # gap> # gap> # The most important DESIGN package function is BlockDesigns, gap> # which can construct and classify block designs satisfying a wide gap> # range of user-specified properties (although this may require gap> # a very large amount of store or time depending on the problem). gap> # gap> # The calling syntax is gap> # gap> # BlockDesigns( param ) gap> # gap> # and the function returns a list of block designs whose properties are gap> # specified by the user in the record param, as described in the gap> # full function documentation (see ?BlockDesigns ). gap> # gap> # Only binary block designs with the given properties are generated if gap> # param.blockDesign is unbound or is a binary block design, which gap> # we assume to be the case in these lectures. gap> # gap> # The properties which must be specified via param are: gap> # gap> # - the number v of points (the point set is then [1..v]), gap> # gap> # - the possible block sizes gap> # gap> # - for one given t >=0, for each t-subset T of the points, gap> # the number of blocks containing T (this number may be constant gap> # or may depend on T). gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Examples gap> # -------- gap> # gap> # We classify the 5-(12,6,1) designs, proving that the gap> # "small Mathieu design" is the unique such design (up to isomorphism). gap> # gap> designs := BlockDesigns( rec( v:=12, > blockSizes:=[6], > tSubsetStructure:=rec(t:=5, lambdas:=[1] ) ) );; gap> gap> Length(designs); 1 gap> List(designs,AllTDesignLambdas); # as a check [ [ 132, 66, 30, 12, 4, 1 ] ] gap> List(designs,d->Size(AutomorphismGroup(d))); [ 95040 ] gap> # gap> # We classify, up to isomorphism, the binary block designs having 11 gap> # points, such that each block has size 4 or 5, and every pair of gap> # distinct points is contained in exactly two blocks. gap> # gap> designs := BlockDesigns( rec( v:=11, > blockSizes:=[4,5], > tSubsetStructure:=rec(t:=2, lambdas:=[2] ) ) );; gap> Length(designs); 5 gap> List(designs,BlockSizes); [ [ 5 ], [ 4, 5 ], [ 4, 5 ], [ 4, 5 ], [ 4, 5 ] ] gap> List(designs,BlockNumbers); [ [ 11 ], [ 10, 5 ], [ 10, 5 ], [ 10, 5 ], [ 10, 5 ] ] gap> List(designs,AllTDesignLambdas); [ [ 11, 5, 2 ], [ ], [ ], [ ], [ ] ] gap> List(designs,d->Size(AutomorphismGroup(d))); [ 660, 6, 8, 12, 120 ] gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Further properties which may optionally be specified gap> # to the function BlockDesigns via param include: gap> # gap> # - for each given possible block size, the maximum multiplicity of a gap> # block of that size gap> # gap> # - for each given possible block size, the number of blocks of that size gap> # gap> # - the possible sizes of intersections of pairs of blocks of given sizes gap> # gap> # - the total number b of blocks gap> # gap> # - a replication number r (that is, specifying that every point gap> # is in exactly r blocks) gap> # gap> # - a permutation group G on the point set [1..v], such that gap> # two designs are considered to be isomorphic if one is in the gap> # G-orbit of the other. If param.blockDesign is unbound, the default gap> # is a group G giving the usual notion of block design isomorphism. gap> # gap> # - a subgroup H of G such that H is required to be a subgroup gap> # of the automorphism group of each returned design. The default is gap> # H=Group(()), the trivial permutation group. gap> # gap> # - whether the user wants a single design with the specified gap> # properties (if one exists), a list of G-orbit representatives gap> # of all such designs (i.e. isomorphism class gap> # representatives as determined by G; this is the default), gap> # or a list of such designs containing at least one representative gap> # from each G-orbit. gap> # gap> # gap> # Example gap> # ------- gap> # gap> # We classify, up to isomorphism, the 1-(14,3,6) designs gap> # invariant under the group gap> # gap> # H = < (1,2,3)(4,5,6)(7,8,9)(10,11,12) >, gap> # gap> # such that every pair of distinct blocks intersect in at most 1 point. gap> # These are precisely the H-invariant partial linear spaces with 14 points gap> # and parameters (2,5). gap> # gap> H := Group( [(1,2,3)(4,5,6)(7,8,9)(10,11,12)] ); Group([ (1,2,3)(4,5,6)(7,8,9)(10,11,12) ]) gap> designs := BlockDesigns( rec( v:=14, > blockSizes:=[3], > tSubsetStructure:=rec(t:=1, lambdas:=[6] ), > requiredAutSubgroup:=H, > blockIntersectionNumbers:=[[ [0,1] ]] ));; gap> Length(designs); 53 gap> Collected(List(designs,AllTDesignLambdas)); [ [ [ 28, 6 ], 53 ] ] gap> Collected(List(designs,d->Size(AutomorphismGroup(d)))); [ [ 3, 37 ], [ 6, 2 ], [ 12, 4 ], [ 21, 2 ], [ 24, 5 ], [ 96, 1 ], [ 192, 1 ], [ 1344, 1 ] ] gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Computing subdesigns using the function BlockDesigns gap> # ---------------------------------------------------- gap> # gap> # gap> # Here a *subdesign* of a block design D means a block design gap> # with the same point set as D and whose block multiset is a gap> # submultiset of the blocks of D. gap> # gap> # gap> # Setting param.blockDesign to be a block design D asks gap> # BlockDesigns( param ) to construct subdesigns of D with gap> # the given properties. See ?BlockDesigns. gap> # gap> # gap> # Example gap> # ------- gap> # gap> # In this example we determine certain "Sylvester designs", gap> # which are highly efficient designs from an experimental gap> # design viewpoint. See: gap> # gap> # R.A. Bailey, P.J. Cameron, L.H. Soicher and E.R. Williams, gap> # Substitutes for the non-existent square lattice designs for 36 varieties, gap> # Journal of Agricultural, Biological and Environmental gap> # Statistics 25 (2020), 487–499. Available online (open-access) at gap> # https://doi.org/10.1007/s13253-020-00388-1 gap> # gap> # gap> # A *Sylvester design* is a 1-(36,6,8) design, such that gap> # gap> # - if a and b are distinct points then {a,b} is contained gap> # in just 1 or 2 blocks, and gap> # gap> # - the graph gamma on 36 vertices whose edges are those gap> # {a,b} contained in 2 blocks is isomorphic to the Sylvester graph. gap> # gap> edges:=UndirectedEdges(Sylvester);; gap> syl2:=DistanceGraph(Sylvester,2);; gap> edges2:=UndirectedEdges(syl2);; gap> GlobalParameters(syl2); [ [ 0, 0, 20 ], [ 1, 11, 8 ], [ -1, -1, 0 ] ] gap> syl3:=DistanceGraph(Sylvester,3);; gap> edges3:=UndirectedEdges(syl3);; gap> GlobalParameters(syl3); [ [ 0, 0, 10 ], [ 1, 4, 5 ], [ 2, 8, 0 ] ] gap> IsIsomorphicGraph(syl3,HammingGraph(2,6)); true gap> comp3:=ComplementGraph(syl3);; gap> K:=CompleteSubgraphsOfGivenSize(comp3,6,2); [ [ 1, 2, 4, 8, 9, 35 ], [ 1, 2, 4, 8, 19, 28 ], [ 1, 2, 4, 9, 11, 30 ], [ 1, 2, 4, 11, 19, 36 ], [ 1, 2, 5, 19, 24, 36 ] ] gap> K:=Union(Orbits(comp3.group,K,OnSets));; gap> Length(K); 720 gap> L:=CompleteSubgraphsOfGivenSize(syl3,6,2); [ [ 1, 10, 13, 16, 22, 23 ] ] gap> L:=Union(Orbits(syl3.group,L,OnSets));; gap> Length(L); 12 gap> BD:=BlockDesign(36,Union(K,L));; gap> # gap> # We are here interested in those Sylvester designs that are gap> # subdesigns of BD. gap> # gap> S := BlockDesigns(rec(v:=36, > blockSizes:=[6], > blockDesign:=BD, # We want subdesigns of BD. > tSubsetStructure:= > rec(t:=2, partition:=[Union(edges2,edges3),edges],lambdas:=[1,2]), > isoGroup:=AutomorphismGroup(Sylvester)));; gap> Length(S); 4 gap> # gap> # The elements of S are (up to the action of the automorphism group gap> # of the Sylvester graph, and so up to isomorphism) the Sylvester designs gap> # whose blocks come from the rows, columns, and transversals of the gap> # 6x6 array defined by the distance-3 graph of the Sylvester graph. gap> # gap> for design in S do > Print("\nSize of automorphism group = ", > Size(AutomorphismGroup(design))); > Print("\nStatistical efficiency A-measure = ", > BlockDesignEfficiency(design).A,"\n"); > Print("\n------------------------------------------------------\n"); > od; Size of automorphism group = 144 Statistical efficiency A-measure = 7007/8196 ------------------------------------------------------ Size of automorphism group = 16 Statistical efficiency A-measure = 7007/8196 ------------------------------------------------------ Size of automorphism group = 72 Statistical efficiency A-measure = 7007/8196 ------------------------------------------------------ Size of automorphism group = 1440 Statistical efficiency A-measure = 7007/8196 ------------------------------------------------------ gap> # gap> # gap> # Challenge problem: Classify *all* the Sylvester designs. gap> # gap> # gap> # ===================================================================== gap> # gap> # gap> # Partitioning block designs in DESIGN gap> # ------------------------------------ gap> # gap> # gap> # The DESIGN package function PartitionsIntoBlockDesigns constructs gap> # partitions of (the block multiset of) a given block design D, such gap> # that the subdesigns of D whose block multisets are the parts of this gap> # partition each have the same user-specified properties. gap> # gap> # See ?PartitionsIntoBlockDesigns for full details. gap> # gap> # For example, given a block design D having v points and gap> # each of whose blocks has size k, we can classify the gap> # resolutions of D by classifying the partitions of D into gap> # 1-(v,k,1) designs, up to the action of the automorphism group of D. gap> # gap> # gap> for design in S do > partitions:=PartitionsIntoBlockDesigns(rec(v:=36, blockSizes:=[6], > blockDesign:=design, tSubsetStructure:=rec(t:=1,lambdas:=[1]), > isoGroup:=AutomorphismGroup(design))); > Print("\nNumber of isomorphism classes of resolutions = ", > Length(partitions)); > partitions:=PartitionsIntoBlockDesigns(rec(v:=36, blockSizes:=[6], > blockDesign:=design, tSubsetStructure:=rec(t:=1,lambdas:=[1]), > isoGroup:=Group(()) )); > Print("\nNumber of resolutions = ",Length(partitions)); > Print("\n------------------------------------------------------\n"); > od; Number of isomorphism classes of resolutions = 1 Number of resolutions = 4 ------------------------------------------------------ Number of isomorphism classes of resolutions = 0 Number of resolutions = 0 ------------------------------------------------------ Number of isomorphism classes of resolutions = 1 Number of resolutions = 2 ------------------------------------------------------ Number of isomorphism classes of resolutions = 1 Number of resolutions = 2 ------------------------------------------------------ gap> # gap> #