Permutation separations and complete bipartite factorisations of \(K_{n,n}\)
The electronic journal of combinatorics, Tome 10 (2003)
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$.
@article{10_37236_1730,
author = {Nigel Martin and Richard Stong},
title = {Permutation separations and complete bipartite factorisations of {\(K_{n,n}\)}},
journal = {The electronic journal of combinatorics},
year = {2003},
volume = {10},
doi = {10.37236/1730},
zbl = {1023.05109},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1730/}
}
Nigel Martin; Richard Stong. Permutation separations and complete bipartite factorisations of \(K_{n,n}\). The electronic journal of combinatorics, Tome 10 (2003). doi: 10.37236/1730
Cité par Sources :