This chapter describes the function `PartitionsIntoBlockDesigns`

which can
classify partitions of (the block multiset of) a given block design into
(the block multisets of) block designs having user-specified properties.
We also describe `MakeResolutionsComponent`

which is useful for the
special case when the desired partitions are resolutions.

`PartitionsIntoBlockDesigns( `

` )`

Let `D` equal `param``.blockDesign`

. This function returns a list `PL`
of partitions of (the block multiset of) `D`. Each element of `PL` is a
record with one component `partition`

, and, in most cases, a component
`autGroup`

. The `partition`

component gives a list `P` of block designs,
all with the same point set as `D`, such that the list of (the block
multisets of) the designs in `P``.partition`

forms a partition of (the
block multiset of) `D`. The component `P``.autGroup`

, if bound, gives
the automorphism group of the partition, which is the stabilizer of the
partition in the automorphism group of `D`. The precise interpretation
of the output depends on `param`, described below.

The required components of `param` are `blockDesign`

, `v`

, `blockSizes`

,
and `tSubsetStructure`

.

`param``.blockDesign`

is the block design to be partitioned.

`param``.v`

must be a positive integer, and specifies that for each block
design in each partition in `PL`, the points are 1,...,`param``.v`

.
It is required that `param``.v`

be equal to `param``.blockDesign.v`

.

`param``.blockSizes`

must be a set of positive integers, and specifies
that the block sizes of each block design in each partition in `PL`
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 each partition in `PL`, 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 that each block of `param``.blockDesign`

contains at least `t` distinct elements.

The optional components of `param` are used to specify additional
constraints on the partitions in `PL`, or to change default parameter
values. These optional components are `r`

, `b`

, `blockNumbers`

,
`blockIntersectionNumbers`

, `blockMaxMultiplicities`

, `isoGroup`

,
`requiredAutSubgroup`

, and `isoLevel`

. Note that the last three of these
optional components refer to the partitions and not to the block designs
in a partition.

`param``.r`

must be a positive integer, and specifies that in each design
in each partition in `PL`, each point must occur exactly `param``.r`

times in the list of blocks.

`param``.b`

must be a positive integer, and specifies that each design
in each partition in `PL` has 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``]`

(in each design in each partition in `PL`). 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``]`

(in each design in each partition
in `PL`). 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 each partition in `PL`). The length of
`param``.blockMaxMultiplicities`

must equal that of `param``.blockSizes`

.

`param``.isoGroup`

must be a subgroup of the automorphism group of
`param``.blockDesign`

. We consider two elements of `PL` to be
**equivalent** if they are in the same orbit of `param``.isoGroup`

(in its action on multisets of block multisets). The default for
`param``.isoGroup`

is the automorphism group of `param``.blockDesign`

.

`param``.requiredAutSubgroup`

must be a subgroup of `param``.isoGroup`

,
and specifies that each partition in `PL` must be invariant under
`param``.requiredAutSubgroup`

(in its action on multisets of block
multisets). 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 `PL` will contain at most one partition, and will contain
one partition with the required properties if and only if such a partition
exists; the value 1 specifies that `PL` will contain (perhaps properly)
a list of `param``.isoGroup`

orbit-representatives of the required
partitions; the value 2 specifies that `PL` will consist precisely of
`param``.isoGroup`

-orbit representatives of the required partitions.

For an example, we first classify up to isomorphism the 2-(15,3,1)
designs invariant under a semi-regular group of automorphisms of order 5,
and then use `PartitionsIntoBlockDesigns`

to classify all the resolutions
of these designs, up to the actions of the respective automorphism groups
of the designs.

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,D->Size(AutGroupBlockDesign(D))); [ 20160, 5, 60 ] gap> PL:=PartitionsIntoBlockDesigns(rec( > blockDesign:=DL[1], > v:=15,blockSizes:=[3], > tSubsetStructure:=rec(t:=1,lambdas:=[1]))); [ rec( partition := [ rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 2, 6 ], [ 3, 4, 8 ], [ 5, 7, 14 ], [ 9, 12, 15 ], [ 10, 11, 13 ] ] ), rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 3, 11 ], [ 2, 4, 12 ], [ 5, 6, 8 ], [ 7, 13, 15 ], [ 9, 10, 14 ] ] ), rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 4, 14 ], [ 2, 5, 15 ], [ 3, 10, 12 ], [ 6, 7, 11 ], [ 8, 9, 13 ] ] ), rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 5, 10 ], [ 2, 9, 11 ], [ 3, 14, 15 ], [ 4, 6, 13 ], [ 7, 8, 12 ] ] ), rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 7, 9 ], [ 2, 8, 10 ], [ 3, 5, 13 ], [ 4, 11, 15 ], [ 6, 12, 14 ] ] ), rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 8, 15 ], [ 2, 13, 14 ], [ 3, 6, 9 ], [ 4, 7, 10 ], [ 5, 11, 12 ] ] ), rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 12, 13 ], [ 2, 3, 7 ], [ 4, 5, 9 ], [ 6, 10, 15 ], [ 8, 11, 14 ] ] ) ], autGroup := Group([ (1,10)(2,11)(3,8)(6,13)(7,14)(12,15), (1,13)(2,11)(3,14)(4,5)(6,10)(7,8), (1,13,7)(2,11,5)(6,10,14)(9,12,15), (2,11,5,15,4,9,12)(3,10,8,14,7,13,6) ]) ), rec( partition := [ rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 2, 6 ], [ 3, 4, 8 ], [ 5, 7, 14 ], [ 9, 12, 15 ], [ 10, 11, 13 ] ] ), rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 3, 11 ], [ 2, 4, 12 ], [ 5, 6, 8 ], [ 7, 13, 15 ], [ 9, 10, 14 ] ] ), rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 4, 14 ], [ 2, 5, 15 ], [ 3, 10, 12 ], [ 6, 7, 11 ], [ 8, 9, 13 ] ] ), rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 5, 10 ], [ 2, 13, 14 ], [ 3, 6, 9 ], [ 4, 11, 15 ], [ 7, 8, 12 ] ] ), rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 7, 9 ], [ 2, 8, 10 ], [ 3, 14, 15 ], [ 4, 6, 13 ], [ 5, 11, 12 ] ] ), rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 8, 15 ], [ 2, 9, 11 ], [ 3, 5, 13 ], [ 4, 7, 10 ], [ 6, 12, 14 ] ] ), rec( isBlockDesign := true, v := 15, blocks := [ [ 1, 12, 13 ], [ 2, 3, 7 ], [ 4, 5, 9 ], [ 6, 10, 15 ], [ 8, 11, 14 ] ] ) ], autGroup := Group([ (1,15)(2,9)(3,4)(5,7)(6,12)(10,13), (1,12)(2,9)(3,5)(4,7)(6,15)(8,14), (1,14)(2,5)(3,8)(6,7)(9,12)(10,13), (1,8,10)(2,5,15)(3,14,13)(4,9,12) ]) ) ] gap> List(PL,resolution->Size(resolution.autGroup)); [ 168, 168 ] gap> PL:=PartitionsIntoBlockDesigns(rec( > blockDesign:=DL[2], > v:=15,blockSizes:=[3], > tSubsetStructure:=rec(t:=1,lambdas:=[1]))); [ ] gap> PL:=PartitionsIntoBlockDesigns(rec( > blockDesign:=DL[3], > v:=15,blockSizes:=[3], > tSubsetStructure:=rec(t:=1,lambdas:=[1]))); [ ]

`MakeResolutionsComponent( `

` )`

`MakeResolutionsComponent( `

`, `

` )`

This function computes resolutions of the block design `D`, and stores
the result in `D``.resolutions`

. If `D``.resolutions`

already exists
then it is ignored and overwritten. This function returns no value.

A **resolution** of a block design `D` is a partition of the blocks into
subsets, each of which forms a partition of the point set. We say that
two resolutions `R` and `S` of `D` are **isomorphic** if there is an element
`g` in the automorphism group of `D`, such that the `g`-image of `R`
is `S`. (Isomorphism defines an equivalence relation on the set of
resolutions of `D`.)

The parameter `isolevel` (default 2) determines how many resolutions are
computed: `isolevel`=2 means to classify up to isomorphism, `isolevel`=1
means to determine at least one representative from each isomorphism
class, and `isolevel`=0 means to determine whether or not `D` has
a resolution.

When this function is finished, `D``.resolutions`

will have the following
three components:

`list`

: a list of distinct partitions into block designs forming resolutions
of `D`;

`pairwiseNonisomorphic`

: `true`

, `false`

or `"unknown"`

, depending on the
resolutions in `list`

and what is known. If `isolevel`=0 or `isolevel`=2
then this component will be `true`

;

`allClassesRepresented`

: `true`

, `false`

or `"unknown"`

, depending on the
resolutions in `list`

and what is known. If `isolevel`=1 or `isolevel`=2
then this component will be `true`

.

Note that `D``.resolutions`

may be changed to contain more information
as a side-effect of other functions in the DESIGN package.

gap> L:=BlockDesigns(rec(v:=9,blockSizes:=[3], > tSubsetStructure:=rec(t:=2,lambdas:=[1])));; gap> D:=L[1];; gap> MakeResolutionsComponent(D); gap> D; rec( isBlockDesign := true, v := 9, blocks := [ [ 1, 2, 3 ], [ 1, 4, 5 ], [ 1, 6, 7 ], [ 1, 8, 9 ], [ 2, 4, 6 ], [ 2, 5, 8 ], [ 2, 7, 9 ], [ 3, 4, 9 ], [ 3, 5, 7 ], [ 3, 6, 8 ], [ 4, 7, 8 ], [ 5, 6, 9 ] ], tSubsetStructure := rec( t := 2, lambdas := [ 1 ] ), isBinary := true, isSimple := true, blockSizes := [ 3 ], blockNumbers := [ 12 ], r := 4, autGroup := Group([ (1,2)(5,6)(7,8), (1,3,2)(4,8,7)(5,6,9), (1,2)(4,7)(5,9), (1,2)(4,9)(5,7)(6,8), (1,4,8,6,9,2)(3,5,7) ]), resolutions := rec( list := [ rec( partition := [ rec( isBlockDesign := true, v := 9, blocks := [ [ 1, 2, 3 ], [ 4, 7, 8 ], [ 5, 6, 9 ] ] ), rec( isBlockDesign := true, v := 9, blocks := [ [ 1, 4, 5 ], [ 2, 7, 9 ], [ 3, 6, 8 ] ] ), rec( isBlockDesign := true, v := 9, blocks := [ [ 1, 6, 7 ], [ 2, 5, 8 ], [ 3, 4, 9 ] ] ), rec( isBlockDesign := true, v := 9, blocks := [ [ 1, 8, 9 ], [ 2, 4, 6 ], [ 3, 5, 7 ] ] ) ], autGroup := Group( [ (2,3)(4,5)(6,7)(8,9), (1,3,2)(4,8,7)(5,6,9), (1,8,9)(2,4,6)(3,7,5), (1,2)(5,6)(7,8), (1,2)(4,7)(5,9), (1,2,9,6,8,4)(3,7,5) ]) ) ], pairwiseNonisomorphic := true, allClassesRepresented := true ) )

[Up] [Previous] [Next] [Index]

design manual

November 2011