Introduction

The complete bipartite graph K_n,n has 2n vertices, split into two clusters of size n. Every vertex in the first cluster is adjacent to every vertex in the second cluster. A one-factor (or perfect matching) is a set of n edges which meets each vertex exactly once. A one-factorisation is a decomposition of the edge set of K_n,n into n one-factors.

If we label the vertices in the first cluster with labels "row 1", "row 2", etc. and label the vertices in the second cluster with labels "col 1", "col 2", etc, and label the edges of the i-th one-factor with symbol i (1<=i<=n), then a one-factorisation is seen to be the same thing as a latin square: the cell in row i, column j is filled with the symbol attached to that corresponding edge.

If we label the vertices in each cluster with the numbers 1,2,...,n, then each one-factor is a permutation on this set. So a one-factorisation is the same as a set of n permutations in the symmetric group S_n with the property that, for any pair a,b of distinct permutations in the set,
a b ^-1 has no fixed points.

In a one-factorisation, the union of any two one-factors forms a 2-regular graph on 2n vertices (in fact, each component is a cycle of even length). A perfect one-factorisation is one in which the union of any two distinct one-factors is a single cycle of length 2n. A more general class of one-factorisations is the class of uniform one-factorisations. A one-factorisation is uniform of shape [k₁,k₂,..., k_s] provided the union of any two distinct one-factors is a graph with components of lengths 2k₁, 2k₂, ..., 2k_s.

Viewed as a set of permutations in the symmetric group, we seek n elements of S_n, say p₁, p₂,...,p_n, having the property that, for each i and j, (p_i)(p_j)^-1 belongs to a specified conjuagcy class. There is an association scheme naturally attached to the symmetric group; these one-factorisations correspond to maximal cliques in certain graphs of this association scheme.