Latin squares and perfect factorisations of graphs

Ian Wanless

A 1-factor (also known as a perfect matching) of a graph is a selection of edges such that no two edges share a vertex but every vertex is on one of the edges. A perfect 1-factorisation of a graph is a decomposition of the graph into 1-factors in such a way that the union of any two 1-factors is a single (Hamiltonian) cycle.

Perfect 1-factorisations of complete graphs have been studied in some depth, but the problem for complete bipartite graphs does not seem to have been touched until recently. I will talk about what is known and demonstrate an interesting connection with Latin squares which have a particularly nice structure. These Latin squares are indivisible in a fairly strong sense -- not only do they have no non-trivial Latin subsquares, they don't even have subrectangles.