Latin squares and perfect factorisations of graphs
Ian Wanless
Oxford
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.