Latin trades in groups defined on planar triangulations
Nicholas J. Cavenagh
and Ian M. Wanless
DOI: 10.1007/s10801-008-0165-9
Abstract
For a finite triangulation of the plane with faces properly coloured white and black, let A W \mathcal{A}_{W} be the abelian group constructed by labelling the vertices with commuting indeterminates and adding relations which say that the labels around each white triangle add to the identity. We show that A W \mathcal{A}_{W} has free rank exactly two. Let A W * \mathcal{A}_{W}^{*} be the torsion subgroup of A W \mathcal{A}_{W} , and A B * \mathcal{A}_{B}^{*} the corresponding group for the black triangles. We show that A W * \mathcal{A}_{W}^{*} and A B * \mathcal{A}_{B}^{*} have the same order, and conjecture that they are isomorphic.
For each spherical latin trade W, we show there is a unique disjoint mate B such that ( W, B) is a connected and separated bitrade. The bitrade ( W, B) is associated with a two-colourable planar triangulation and we show that W can be embedded in A W * \mathcal{A}_{W}^{*} , thereby proving a conjecture due to Cavenagh and Drápal. The proof involves constructing a (0,1) presentation matrix whose permanent and determinant agree up to sign. The Smith normal form of this matrix determines A W * \mathcal{A}_{W}^{*} , so there is an efficient algorithm to construct the embedding. Contrasting with the spherical case, for each genus g\geq 1 we construct a latin trade which is not embeddable in any group and another that is embeddable in a cyclic group.
Pages: 323–347
Keywords: keywords Latin trade; bitrade; Latin square; abelian group; planar triangulation; Smith normal form; permanent
Full Text: PDF
References
1. Bate, J.A., van Rees, G.H.J.: Minimal and near-minimal critical sets in back circulant latin squares. Australas. J. Comb. 27, 47-61 (2003)
2. Cavenagh, N.J.: The theory and application of latin bitrades: a survey. Math. Slovaca 58, 1-28 (2008)
3. Cavenagh, N.J.: Embedding 3-homogeneous latin trades into abelian 2-groups. Comment. Math. Univ. Carol. 45, 194-212 (2004)
4. Cavenagh, N.J., Hämäläinen, C., Drápal, A.: Latin bitrades derived from groups. Discrete Math. 308, 6189-6202 (2008)
5. Cavenagh, N.J., Lison\check ek, P.: Planar Eulerian triangulations are equivalent to spherical latin bitrades. J. Comb. Theory Ser. A 115, 193-197 (2008)
6. Cooper, J., Donovan, D., Seberry, J.: Latin squares and critical sets of minimal size. Australas. J. Comb. 4, 113-120 (1991)
7. Dénes, J., Keedwell, A.D.: Latin Squares and Their Applications. Akadémiai Kiadó, Budapest (1974)
8. Drápal, A.: On a planar construction of quasigroups. Czechoslov. Math. J. 41, 538-548 (1991)
9. Drápal, A.: Hamming distances of groups and quasi-groups. Discrete Math. 235, 189-197 (2001)
10. Drápal, A., Kepka, T.: Exchangeable partial groupoids I. Acta Univ. Carol. Math. Phys. 24, 57-72 (1983)
11. Drápal, A., Kepka, T.: Group modifications of some partial groupoids. Ann. Discrete Math. 18, 319- 332 (1983)
12. Drápal, A., Kepka, T.: Group distances of Latin squares. Comment. Math. Univ. Carol. 26, 275-283 (1985)
13. Drápal, A., Kepka, T.: On a distance of groups and Latin squares. Comment. Math. Univ. Carol. 30, 621-626 (1989)
14. Drápal, A., Hämäläinen, C., Kala, V.: Latin bitrades and dissections of equilateral triangles. Preprint
15. Egan, J., Wanless, I.M.: Latin squares with no small odd plexes. J. Comb. Des. 16, 477-492 (2008)
16. Keedwell, A.D.: Critical sets in latin squares and related matters: an update. Util. Math. 65, 97-131 (2004)
17. McCuaig, W.: Pólya's permanent problem. Electron. J. Comb. 11, R79 (2004)
18. Sims, C.C.: Computation with Finitely Presented Groups. Encyclopedia Math. Appl., vol.
48. Cambridge University Press, Cambridge (1994)
19. Suschkewitsch, A.: On a generalization of the associative law. Trans. Am. Math. Soc. 31, 204-214 (1929)
20. Wanless, I.M.: A computer enumeration of small latin trades. Australas. J. Comb. 39, 247-258 (2007)
21. Wanless, I.M.: Permanents. In: Hogben, L. (ed.) Handbook of Linear Algebra. Chapman & Hall/CRC, Boca Raton (2007)
22. Wanless, I.M.: Personal webpage.
23. Wanless, I.M., Webb, B.S.: The existence of latin squares without orthogonal mates. Des. Codes Cryptogr. 40, 131-135 (2006)
24. Open problems from Workshop on latin trades Prague, 6-10 February 2006.
2. Cavenagh, N.J.: The theory and application of latin bitrades: a survey. Math. Slovaca 58, 1-28 (2008)
3. Cavenagh, N.J.: Embedding 3-homogeneous latin trades into abelian 2-groups. Comment. Math. Univ. Carol. 45, 194-212 (2004)
4. Cavenagh, N.J., Hämäläinen, C., Drápal, A.: Latin bitrades derived from groups. Discrete Math. 308, 6189-6202 (2008)
5. Cavenagh, N.J., Lison\check ek, P.: Planar Eulerian triangulations are equivalent to spherical latin bitrades. J. Comb. Theory Ser. A 115, 193-197 (2008)
6. Cooper, J., Donovan, D., Seberry, J.: Latin squares and critical sets of minimal size. Australas. J. Comb. 4, 113-120 (1991)
7. Dénes, J., Keedwell, A.D.: Latin Squares and Their Applications. Akadémiai Kiadó, Budapest (1974)
8. Drápal, A.: On a planar construction of quasigroups. Czechoslov. Math. J. 41, 538-548 (1991)
9. Drápal, A.: Hamming distances of groups and quasi-groups. Discrete Math. 235, 189-197 (2001)
10. Drápal, A., Kepka, T.: Exchangeable partial groupoids I. Acta Univ. Carol. Math. Phys. 24, 57-72 (1983)
11. Drápal, A., Kepka, T.: Group modifications of some partial groupoids. Ann. Discrete Math. 18, 319- 332 (1983)
12. Drápal, A., Kepka, T.: Group distances of Latin squares. Comment. Math. Univ. Carol. 26, 275-283 (1985)
13. Drápal, A., Kepka, T.: On a distance of groups and Latin squares. Comment. Math. Univ. Carol. 30, 621-626 (1989)
14. Drápal, A., Hämäläinen, C., Kala, V.: Latin bitrades and dissections of equilateral triangles. Preprint
15. Egan, J., Wanless, I.M.: Latin squares with no small odd plexes. J. Comb. Des. 16, 477-492 (2008)
16. Keedwell, A.D.: Critical sets in latin squares and related matters: an update. Util. Math. 65, 97-131 (2004)
17. McCuaig, W.: Pólya's permanent problem. Electron. J. Comb. 11, R79 (2004)
18. Sims, C.C.: Computation with Finitely Presented Groups. Encyclopedia Math. Appl., vol.
48. Cambridge University Press, Cambridge (1994)
19. Suschkewitsch, A.: On a generalization of the associative law. Trans. Am. Math. Soc. 31, 204-214 (1929)
20. Wanless, I.M.: A computer enumeration of small latin trades. Australas. J. Comb. 39, 247-258 (2007)
21. Wanless, I.M.: Permanents. In: Hogben, L. (ed.) Handbook of Linear Algebra. Chapman & Hall/CRC, Boca Raton (2007)
22. Wanless, I.M.: Personal webpage.
23. Wanless, I.M., Webb, B.S.: The existence of latin squares without orthogonal mates. Des. Codes Cryptogr. 40, 131-135 (2006)
24. Open problems from Workshop on latin trades Prague, 6-10 February 2006.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition