×

Permutation separations and complete bipartite factorisations of \(K_{n,n}\). (English) Zbl 1023.05109

Electron. J. Comb. 10, Research paper R37, 26 p. (2003); printed version J. Comb. 10, No. 4 (2003).
Summary: 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 \leq k\leq 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\leq j\leq 2k-1\) and \(1\leq i\leq n\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)