| Title:
|
Minimal and minimum size latin bitrades of each genus (English) |
| Author:
|
Lefevre, James |
| Author:
|
Donovan, Diane |
| Author:
|
Cavenagh, Nicholas |
| Author:
|
Drápal, Aleš |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
48 |
| Issue:
|
2 |
| Year:
|
2007 |
| Pages:
|
189-203 |
| . |
| Category:
|
math |
| . |
| 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$. (English) |
| Keyword:
|
latin trade |
| Keyword:
|
bitrade |
| Keyword:
|
genus |
| MSC:
|
05B15 |
| idZBL:
|
Zbl 1199.05021 |
| idMR:
|
MR2338087 |
| . |
| Date available:
|
2009-05-05T17:02:11Z |
| Last updated:
|
2012-05-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119649 |
| . |
| Reference:
|
[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. Zbl 1024.05014, MR 1955387 |
| Reference:
|
[2] Cooper J., Donovan D., Seberry J.: Latin squares and critical sets of minimal size.Australasian J. Combin. 4 (1991), 113-120. Zbl 0759.05017, MR 1129273 |
| Reference:
|
[3] Drápal A.: Geometry of latin trades.manuscript circulated at the conference Loops `03, Prague, 2003. |
| Reference:
|
[4] Drápal A., Kepka T.: Exchangeable partial groupoids I.Acta Univ. Carolin. Math. Phys. 24 (1983), 57-72. MR 0733686 |
| Reference:
|
[5] Fu H.-L.: On the construction of certain type of latin squares with prescribed intersections.Ph.D. Thesis, Auburn University, 1980. |
| Reference:
|
[6] Grannell M.J., Griggs T.S., Knor M.: Biembeddings of latin squares and hamiltonian decompositions.Glasg. Math. J. 46 (2004), 443-457. Zbl 1062.05030, MR 2094802 |
| Reference:
|
[7] Keedwell A.D.: Critical sets in latin squares and related matters: an update.Utilitas Math. 65 (2004), 97-131. Zbl 1053.05019, MR 2048415 |
| Reference:
|
[8] Khosrovshahi G.B., Maysoori C.H.: On the bases for trades.Linear Algebra Appl. 226-228 (1995), 731-748. MR 1344595 |
| Reference:
|
[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 |
| Reference:
|
[10] Wanless I.M.: Cycle switches in latin squares.Graphs Combin. 20 (2004), 545-570. Zbl 1053.05020, MR 2108400 |
| . |
