A generalization of transversals for Latin squares
The electronic journal of combinatorics, Tome 9 (2002)
We define a $k$-plex to be a partial latin square of order $n$ containing $kn$ entries such that exactly $k$ entries lie in each row and column and each of $n$ symbols occurs exactly $k$ times. A transversal of a latin square corresponds to the case $k=1$. For $k>n/4$ we prove that not all $k$-plexes are completable to latin squares. Certain latin squares, including the Cayley tables of many groups, are shown to contain no $(2c+1)$-plex for any integer $c$. However, Cayley tables of soluble groups have a $2c$-plex for each possible $c$. We conjecture that this is true for all latin squares and confirm this for orders $n\leq8$. Finally, we demonstrate the existence of indivisible $k$-plexes, meaning that they contain no $c$-plex for $1\leq c < k$.
@article{10_37236_1629,
author = {Ian M. Wanless},
title = {A generalization of transversals for {Latin} squares},
journal = {The electronic journal of combinatorics},
year = {2002},
volume = {9},
doi = {10.37236/1629},
zbl = {0993.05033},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1629/}
}
Ian M. Wanless. A generalization of transversals for Latin squares. The electronic journal of combinatorics, Tome 9 (2002). doi: 10.37236/1629
Cité par Sources :