Block designs: duality etc.

[Peter Cameron]

Here is the promised document...

	Block designs: Representations, automorphisms, duality
	------------------------------------------------------

					pjc, 16/04/2003

This document discusses three models of a block design and sets various
issues in these three contexts.

Here are three representations of a block design. The elements of the block
design are treatments (or points), blocks, and plots (or flags).

First model. The treatments are are the members of a partition of the set of
plots. The blocks are the members of another partition of the set of plots.

Second model. The treatments and blocks are the two classes of vertices of a
bipartite graph with positive integer labels on the edges. The plots form a
multiset whose underlying set is the edge set of the graph, and where the
multiplicity of each edge is its label.

Third model. (This is the one used in DTRS.) The points form a set. Each
block is a multiset of points, and the blocks form a multiset. It is quite
tricky to say what the plots are in this model; but, if the design is binary
(that is, if each block is a set), then a plot is an ordered pair (point,
block), where the point is in the block.

Here are the translations among them.

 From Model 1 to Model 2: Given a design in Model 1, form a bipartite graph
where the label on the edge from a point to a block is the number of plots in
intersection of these two sets. (If the intersection is empty, we put no
edge.)

 From Model 2 to Model 1: Given a design in model 2, the plots form the set
whose elements are pairs (edge, number), where the number ranges from 0 to
one less than the edge label. Then a treatment corresponds to the set of
plots whose edge is incident with that treatment, and a block corresponds to
the set of plots whose edge is incident with that block.

A moment's thought shows that these constructions are mutually inverse.

 From Model 2 to Model 3: Given a design in Model 2, the point set is the set
of treatments; each block corresponds the multiset consisting of the
treatments adjacent to that block, with multiplicity equal to the label on
the corresponding edge. The same multiset may arise several times in the
construction; this is dealt with by taking it with the appropriate
multiplicity in the set of all blocks.

 From Model 3 to Model 2: Given a design in Model 3, take the set of
treatments, and the set of pairs (block, number), where the number ranges
from 0 to one less than the multiplicity of the block. Now join a treatment
to a (block, number) pair if the treatment is in the block, and label it with
the multiplicity of the treatment in the block.

A moment's thought shows that these constructions are also mutually inverse.

The third model is most convenient for storage, and is the one most commonly
used by mathematicians. But the first model is closest to the use in
experimental design (where the set of experimental units often comes
partitioned into blocks, and the experimenter introduces another partition by
applying treatments to the blocks.

I propose that questions about what to permit in a block design can best be
answered by going back to the first model. Let us look at a few.

1. "Can a block contain no points?" The equivalent question in  Model 1 is
"Can an element of the block partition intersect no parts of the treatment
partition?" The answer is clearly "no", since parts of a partition are
necessarily non-empty. The same principle would incidentally forbid a point
lying on no blocks.

2. Repeated points and blocks. The blocks form a multiset; in other words,
"repeated blocks" are permitted. But what are "repeated points"? Clearly
these would be points which lie in the same blocks and have the same
multiplicities there; but there is no mechanism for lumping them together,
since we have insisted that the points form a set. In Model 1, neither
repeated treatments nor repeated blocks give any difficulty; the reader is
invited to think about what they mean in this model.

3. Questions about duality. Clearly there is no problem about duality in
Model 1 (or Model 2). But in Model 3 we get into deep water. In order to find
the dual of a block design in Model 3, it is necessary to convert it to Model
2, then exchange "treatment" and "block" as labels for the parts of the
bipartite graph, and then convert the result to Model 3.

4. Automorphism groups. The three models lead to differing definitions of the
automorphism group: in Model 1, a permutation of the plots preserving the
treatment and block partitions; in Model 2, a permutation of the treatments
and blocks preserving the edges and labels in the bipartite graph; and in
Model 3, a permutation of the points which maps a block to a block with the
same multiplicity in the block multiset. There is a homomorphism from the
first to the second whose kernel is the direct product of symmetric groups on
the parts of the meet of the two partitions. There is a homomorphism from the
second to the third whose kernel is the kernel of the action of the group on
the bipartite block consisting of the treatments; this kernel is the direct
product of the symmetric groups on the equivalence classes of blocks, two
blocks equivalent if they are joined to the same treatments with the same
multiplicities. It can be argued (as we have done) that what we lose in the
kernels of these two homomorphisms is easy to recover, and the "smallest"
group (the automorphism group of Model 3) has all the essential information.

Time for an example.

Model 1:
	Plot set {1,2,3,4,5,6}
	Treatment partition {{1,2,4,5},{3,6}}
	Block partition {{1,2,3},{4,5,6}}
	Automorphism group of order 8, generated by the permutations
		     (1,2), (4,5), and (1,4)(2,5)(3,6).

Model 2: Calling the treatments X and Y, and the blocks A and B, in the order
written, the graph has edges XA (label 2), XB (label 2), YA (label 1), YB
(label 1). Automorphism group of order 2, generated by (A,B).

Model 3:
	Point set {X,Y}
	Block multiset [[X,X,Y],[X,X,Y]]
	Automorphism group trivial.

Note that the dual, in Model 3, has
	Point set {A,B}
	Block set [[A,A,B,B],[A,B]]
	Automorphism group of order 2 generated by (A,B).

Note that the kernel of the first homomorphism "measures" non-binarity of the
design, while the kernel of the second arises from "repeated blocks".

This suggests that there is an even more compact representation of a block
design, in which the automorphism group is the image of the group of Model 2
under a homomorphism whose kernel is the product of the "repeated points" and
"repeated blocks" kernels. (These kernels commute and so generate their
direct product.) To describe such a model in the language of Model 3 would
involve allowing the points to form a multiset where each point is taken with
full multiplicity or not at all in a block. A Model 2-type description is
easier. As well as numbers on the edges, we also have numbers on the vertices
indicating the numbers of times the corresponding objects are repeated. An
automorphism is now simply a graph automorphism preserving the bipartite
blocks and the vertex and edge labels.

The representation of our earlier example in this form would have points X
and Y each with label 1 and block A with label 2, and edges AX with label 2
and AY with label 1.

Final note on intersection of blocks. Clearly in Model 1, the "intersection"
of two different blocks is always the empty set. In Model 3, if the design
is simple, the intersection is the number of points (treatments) occurring
in both blocks. Carrying this back to Model 1, the concurrence of two blocks
is the number of ordered pairs of plots such that the first plot is in the
first block and the second plot in the second block and the two plots are
in the same treatment. Now taking this forward again to Model 3, we see that
the general definition of concurrence of two blocks in this model should be
calculated as follows: for each point, multiply its multiplicities in the two
blocks, and sum these products. This extends in the obvious way to the
concurrence of more than two blocks.