Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
latin trade; bitrade; genus
latin trade; bitrade; genus
Summary:
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$.
References:
[1] Bate J.A., van Rees G.H.J.: Minimal and near-minimal critical sets in back circulant latin squares. Australasian J. Combin. 27 (2003), 47-61. MR 1955387 | Zbl 1024.05014
[2] Cooper J., Donovan D., Seberry J.: Latin squares and critical sets of minimal size. Australasian J. Combin. 4 (1991), 113-120. MR 1129273 | Zbl 0759.05017
[3] Drápal A.: Geometry of latin trades. manuscript circulated at the conference Loops `03, Prague, 2003.
[4] Drápal A., Kepka T.: Exchangeable partial groupoids I. Acta Univ. Carolin. Math. Phys. 24 (1983), 57-72. MR 0733686
[5] Fu H.-L.: On the construction of certain type of latin squares with prescribed intersections. Ph.D. Thesis, Auburn University, 1980.
[6] Grannell M.J., Griggs T.S., Knor M.: Biembeddings of latin squares and hamiltonian decompositions. Glasg. Math. J. 46 (2004), 443-457. MR 2094802 | Zbl 1062.05030
[7] Keedwell A.D.: Critical sets in latin squares and related matters: an update. Utilitas Math. 65 (2004), 97-131. MR 2048415 | Zbl 1053.05019
[8] Khosrovshahi G.B., Maysoori C.H.: On the bases for trades. Linear Algebra Appl. 226-228 (1995), 731-748. MR 1344595
[9] Street A.P.: Trades and defining sets. in: C.J. Colbourn and J.H. Dinitz, Eds., CRC Handbook of Combinatorial Designs (CRC Press, Boca Raton, FL., 1996), pp.474-478. Zbl 0847.05011
[10] Wanless I.M.: Cycle switches in latin squares. Graphs Combin. 20 (2004), 545-570. MR 2108400 | Zbl 1053.05020
Search
Partner of
