1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%A classify.tex DESIGN documentation Leonard Soicher
%
%
%
\def\GRAPE{\sf GRAPE}
\def\DESIGN{\sf DESIGN}
\def\nauty{\it nauty}
\def\Aut{{\rm Aut}\,}
\Chapter{Classifying block designs}
This chapter describes the function `BlockDesigns' which can classify
block designs with given properties. The possible properties a user
can specify are many and varied, and are described below. Depending on
the properties, this function can handle block designs with up to about
20 points (sometimes more and sometimes less, depending on the problem).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{The function BlockDesigns}
\>BlockDesigns( <param> )
This function returns a list <DL> of block designs whose properties are
specified by the user in the record <param>. The precise interpretation
of the output depends on <param>, described below. Only binary designs
are generated by this function, if `<param>.blockDesign' is unbound
or is a binary design.
The required components of <param> are `v', `blockSizes', and
`tSubsetStructure'.
`<param>.v' must be a positive integer, and specifies that for each block
design in the list <DL>, the points are 1,...,`<param>.v'.
`<param>.blockSizes' must be a set of positive integers, and specifies
that the block sizes of each block design in <DL> will be contained in
`<param>.blockSizes'.
`<param>.tSubsetStructure' must be a record, having
components `t', `partition', and `lambdas'. Let <t>
be equal to `<param>.tSubsetStructure.t', <partition>
be `<param>.tSubsetStructure.partition', and <lambdas> be
`<param>.tSubsetStructure.lambdas'. Then <t> must be a non-negative
integer, <partition> must be a list of non-empty sets of <t>-subsets of
`[1..<param>.v]', forming an ordered partition of all the <t>-subsets of
`[1..<param>.v]', and <lambdas> must be a list of distinct non-negative
integers (not all zero) of the same length as <partition>. This specifies
that for each design in <DL>, each <t>-subset in `<partition>[<i>]'
will occur exactly `<lambdas>[<i>]' times, counted over all blocks of
the design. For binary designs, this means that each <t>-subset in
`<partition>[<i>]' is contained in exactly `<lambdas>[<i>]' blocks.
The `partition' component is optional if <lambdas> has length 1.
We require that <t> is less than or equal to each element of
`<param>.blockSizes', and if `<param>.blockDesign' is bound,
then each block of `<param>.blockDesign' must contain at least <t>
distinct elements. Note that if `<param>.tSubsetStructure' is equal to
`rec(t:=0,lambdas:=[<b>])', for some positive integer <b>, then all
that is being specified is that each design in <DL> must have exactly
<b> blocks.
The optional components of <param> are used to specify additional
constraints on the designs in <DL> or to change default parameter
values. These optional components are `blockDesign', `r', `b',
`blockNumbers', `blockIntersectionNumbers', `blockMaxMultiplicities',
`isoGroup', `requiredAutSubgroup', and `isoLevel'.
`<param>.blockDesign' must be a block design with `<param>.blockDesign.v'
equal to `<param>.v'. Then each block multiset of a design in <DL> will
be a submultiset of `<param>.blockDesign.blocks' (that is, each block of
a design <D> in <DL> will be a block of `<param>.blockDesign', and the
multiplicity of a block of <D> will be less than or equal to that block's
multiplicity in `<param>.blockDesign'). The `blockDesign' component is
useful for the computation of subdesigns, such as parallel classes.
`<param>.r' must be a positive integer, and specifies that in each design
in <DL>, each point will occur exactly `<param>.r' times in the list of
blocks. In other words, each design in <DL> will have replication number
`<param>.r'.
`<param>.b' must be a positive integer, and specifies that each design
in <DL> will have exactly `<param>.b' blocks.
`<param>.blockNumbers' must be a list of non-negative integers, the <i>-th
element of which specifies the number of blocks whose size is equal
to `<param>.blockSizes[<i>]' (for each design in <DL>). The length of
`<param>.blockNumbers' must equal that of `<param>.blockSizes', and at
least one entry of `<param>.blockNumbers' must be positive.
`<param>.blockIntersectionNumbers' must be a symmetric matrix of sets
of non-negative integers, the `[<i>][<j>]'-element of which specifies
the set of possible sizes for the intersection of a block $B$ of
size `<param>.blockSizes[<i>]' with a different block (but possibly
a repeat of $B$) of size `<param>.blockSizes[<j>]' (for each design
in <DL>). In the case of multisets, we take the multiplicity of an
element in the intersection to be the minimum of its multiplicities in
the multisets being intersected; for example, the intersection of
`[1,1,1,2,2,3]' with `[1,1,2,2,2,4]' is `[1,1,2,2]', having size 4. The
dimension of `<param>.blockIntersectionNumbers' must equal the length of
`<param>.blockSizes'.
`<param>.blockMaxMultiplicities' must be a list of non-negative integers,
the <i>-th element of which specifies an upper bound on the multiplicity
of a block whose size is equal to `<param>.blockSizes[<i>]' (for each
design in <DL>). The length of `<param>.blockMaxMultiplicities' must
equal that of `<param>.blockSizes'.
Let <G> be the automorphism group of `<param>.blockDesign' if bound, and
<G> be `SymmetricGroup(<param>.v)' otherwise. Let <H> be the subgroup of
<G> stabilizing `<param>.tSubsetStructure.partition' (as an ordered list
of sets of sets) if bound, and <H> be equal to <G> otherwise.
`<param>.isoGroup' must be a subgroup of <H>, and specifies that we
consider two designs with the required properties to be *equivalent*
if their block multisets are in the same orbit of `<param>.isoGroup'
(in its action on multisets of multisets of `[1..<param>.v]'). The
default for `<param>.isoGroup' is <H>. Thus, if `<param>.blockDesign'
and `<param>.isoGroup' are both unbound, equivalence is the same as
block-design isomorphism for the required designs.
`<param>.requiredAutSubgroup' must be a subgroup of `<param>.isoGroup',
and specifies that each design in <DL> must be invariant under
`<param>.requiredAutSubgroup' (in its action on multisets of multisets of
`[1..<param>.v]'). The default for `<param>.requiredAutSubgroup' is the
trivial permutation group.
`<param>.isoLevel' must be 0, 1, or 2 (the default is 2). The value
0 specifies that <DL> will contain at most one block design, and will
contain one block design with the required properties if and only if
such a block design exists; the value~1 specifies that <DL> will contain
(perhaps properly) a list of `<param>.isoGroup'-orbit representatives of
the required designs; the value 2 specifies that <DL> will consist
precisely of `<param>.isoGroup'-orbit representatives of the required
designs.
For an example, we classify up to isomorphism the 2-(15,3,1) designs
invariant under a semi-regular group of automorphisms of order 5, and
then classify all parallel classes of these designs, up to the action
of the automorphism groups of these designs.
\beginexample
gap> DL:=BlockDesigns(rec(
> v:=15,blockSizes:=[3],
> tSubsetStructure:=rec(t:=2,lambdas:=[1]),
> requiredAutSubgroup:=
> Group((1,2,3,4,5)(6,7,8,9,10)(11,12,13,14,15))));;
gap> List(DL,AllTDesignLambdas);
[ [ 35, 7, 1 ], [ 35, 7, 1 ], [ 35, 7, 1 ] ]
gap> List(DL,D->Size(AutGroupBlockDesign(D)));
[ 20160, 5, 60 ]
gap> parclasses:=List(DL,D->
> BlockDesigns(rec(
> blockDesign:=D,
> v:=15,blockSizes:=[3],
> tSubsetStructure:=rec(t:=1,lambdas:=[1]))));
[ [ rec( isBlockDesign := true, v := 15,
blocks := [ [ 1, 2, 6 ], [ 3, 4, 8 ], [ 5, 7, 14 ], [ 9, 12, 15 ],
[ 10, 11, 13 ] ],
tSubsetStructure := rec( t := 1, lambdas := [ 1 ] ),
isBinary := true, isSimple := true, blockSizes := [ 3 ],
blockNumbers := [ 5 ], r := 1,
autSubgroup := Group([ (2,6)(3,11)(4,10)(5,14)(8,13)(12,15),
(2,6)(4,8)(5,12)(7,9)(10,13)(14,15),
(2,6)(3,12)(4,9)(7,14)(8,15)(11,13),
(3,12,5)(4,15,7)(8,9,14)(10,11,13),
(1,6,2)(3,4,8)(5,7,14)(9,12,15)(10,11,13),
(1,8,11,2,3,10)(4,13,6)(5,15,14,9,7,12) ]) ) ],
[ rec( isBlockDesign := true, v := 15,
blocks := [ [ 1, 7, 12 ], [ 2, 8, 13 ], [ 3, 9, 14 ],
[ 4, 10, 15 ], [ 5, 6, 11 ] ],
tSubsetStructure := rec( t := 1, lambdas := [ 1 ] ),
isBinary := true, isSimple := true, blockSizes := [ 3 ],
blockNumbers := [ 5 ], r := 1,
autSubgroup := Group([ (1,5,4,3,2)(6,10,9,8,7)(11,15,14,13,12) ]) )
],
[ rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 2, 6 ], [ 3, 10, 13
], [ 4, 11, 12 ], [ 5, 7, 15 ], [ 8, 9, 14 ] ],
tSubsetStructure := rec( t := 1, lambdas := [ 1 ] ),
isBinary := true, isSimple := true, blockSizes := [ 3 ],
blockNumbers := [ 5 ], r := 1,
autSubgroup := Group([ (1,2)(3,5)(7,10)(8,9)(11,12)(13,15),
(1,11,8)(2,12,9)(3,13,10)(4,14,6)(5,15,7) ]) ),
rec( isBlockDesign := true, v := 15,
blocks := [ [ 1, 8, 11 ], [ 2, 9, 12 ], [ 3, 10, 13 ],
[ 4, 6, 14 ], [ 5, 7, 15 ] ],
tSubsetStructure := rec( t := 1, lambdas := [ 1 ] ),
isBinary := true, isSimple := true, blockSizes := [ 3 ],
blockNumbers := [ 5 ], r := 1,
autSubgroup := Group([ (1,2)(3,5)(7,10)(8,9)(11,12)(13,15),
(1,3,4,2)(6,9,8,10)(11,13,14,12),
(1,3,5,2,4)(6,8,10,7,9)(11,13,15,12,14),
(1,11,8)(2,12,9)(3,13,10)(4,14,6)(5,15,7) ]) ) ] ]
gap> List(parclasses,Length);
[ 1, 1, 2 ]
gap> List(parclasses,L->List(L,parclass->Size(parclass.autSubgroup)));
[ [ 360 ], [ 5 ], [ 6, 60 ] ]
\endexample
|
