Block designs: Representations, automorphisms, duality

A printable PDF version of this document is available.

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

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.

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

Model 3

• Point set {X,Y}
• Block multiset [[X,X,Y],[X,X,Y]]
• Automorphism group trivial.

Model 3, dual

• Point set {A,B}
• Block set [[A,A,B,B],[A,B]]
• Automorphism group of order 2 generated by (A,B).

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.

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