Circular repeated-measurements designs

My first paper in a real statistical journal has just been almost accepted (just a bit of re-formatting …)

The paper is entitled “On optimality and construction of circular repeated-measurements designs”, the other authors are R. A. Bailey, K. Filipiak, J. Kunert and A. Markiewicz. You can find a preliminary version here on the arXiv.

I won’t talk about the statistics here (which wasn’t my part anyway), but there are some interesting mathematical aspects.

In matrix terms, we have a t×t matrix S which has the properties

  • S has all diagonal entries 0 and off-diagonal entries λ−1 and λ, for some λ;
  • S has constant row and column sums n;
  • SST is completely symmetric (that is, its diagonal entries are constant and its off-diagonal elements are constant), where T denotes transpose.

More is required; I will discuss the extra requirements below.

It is convenient to put A = ST−(λ−1)(JI), where J is the all-1 matrix. Then A is a zero-one matrix with zero diagonal and constant row and column sums such that ATA−(λ−1)(A+AT) is completely symmetric. Furthermore, we then divide cases as follows:

  • Type I if A+AT is completely symmetric;
  • Type II if A+AT is not completely symmetric and λ = 1;
  • Type III if A+AT is not completely symmetric and λ > 1.

In cases I and II, ATA is completely symmetric, so A is the incidence matrix of a symmetric BIBD (or 2-design). Moreover, in Type I, A+AT = JI, so A is the adjacency matrix of a doubly regular tournament (a regular tournament in which the number of points dominating a pair of points is constant). The extra that is required is a decomposition of the arcs of the tournament into Hamiltonian cycles. It is conjectured that any doubly regular tournament has such a Hamiltonian decomposition. Quite a few examples are known.

Type II allows symmetric BIBDs with other (non-Hadamard) parameters. If the BIBD arises from a difference set modulo t, all of whose elements are coprime to t, the Hamiltonian decomposition is easily found: for each element d of the difference set, take the cycle which takes steps of size d.

Type III is the most interesting and mysterious. We give several constructions. One of these takes a doubly regular tournament and simply “blows up” each vertex into a fixed number m of vertices. Another uses a “double cover” of the complete directed graph, similar to double covers of complete graphs which correspond to regular two-graphs. The only reference we could find in the literature was to a paper I wrote with Laci Babai, which I discussed here. We proved that a finite group is the automorphism group of a switching class of tournaments if and only if its Sylow 2-subgroups are cyclic or dihedral. The digraphs, to which we gave the slightly silly name “S-digraphs”, have the property that the vertices are paired, with no arc between paired vertices; the induced subgraph on any two pairs of vertices is a 4-cycle. From doubly regular tournaments we construct S-digraphs which give Type III designs in some cases.

The existence question is not completely solved; for example, the question about Hamiltonian decompositions of doubly regular tournaments is still open as far as I know. Something worth working on here, maybe?


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s