Minimal and minimum size latin bitrades of each genus

Lefevre, James ; Donovan, Diane ; Cavenagh, Nicholas ; Drápal, Aleš

Commentationes Mathematicae Universitatis Carolinae, Tome 48 (2007) no. 2, pp. 189-203

Résumé

Suppose that $T^{\circ}$ and $T^{\star}$ are partial latin squares of order $n$, with the property that each row and each column of $T^{\circ}$ contains the same set of entries as the corresponding row or column of $T^{\star}$. In addition, suppose that each cell in $T^{\circ}$ contains an entry if and only if the corresponding cell in $T^{\star}$ contains an entry, and these entries (if they exist) are different. Then the pair $T=(T^{\circ},T^{\star})$ forms a {\it latin bitrade\/}. The {\it size\/} of $T$ is the total number of filled cells in $T^{\circ}$ (equivalently $T^{\star}$). The latin bitrade is {\it minimal\/} if there is no latin bitrade $(U^{\circ},U^{\otimes})$ such that $U^{\circ}\subseteq T^{\circ}$. Drápal (2003) represented latin bitrades in terms of row, column and entry cycles, which he proved formed a coherent digraph. This digraph can be considered as a combinatorial surface, thus associating each latin bitrade with an integer genus, which is a robust structural property of the latin bitrade. For each genus $g\ge 0$, we construct a latin bitrade of smallest possible size, and also a minimal latin bitrade of size $8g+8$.

Détail

Classification : 05B15
Keywords: latin trade; bitrade; genus