COBS and equitable partitions

It happens sometimes that researchers working in different fields study the same thing, give it different names, and don’t realise that there is further work on the subject somewhere else. Here is a story of such a situation, which arose indirectly from the work Rosemary and I were doing with statisticians in Covilhã, Portugal, namely Dário and Sandra Ferreira and Célia Nunes.

I begin with the statistics. We are designing an experiment to test a number of different “treatments” (fertilizers, drugs, or whatever). We have a number of experimental units available: these may be plots of land, fruit trees, human or animal subjects, etc. For brevity I will call them “plots”.

The design for the experiment is a function from the set of plots to the set of treatments, giving the treatment to be applied to each plot.

The simplest case is where the plots are all alike, apart from small random variations. In this case there is no restriction on how we choose the design function; for efficiency (meaning small variance of estimators of treatment differences) we should apply each treatment the same number of times, or if this is not possible, choose the numbers of occurrences to differ by at most one.

But in practice things may be more complicated. The plots may differ on a number of factors, each corresponding to a partition of the set of plots. For example, an agricultural experiment may use several plots on each of a number of farms in different parts of the world; plots on the same farm will be more similar than plots on different farms, and analysis of the experiment should take this into consideration. The plots are partitioned into “blocks”, one for each farm.

Indeed, there may be several such partitions. In an experiment on fruit trees, the trees in an orchard may be arranged in a rectangular array, and may have been used for an experiment last year; then the rows, columns, and earlier treatments all form significant partitions. In an experiment on animal feed, the animals may be divided into pens, a number of pens on each of several farms. In a clinical trial, the gender of the subject and the hospital at which they are treated may be relevant.

Thus we have to consider “plot structure”, usually (as above) defined by a collection of partitions of the set of plots. It is convenient of the partitions satisfy some conditions: each should have all parts of the same size; if possible, any two should be “orthogonal”, meaning that they intersect proportionally; and perhaps the set of partitions should be closed under meet and join and contain the two trivial partitions (the partition with a single part and the partition into singletons). Such a plot structure is called an orthogonal block structure, or OBS for short.

The plot structure is given; the experimenter has no control over it. All that she can control is the design function.

The result of the experiment will typically be a real number measured on each plot, that is, an element of the real vector space V of functions from the set of plots to the real numbers. In this vector space, each partition of the set of plots is represented by a subspace of V, consisting of functions which are constant on each part of the corresponding projection. There is a natural inner product on V (the characteristic functions of singletons forming an orthonormal basis), and so there is an orthogonal projection onto the space corresponding to any partition: this has the effect of averaging the function over each part of the partition.

Even if the plot structure is not completely described by partitions, it may still be the case that it gives rise to a collection of linear maps on V. For example, if the plots lie in a circle, there may be a neighbour effect, and we could consider the adjacency matrix of the cycle graph.

Statisticians introduced a helpful notion here, that of a commutative orthogonal block structure, or COBS for short. Noting that the design function allocating treatments to plots corresponds to another partition of the set of plots (where plots getting the same treatment lie in the same part), they argued that it is helpful if the orthogonal projection onto the treatment subspace commutes with the matrices arising from the plot structure. They call such a set-up a commutative orthogonal block structure, or COBS.

Now we leave statistics for a while and turn to graph theory.

Let Γ be a graph, and Δ a partition of its vertex set with parts P₁, … P_r. Then Δ is said to be equitable if there is a r×r matrix M such that, for any i,j, the number m_ij of vertices of P_j joined to a given vertex in P_i depends only on i and j, and not on the chosen vertex. Among the various consequences of this definition, I mention just one: The matrix M is the restriction of the adjacency matrix of the graph to the subspace consisting of functions constant on the parts of Δ; so this subspace is invariant under the adjacency matrix of the graph, and moreover, the minimal polynomial of the matrix M divides that of the adjacency matrix of the graph, so that its eigenvalues are among those of the adjacency matrix.

Equitable partitions occur widely in finite geometry and combinatorics; among geometrix examples, one could mention ovoids in projective spaces. Also, it is clear that the orbit partition of any group of automorphisms of the graph forms an equitable partition of its vertex set.

Once one suspects that there is a connection between COBS and equitable partitions, it soon becomes clear what theorem needs to be proved to connect them. It is the following, whose proof is straightforward once we have decided what is needed.

Theorem A partition Δ is equitable for a graph Γ if and only if the projection matrix onto the subspace of functions constant on parts of Δ commutes with the adjacency matrix of Γ.

A simple consequence of this theorem (not immediately obvious) is that, if the graph Γ is distance-regular, then an equitable partition of Γ is also equitable for the distance-i graph of Γ, for all i up to the diameter of the graph. For distance-regularity means that the distance-i graphs have adjacency matrices which are polynomials in the adjacency matrix of Γ so any matrix which commutes with the adjacency matrix of Γ commutes with the adjacency matrices of all distance-i graphs.

The work we were doing in Covilhã concerned COBS for the half-diallel, a genetic term referring to the situation where the genome of an individual comes from two parents but there is no distinction in their role. Designs for such experiments could also be applied to the situation where an experimental unit consists of a pair of individuals from a population. This might, for example, involve comparing the efficiency of various communication methods (face-to-face, telephone, video call, email, etc.). Thus a COBS for such an experiment is an equitable partition of the triangular graph, whose vertices are the 2-element subsets of the set of individuals, two vertices joined if the subsets have non-empty intersection.

My earlier foray into equitable partitions, with Rosemary Bailey, Sasha Gavrilyuk and Sergei Goryainov, involved Latin square graphs; this could be applied in the situation of an n×n array of fruit trees where last year an experiment in the form of a Latin square was done on the trees.

So how did we come to realise the connection? It happened like this. Rosemary was working on a classification of the COBS for the triangular association scheme. I noticed that what she was doing had a superficial resemblance to what she had done on equitable partitions of Latin square graphs on a plane returning from China a few years ago. As said above, once you suspect that a connection exists, it is fairly straightforward to see what it is and to prove the required theorem.