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