Arrays

This post is about things called triple arrays, and some variants. I was visited by Tomas Nilson last semester, and we have just posted a paper on the arXiv. This is a subject with a quite extraordinary history; Rosemary will tell the story in her talk next July at the British Combinatorial Conference in Strathclyde, so I won’t steal her thunder here, just tell about the objects themselves as if they had no history.

Suppose we have an m×n array in which each cell contains a letter from a set of size b. Here are some conditions that the array may satisfy, with names often used in the statistics literature.

1. Each letter occurs a constant number k of times, where bk = mn. (The array is equireplicate.)
2. No letter occurs more than once in a row or a column. (The array is binary.)
3. The number of letters common to two rows is constant. (The design of rows and letters is balanced.)
4. The number of letters common to two columns is constant. (The design of columns and letters is balanced.)
5. The number of letters common to a row and a column is constant. (The design has adjusted orthogonality.)

In the literature, an array satisfying all five conditions is called a triple array, while one satisfying conditions (1)–(4) is called a double array. We propose the term sesqui-array for an array satisfying (1)–(3) and (5): the prefix “sesqui” means “one-and-a-half”, and of the last three conditions, we require adjusted orthogonality and half of the two balance conditions required for a triple array. (Of course, many other terms are used in the literature for various combinations of these conditions!)

Agrawal’s conjecture

It has been proved several times that a triple array with m rows, n columns, and b symbols, satisfies b ≥ m+n−1. It is called extremal if equality holds here.

Extremal triple arrays are closely connected with square 2-designs, or symmetric BIBDs (in a different language). One of these consists of V points and V blocks, any block containing K points and any point lying in K blocks, such that any two blocks intersect in Λ points and any two points are contained in Λ blocks. (I use capitals to distinguish from the lower-case symbols for the array parameters.)

From any extremal triple array, we can construct a square 2-design as follows:

• the points of the design are symbols indexing the m rows and n columns of the array;
• the blocks are the b symbols of the array together with one new symbol ∞;
• the block ∞ is incident with all the row symbols and none of the column symbols;
• the block corresponding to a symbol x contains the row symbols for the rows not containing x and the column symbols for the columns containing x.

The properties of the design are easily checked.

Does the construction reverse? That is, can we construct a triple array from a square 2-design with a distinguished block? Agrawal knew that this was not possible for the smallest square designs (the Fano plane and its complement), and conjectured that it is possible in any other case. Various people have given algorithms which claim to produce the array from the design, but nobody has succeeded in proving that the algorithms always work, or indeed that the construction is always possible.

This is a kind of Sudoku puzzle. Given the design, consider the m×n array, with m = K and n = V−K, whose rows are indexed by the points of a block B and columns by the points not in B. In the cell in row i and column j, we have to put a symbol for a block which is not incident with point i but is incident with point j. So put the set consisting of all such symbols in this cell. Now our job is to choose an array of distinct representatives for this array of sets; that is, choose one element from the set in each cell such that the chosen elements in any row are all distinct, and the chosen elements in any column are also distinct.

Motivated by this precise problem, Dima Fon-Der-Flaass proved that the general existence problem for an array of distinct representatives for an array of sets is NP-complete. Of course this says nothing about the design problem, since these instances may be easier than the general case!

Here, for example, is the array of sets arising from the Fano plane. You are invited to tackle the easy exercise of showing that it has no ADR.

Difference sets

Suppose that the square design arises from a difference set D of cardinality K in a group G of order V. (This is the case that Tomas and I consider.) This means that every non-identity element of G can be expressed in exactly Λ ways in the form xy⁻¹ with x and y distinct elements of D. The blocks of the design are the right translates of D.

Now we can produce an array of non-identity group elements by taking D to index the rows and G\D the columns, with x,y entry xy⁻¹. Is this a triple array?

We show in the paper that it is always a double array; if the group G is abelian, it is a triple array if and only if −1 is a multiplier of D, that is, the set of inverses of elements of D is a translate of D. This gives new examples of triple arrays.

We also searched for triple arrays from non-abelian groups. Using a computer, we showed that there are none arising from our construction in non-abelian groups of orders 16 or 36.

Biplanes

A biplane is a square 2-design with Λ = 2.

In an attempt to test Agrawal’s conjecture for biplanes, we gave a construction which always produces a sesqui-array, and gave sufficient conditions for it to give a triple array.

This uses the notion of Hussain chains, a convenient representation of a biplane. Let B be a block of a biplane. Any other block meets B in two points, and any pair of points lie in just one further block; so we can represent the other blocks by pairs of points of B. How do we represent the remaining points? If q is a point outside B, then let H(q) be the graph with vertices the points of B, and edges the pairs representing the blocks containing q. It is easy to see that H(q) is a union of cyles. Moreover,

• two intersecting pairs of vertices are edges in a unique Hussain chain;
• two disjoint pairs of vertices are edges in exactly two Hussain chains;
• two distinct Hussain chains share exactly two edges.

Now we build an array as follows:

• the rows are indexed by the points of B, and the columns by the points outside B;
• the symbols are indexed by the 2-element subsets of B;
• in row p and column q, we put {x,y} if x and y are the neighbours of p in H(q).

As stated above, this is always a sesqui-array. It is a triple array if every Hussain chain (for the given choice of block) is a union of 3-cycles.

The biplanes possessing a block with this property are:

• the “nicest” biplane on 16 points (any block will do, and the Hussain chains are all the graphs consisting of two 3-cycles);
• one particular biplane on 37 points (the Hussain chains are the cycles of elements of order 3 in PSL(2,8)).