Mathematics Department

Dr David Bedford

Biography

Throughout my time as a lecturer I have been involved in the national programme of Masterclasses in Mathematics run under the auspices of the Royal Institution. In recent years I have been a co-organiser of the first ever series to be held in Staffordshire. The aim of this series is to stimulate and encourage mathematically able young people (13/14 year olds) in the art and practice of mathematics.

Research Interests

My current research interests include:

1. Generalisations of orthogonality in latin squares. Two latin squares of order n are orthogonal if, when superimposed so as to form an array of ordered pairs, each of the n^2 ordered pairs occurs (exactly) once. Sets of pairwise orthogonal latin squares are important in the construction of experimental designs and are closely related to finite projective planes. In [5] I generalised the notion of orthogonality by stating that two latin squares of order n defined over the same set of symbols are quasi-orthogonal if, when superimposed to form an array of unordered pairs, each of the n(n-1)/2 pairs of distinct elements occurs exactly twice (and hence each pair of repeated elements occurs exactly once). At first sight this appears to be a trivial generalisation but in fact quasi-orthogonal latin squares are related to a number of well known designs such as Room squares, Steiner triple systems, equidistant permutation arrays and quasi-complete latin squares. The major outstanding question in this area is: what is the maximum size of a set of mutually quasi-orthogonal latin squares (MQOLS) of order n? The answer for mutually orthogonal latin squares is n-1 and such sets exist for all prime power orders. The current state regarding MQOLS is that whilst no set larger than n-1 has been found the best upper bound is of order n^2 (see [12]).
2. Enumeration of transversals and near-transversals in the Cayley tables of groups. A partial transversal in a latin square of order n is a set of cells, no two from the same row or column, such that no two cells contain the same symbol. A transversal is a partial transversal of length n. Transversals are closely related to orthogonality in that if two latin squares are orthogonal, then the set of cells containing a fixed symbol in the first square defines a transversal in the second. In fact a latin square has an orthogonal mate if and only if it can be partitioned into n disjoint transversals. Since 1964 it has been known that the Cayley tables of each of the 4 non-cyclic groups of order 8 have 384 transversals but no explanation of this fact was known. In [1] I began an investigation into this fact when I explained why the two non-cyclic abelian groups had the same number transversals and similarly for the two non-abelian groups. In [6] this work was completed when my then PhD student, Roger Whitaker, was able to prove a much stronger result, namely that the number of transversals in each of the non-cyclic groups of order 8 is exactly 48 times the number for the non-cyclic group of order 4; since the latter is easily seen to be 8 the result follows. The following conjecture was made by Richard Brualdi: every latin square of order n has a partial transversal of size (at least) n-1. This conjecture is known to be true for the Cayley tables of abelian groups but it is not even known for all non-abelian groups. The best general lower bound on the size for an arbitrary latin square of order n is of order n-sqrt(n).
3. Uniquely completable sets in latin squares. A partial latin square of order n is an n by n array of cells that are either empty or contain a symbol from a set of size n such that no symbol occurs more than once in any row or column. Not all partial latin squares may be completed to form a latin square, for example:

   1	2	3	-
   -	-	-	4
   -	-	-	-
   -	-	-	-

   A partial latin square (PLS) of order n is uniquely completable if it is contained in exactly one latin square of order n. A uniquely completable PLS is critical if no proper subset of its entries is uniquely completable. It is usual to distinguish between PLS's that are strong uniquely completable and those that are weak. Details are contained in [8] but loosely a PLS is weak uniquely completable if its completion requires some form of backtracking. It had been conjectured that the Cayley table of a cyclic group contains no weak uniquely completable PLS but in [8] Matthew Johnson and myself proved that a finite group has a weak uniquely completable PLS if and only if it has order greater than 5. There are many further interesting questions in this area, one of which concerns the nature of critical PLS's of smallest size. I do not know of a latin square that has a weak uniquely completable PLS smaller than any of its strong uniquely completable PLS's; I would expect there to be many such squares!
4. Construction of tournaments that are balanced with respect to carry-over effects. The problem of constructing a tournament between two teams of n players where each player plays every member of the opposing team once in rounds is equivalent to the construction of a latin square of order n. If a tournament is desired with certain properties such as balance then these properties easily translate into properties of the corresponding latin square. In [11] Matthew Ollis (then an undergraduate student at QMW), Roger Whitaker and myself combined to find the first example of such a tournament for odd n. In fact we found an example of order 21, this is because we were looking at Cayley tables for non-abelian groups and the smallest of odd order has 21 elements. Using our technique the next order to consider is 27 but it would appear most likely that smaller examples exist that are not based on groups. Of course what would be really nice would be a general construction for all odd n greater than some given integer.

Publications