This chapter describes the function SemiLatinSquareDuals which can
classify semi-Latin squares with certain given properties, and return
a list of their duals as block designs.
Let n and k be positive integers. An (ntimesn)/k semi-Latin square is an n by n array A, whose entries are k-subsets of a kn-set X (the symbol-set), such that each element of X occurs exactly once in each row and exactly once in each column of A. (Thus an (ntimesn)/1 semi-Latin square is the same thing as a Latin square of order n.) For extensive useful information on semi-Latin squares, see http://www.maths.qmul.ac.uk/~rab/sls.html.
A SOMA(k,n) is an (ntimesn)/k semi-Latin square A, with nge2, in which no 2-subset of the symbol-set is contained in more than one entry of A. For extensive useful information on SOMAs, see http://www.maths.qmul.ac.uk/~lsoicher/soma/.
Let A and B be (ntimesn)/k semi-Latin squares. We say that B is (weakly) isomorphic to A if B can be obtained from A by applying one or more of: a row permutation; a column permutation; transposing; renaming the symbols. If transposing is not allowed then we get the concept of strong isomorphism. More formally, B is strongly isomorphic to A if B can be obtained from A by applying one or more of: a row permutation; a column permutation; renaming the symbols.
Let A be an (ntimesn)/k semi-Latin square. Then the dual of A can be represented as a binary block design as follows. The point-set of D is taken to be the Cartesian square of {1,...,n}, with [x,y] representing the [x,y]-entry of A. The blocks of D are in one-to-one correspondence with the symbols of A, with the i-th block of D consisting of the ordered pairs [x,y] such that the i-th symbol of A is contained in the [x,y]-entry of A. Given D, the semi-Latin square A can be recovered, up to the naming of its symbols.
SemiLatinSquareDuals( n, k )
SemiLatinSquareDuals( n, k, maxmult )
SemiLatinSquareDuals( n, k, maxmult, blockintsizes )
SemiLatinSquareDuals( n, k, maxmult, blockintsizes, isolevel )
Let n and k be positive integers. Then this function (which makes
heavy use of the function BlockDesigns) returns a list DL of block
designs which are the duals of the (ntimesn)/k semi-Latin
squares whose properties are specified by the given parameters, described
below. In practice, depending on the specified properties, this function
can be useful for n up to about 6 or 7.
The parameter maxmult, if given, must be a positive integer or
the string "default". If it is a positive integer, then maxmult
specifies an upper bound on the multiplicity of each block in each
semi-Latin square dual in DL. The default value for maxmult (if
omitted or if given as "default") is k, which poses no constraint
on the block multiplicities.
The parameter blockintsizes, if given, must be a set of non-negative
integers or the string "default". If it is given as a set, then
blockintsizes specifies, for each semi-Latin square dual in DL,
the set of possible sizes for the intersection of a block B with a
different block (but possibly a repeat of B). The default value for
blockintsizes (if omitted or if given as "default") is [0..n],
which poses no constraint on the block intersection sizes. Note that
block intersection sizes in the dual of a semi-Latin square correspond
to concurrencies of points in the semi-Latin square itself. Also note
that if nge2 and blockintsizes is specified to be [0,1] then
the (ntimesn)/k semi-Latin squares being considered are SOMA(k,n)s.
The parameter isolevel, if given, must be 0, 1, 2, 3, 4 or the string
"default" (the default value is 2). The value 0 specifies that DL
will contain at most one (semi-Latin square dual given as a) block design,
and will contain one such block design if and only if a semi-Latin square
with the required properties exists. The value 1 specifies that DL
will contain a list of duals representing all weak isomorphism classes
of semi-Latin squares with the required properties (possibly with some
classes represented more than once) and the value 2 specifies that DL
will contain precisely one dual semi-Latin square representative for
each weak isomorphism class of semi-Latin squares with the required
properties. The values 3 and 4 for isolevel play the roles of 1 and 2,
respectively, but with weak isomorphism replaced by strong isomorphism.
Thus, isolevel=3 specifies that DL will contain a list of duals
representing all strong isomorphism classes of semi-Latin squares with
the required properties (possibly with some classes represented more than
once) and isolevel=4 specifies that DL will contain precisely one
dual semi-Latin square representative for each strong isomorphism class
of semi-Latin squares with the required properties.
For example, we determine the numbers of weak and strong isomorphism classes of (4times4)/k semi-Latin squares for k=1,...,6. (These numbers disagree with P. E. Chigbu's classification for the cases k=3,4 BaCh.)
gap> List([1..6],k->Length(SemiLatinSquareDuals(4,k))); # weak [ 2, 10, 40, 164, 621, 2298 ] gap> List([1..6],k->Length(SemiLatinSquareDuals(4,k,"default","default",4))); # strong [ 2, 11, 46, 201, 829, 3343 ]
Next, we determine one SOMA(3,6).
gap> SemiLatinSquareDuals(6,3,"default",[0,1],0);
[ rec( isBlockDesign := true, v := 36,
blocks := [ [ 1, 8, 15, 22, 29, 36 ], [ 1, 9, 16, 23, 30, 32 ],
[ 1, 12, 14, 21, 28, 35 ], [ 2, 9, 17, 24, 25, 34 ],
[ 2, 11, 18, 22, 27, 31 ], [ 2, 12, 16, 19, 29, 33 ],
[ 3, 10, 14, 24, 29, 31 ], [ 3, 11, 16, 20, 25, 36 ],
[ 3, 12, 13, 23, 26, 34 ], [ 4, 7, 14, 23, 27, 36 ],
[ 4, 8, 17, 21, 30, 31 ], [ 4, 9, 18, 19, 26, 35 ],
[ 5, 7, 15, 20, 30, 34 ], [ 5, 8, 13, 24, 28, 33 ],
[ 5, 10, 18, 21, 25, 32 ], [ 6, 7, 17, 22, 26, 33 ],
[ 6, 10, 13, 20, 27, 35 ], [ 6, 11, 15, 19, 28, 32 ] ],
tSubsetStructure := rec( t := 1, lambdas := [ 3 ] ), isBinary := true,
isSimple := true, blockSizes := [ 6 ], blockNumbers := [ 18 ], r := 3,
autSubgroup := <permutation group of size 72 with 3 generators>,
pointNames := [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ],
[ 1, 6 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ],
[ 2, 6 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ], [ 3, 4 ], [ 3, 5 ],
[ 3, 6 ], [ 4, 1 ], [ 4, 2 ], [ 4, 3 ], [ 4, 4 ], [ 4, 5 ],
[ 4, 6 ], [ 5, 1 ], [ 5, 2 ], [ 5, 3 ], [ 5, 4 ], [ 5, 5 ],
[ 5, 6 ], [ 6, 1 ], [ 6, 2 ], [ 6, 3 ], [ 6, 4 ], [ 6, 5 ],
[ 6, 6 ] ] ) ]
[Up] [Previous] [Next] [Index]
design manual