Latin Squares

Dr Ian Wanless and Judith Egan, School of Mathematical Sciences

A 'Latin square' of order n is an n by n array containing n different symbols. Each symbol must occur exactly once in each row and column.  A completed sudoku puzzle is a familiar example of a Latin square of order 9, using the symbols 1,2,3,...,9.  Despite being best known in this recreational context, Latin squares play an important role in pure mathematics (in particular in the areas of combinatorial design theory, algebra and finite geometry) and have many applications in the design of sporting tournaments, statistical experiments, and in producing error correcting codes, to name just a few.

This project aims to develop the theory on important substructures of latin squares such as transversals, subsquares and latin trades.  Even for fairly small values of n and with a powerful computer there are too many Latin squares to generate them all. However, by making use of extensive computations it is still possible to generate enough examples that patterns emerge. In a number of cases an interesting general theorem has been found by first enumerating as many examples as we can with current technology, then thinking deeply about what we've found. Typically the enumerations use several CPU years, even after the algorithm was been fine-tuned and carefully coded.  Due to the size of the search space, a naive algorithm could easily run for thousands of years, and human investigation is out of the question.

The research team uses distributed computing, including the Monash Sun Grid, Monash Green SPONGE and Brecca HPC facilities, as an investigative tool to find patterns which can then by turned into mathematical theorems by humans.