Designs of perfect matchings

Lukas Klawuhn (Paderborn University)

It is well-known that the complete graph \(K_{2n}\) on \(2n\) vertices can always be decomposed into perfect matchings, called a \(1\)-factorisation. In such a decomposition, every edge of \(K_{2n}\) appears in exactly \(1\) perfect matching. This was generalised by Jungnickel and Vanstone to hyperfactorisations. These are sets of perfect matchings such that every pair of disjoint edges of \(K_{2n}\) appears in a constant number of perfect matchings. Hyperfactorisations are examples of Cameron’s partition systems and were rediscovered by Stinson who called them hyperresolutions. We generalise all these ideas to \(\lambda\)-factorisations of \(K_{2n}\) and characterise them algebraically as Delsarte designs in an association scheme using the theory of Gelfand pairs. We use this characterisation to derive divisibility conditions and non-existence results. Furthermore, we explore a connection to finite geometry, giving rise to explicit constructions of \(\lambda\)-factorisations.

This is joint work with John Bamberg. It is based on ideas developed together with Kai-Uwe Schmidt.

 Overview  Program