Generating Uniformly-Distributed Random Generalised 2-designs with Block Size 3

Abstract

Generalised t-designs, defined by Cameron, describe a generalisation of many combinatorial objects including: Latin squares, 1-factorisations of K2n (the complete graph on 2n vertices), and classical t-designs. This new relationship raises the question of how their respective theory would fare in a more general setting. In 1991, Jacobson and Matthews published an algorithm for generating uniformly distributed random Latin squares and Cameron conjectures that this work extends to other generalised 2-designs with block size 3. In this thesis, we divide Cameron’s conjecture into three parts. Firstly, for constants RC, RS and CS, we study a generalisation of Latin squares, which are (r c) grids whose cells each contain RC symbols from the set f1;2; : : : ; sg such that each symbol occurs RS times in each column and CS times in each row. We give fundamental theory about these objects, including an enumeration for small parameter values. Further, we prove that Cameron’s conjecture is true for these designs, for all admissible parameter values, which provides the first method for generating them uniformly at random. Secondly, we look at a generalisation of 1-factorisations of the complete graph. For constants NN and NC, these graphs have n vertices, each incident with NN coloured edges, such that each colour appears at each vertex NC times. We successfully show how to generate these designs uniformly at random when NC 0 (mod 2) and NN NC. Finally, we observe the difficulties that arise when trying to apply Jacobson and Matthews’ theory to the classical triple systems. Cameron’s conjecture remains open for these designs, however, there is mounting evidence which suggests an affirmative result. A function reference for DesignMC, the bespoke software that was used during this research, is provided in an appendix.