Permutation Separations and Complete Bipartite Factorisations of $K_{n,n}$

  • Nigel Martin
  • Richard Stong

Abstract

Suppose $p < q$ are odd and relatively prime. In this paper we complete the proof that $K_{n,n}$ has a factorisation into factors $F$ whose components are copies of $K_{p,q}$ if and only if $n$ is a multiple of $pq(p+q)$. The final step is to solve the "c-value problem" of Martin. This is accomplished by proving the following fact and some variants: For any $0\le k\le n$, there exists a sequence $(\pi_1,\pi_2, \dots,\pi_{2k+1})$ of (not necessarily distinct) permutations of $\{1,2,\dots,n\}$ such that each value in $\{-k,1-k,\dots,k\}$ occurs exactly $n$ times as $\pi_j(i)-i$ for $1\le j\le 2k-1$ and $1\le i\le n$.

Published
2003-09-17
Article Number
R37