Sesqui-arrays

Rosemary Bailey, Tomas Nilson and I have just put a paper on the arXiv on this topic.

I discussed related things here last year, but here is a reminder. A triple array is an r×c array whose entries are from a set of v letters, satisfying the following five conditions:

  • (A0) No letter appears more than once in any row or column.
  • (A1) Each letter occurs a constant number k of times, where vk = rc.
  • (A2) The numbers of letters common to any two rows is a non-zero constant.
  • (A3) The numbers of letters common to any two columns is a non-zero constant.
  • (A4) The numbers of letters common to a row and a column is a non-zero constant.

I will refer to these conditions as binary, equireplicate, row-balanced, column-balanced, and having adjusted orthogonality. (For more precise usage see the paper.)

These arrays were first considered by Agrawal (I described this here.) He noted that if a triple array has r+c = v+1, then it gives rise to a symmetric BIBD, whose points are the rows and columns and whose blocks are the letters and an additional symbol *; a letter is incident with the rows not containing that letter and the columns containing it, whereas * is incident with all rows and no columns. He conjectured that the process could be reversed, so that from a symmetric BIBD one could construct a triple array, except for the Fano plane and its complement (where a simple sudoku-like argument shows that it is not possible). The conjecture is still open; no counterexamples have been found, and in general it seems easy to find the appropriate array.

In the paper, we define a sesqui-array as an array satisfying (A0)–(A2) and (A4) but not necessarily (A3).

From a statistical point of view, we are interested in things like “efficiency” and “optimality” of a desigh, which are answers to the question: how accurately can we estimate, say, differences between treatment effects using this design? Among block designs, it is known that balanced incomplete block designs (if they exist) are optimal for all the standard measures of optimality. Analogously, triple arrays are best if they exist. But if a triple array does not exist, a sesqui-array may be a good substitute, since the adjusted orthogonality is important, and apart from that, we want the row and column designs to be as good as possible; if the row design is balanced then the array with the better column design should win.

In the paper, there are two main constructions. The first is a 7×36 sesqui-array with 42 letters, whose column design is the Sylvester design which I mentioned here: since it is a good design, hopefully the sesqui-array is also efficient. (Just a week or so ago, I got the computer to print out the array from my elegant construction, and found that it was fatally flawed and couldn’t be fixed; so this would have to come out of the paper, which would play havoc with the balance. Fortunately, within a day I had fixed it!)

The other is a construction of sesqui-arrays from biplanes which contains a small surprise.

A biplane is a symmetric BIBD with parameters (V,K,2). In other words, there are V points and V blocks; each block has K points and each point lies in K blocks; two points lie in two blocks, and two blocks intersect in two points. We have V = 1+K(K−1)/2. (I will use capital letters, as we have used the more common lower-case v and k as array parameters.)

There are only finitely many known biplanes, though no finiteness theorem has been proved. The standard reference on them is Section 15.8 of Marshall Hall’s book Combinatorial Theory, second edition. (Actually the data in this section contains several errors; I will list the ones we found at the end.)

There is a convenient description of a biplane that Hall uses. Fix a block B of a biplane. Now any further block meets B in two points, and any two points of B lie in one further block; so we can represent the other blocks by the 2-element subsets of B. If q is a point outside B, then the blocks containing q meet B in two points, which can be thought of as the edges of a graph H(q) of valency 2 (that is, a union of cycles), called a Hussain chain. It is easy to see that the biplane can be reconstructed from the set of Hussain chains on a block.

Now consider the array whose rows and columns are labelled by the points in B and the points not in B respectively. In row p and column q, we put the 2-element subset of B consisting of the two neigbours of p in the Hussain chain H(q). Now observe:

  • There are no pairs repeated in a row, as is easily seen (two adjacent edges belong to a unique Hussain chain). There may be repeated pairs in a column; this will occur if there is a 4-cycle in a Hussain chain, since two opposite points on a 4-cycle have the same set of neighbours.
  • The array is equireplicate, row-balanced, and has adjusted orthogonality. Therefore, if no Hussain chain contains a 4-cycle, we get a sesqui-array.
  • If every Hussain chain consists of 3-cycles only, then the two neighbours of a vertex themselves form an edge, so the array is the one associated to the biplane by Agrawal, and is therefore a triple array. This occurs for Hall’s first 16-point biplane B1 (with any choice of block; the Hussain chains are all 10 possible pairs of triangles), and for Hall’s first 37-point biplane (the Hussain chains are the orbits of subgroups of order 3 in PGL(2,8)). This gives 6×10 and 9×28 triple arrays in a very simple form.

The surprise comes from looking at the other two 16-point biplanes (B2 and B3 in Hall). In both cases, even though some Hussain chains are hexagons, the sesqui-array turns out to be a triple array; and in both cases, the biplane associated to it by Agrawal’s construction is B1. There is a nice explanation for this, which you can find in the paper. But it does show that the relation between isomorphism of designs and isomorphism of arrays is rather subtle.

For the record, the misprints we found in Hall’s book are:

  • Block A10 in the biplane B1 with k = 6: the entry 16 should be 15.
  • In the biplane BL(9), the second occurrence of 31 in the permutation ψ should be 34, and the element 32 in the second base block should be 22.
  • In the biplane BH(9), in the block beginning 2, 8, the entry 38 should be 34; and in the block beginning 7,8, the entry 10 should be 16.
  • In the table of chain lengths on p.333, 5-5-3 should be 5-3-3.
  • There are two misprints in the generators of the automorphism group of B(13) on p.334: the generator x should have 69 inserted before 70 in the last cycle, and the generator z should have the cycle (15,24) rather than (15,25).
Advertisements

About Peter Cameron

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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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