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

7 Classifying block designs

Sections

  1. The function BlockDesigns

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).

7.1 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.

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

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

    design manual
    November 2011