Constructing and embedding mutually orthogonal Latin squares: reviewing both new and existing results

Diane M. Donovan; Mike Grannell; Emine Ş. Yazıcı

Commentationes Mathematicae Universitatis Carolinae (2020)

  • Volume: 61, Issue: 4, page 437-457
  • ISSN: 0010-2628

Abstract

top
We review results for the embedding of orthogonal partial Latin squares in orthogonal Latin squares, comparing and contrasting these with results for embedding partial Latin squares in Latin squares. We also present a new construction that uses the existence of a set of t mutually orthogonal Latin squares of order n to construct a set of 2 t mutually orthogonal Latin squares of order n t .

How to cite

top

Donovan, Diane M., Grannell, Mike, and Yazıcı, Emine Ş.. "Constructing and embedding mutually orthogonal Latin squares: reviewing both new and existing results." Commentationes Mathematicae Universitatis Carolinae 61.4 (2020): 437-457. <http://eudml.org/doc/296974>.

@article{Donovan2020,
abstract = {We review results for the embedding of orthogonal partial Latin squares in orthogonal Latin squares, comparing and contrasting these with results for embedding partial Latin squares in Latin squares. We also present a new construction that uses the existence of a set of $t$ mutually orthogonal Latin squares of order $n$ to construct a set of $2t$ mutually orthogonal Latin squares of order $n^t$.},
author = {Donovan, Diane M., Grannell, Mike, Yazıcı, Emine Ş.},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {embedding; mutually orthogonal Latin square},
language = {eng},
number = {4},
pages = {437-457},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Constructing and embedding mutually orthogonal Latin squares: reviewing both new and existing results},
url = {http://eudml.org/doc/296974},
volume = {61},
year = {2020},
}

TY - JOUR
AU - Donovan, Diane M.
AU - Grannell, Mike
AU - Yazıcı, Emine Ş.
TI - Constructing and embedding mutually orthogonal Latin squares: reviewing both new and existing results
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2020
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 61
IS - 4
SP - 437
EP - 457
AB - We review results for the embedding of orthogonal partial Latin squares in orthogonal Latin squares, comparing and contrasting these with results for embedding partial Latin squares in Latin squares. We also present a new construction that uses the existence of a set of $t$ mutually orthogonal Latin squares of order $n$ to construct a set of $2t$ mutually orthogonal Latin squares of order $n^t$.
LA - eng
KW - embedding; mutually orthogonal Latin square
UR - http://eudml.org/doc/296974
ER -

References

top
  1. Abel R. J. R., Li Y., 10.1016/j.disc.2014.11.018, Discrete Math. 338 (2015), no. 4, 593–607. MR3300747DOI10.1016/j.disc.2014.11.018
  2. Andersen L. D., Hilton A. J. W., Thanks Evans!, Proc. London Math. Soc. (3) 47 (1983), no. 3, 507–522. MR0716801
  3. Andersen L. D., Hilton A. J. W., Rodger C. A., 10.1112/jlms/s2-26.1.21, J. London Math. Soc. (2) 26 (1982), no. 1, 21–27. MR0667240DOI10.1112/jlms/s2-26.1.21
  4. Barber B., Kühn D., Lo A., Osthus D., Taylor A., 10.1016/j.jcta.2017.04.005, J. Combin. Theory Ser. A. 151 (2017), 146–201. MR3663493DOI10.1016/j.jcta.2017.04.005
  5. Belyavskaya G. B., Lumpov A. D., Cross product of two systems of quasigroups and its use in constructing partially orthogonal quasigroups, Mat. Issled., Issled. Teor. Binarnykh i -arnykh Kvazigrupp 83 (1985), 26–38 (Russian). MR0807271
  6. Bryant D., Buchanan M., 10.1016/j.jcta.2006.10.009, J. Combin. Theory Ser. A 114 (2007), no. 6, 1046–1088. MR2337238DOI10.1016/j.jcta.2006.10.009
  7. Bryant D., Horsley D., 10.1002/jcd.20189, J. Comb. Des. 17 (2009), no. 1, 63–89. MR2475426DOI10.1002/jcd.20189
  8. Colbourn C. J., 10.1016/0166-218X(84)90075-1, Discrete Appl. Math. 8 (1984), 25–30. MR0739595DOI10.1016/0166-218X(84)90075-1
  9. Colbourn C. J., Dinitz J. H., Handbook of Combinatorial Designs, Chapman and Hall/CRC, 2007. MR2246267
  10. Colbourn C. J., Zhu L., The spectrum of R -orthogonal Latin squares, Combinatorics Advances, Tehran, 1994, Math. Appl., 329, Kluwer Acad. Publ., Dordrecht, 1995, pages 49–75. MR1366841
  11. Cruse A. B., 10.1016/0097-3165(74)90068-5, J. Combinatorial Theory Ser. A. 16 (1974), 18–22. MR0329925DOI10.1016/0097-3165(74)90068-5
  12. Damerell R. M., On Smetaniuk's construction for Latin squares and the Andersen–Hilton theorem, Proc. London Math. Soc. (3) 47 (1983), no. 3, 523–526. MR0716802
  13. Dietrich H., Wanless I. M., 10.1016/j.jsc.2017.04.002, J. Symbolic Comput. 86 (2018), 142–152. MR3725217DOI10.1016/j.jsc.2017.04.002
  14. Donovan D., Grannell M., Yazıcı E. Ş., 10.1016/j.disc.2020.111835, Discrete Math. 343 (2020), no. 6, 111835, 6 pages. MR4062293DOI10.1016/j.disc.2020.111835
  15. Donovan D. M., Yazıcı E. Ş., 10.1016/j.jcta.2014.04.003, J. Combin. Theory Ser. A 126 (2014), 24–34. MR3213305DOI10.1016/j.jcta.2014.04.003
  16. Drake D. A., Lenz H., 10.1007/BF01225000, Arch. Math. (Basel) 34 (1980), no. 6, 565–576. MR0596867DOI10.1007/BF01225000
  17. Evans A. B., Orthomorphism Graphs of Groups, Lecture Notes in Mathematics, 1535, Springer, Berlin, 1992. MR1222645
  18. Evans T., 10.1080/00029890.1960.11992032, Amer. Math. Monthly 67 (1960), 958–961. MR0122728DOI10.1080/00029890.1960.11992032
  19. Falcón R. M., Falcón Ó. J., Núñez J., Computing the sets of totally symmetric and totally conjugate orthogonal partial Latin squares by means of a SAT solver, Proc. of 17th Int. Conf. Computational and Mathematical Methods in Science and Engineering, CMMSE 2017, pages 841–852. 
  20. Ganter B., 10.1007/BF01222584, Arch. Math. (Basel) 22 (1971), 328–332 (German). MR0294145DOI10.1007/BF01222584
  21. Ganter B., Partial pairwise balanced designs, Colloq. Int. Sulle Teorie Combinatorie, Rome, 1973, Tomo II, Accad. Naz. Lincei, 1976, pages 377–380. MR0472553
  22. Gustavsson T., Decompositions of Large Graphs and Digraphs with High Minimum Degree, Ph.D. Thesis, Stockholm University, Stockholm, 1991. 
  23. Hall M., 10.1090/S0002-9904-1945-08361-X, Bull. Amer. Math. Soc. 51 (1945), 387–388. MR0013111DOI10.1090/S0002-9904-1945-08361-X
  24. Hall P., On representative subsets, Classic Papers in Combinatorics, Birkhäuser, Boston, 1987, pages 58–62. 
  25. Heinrich K., Zhu L., 10.1016/0012-365X(86)90070-1, Discrete Math. 59 (1986), no. 1–2, 69–78. MR0837956DOI10.1016/0012-365X(86)90070-1
  26. Hilton A. J. W., Rodger C. A., Wojciechowski J., Prospects for good embeddings of pairs of partial orthogonal Latin squares and of partial Kirkman triple systems, J. Combin. Math. Combin. Comput. 11 (1992), 83–91. MR1160067
  27. Hirsch R., Jackson M., 10.2178/jsl.7704090, J. Symbolic Logic 77 (2012), no. 4, 1211–1244. MR3051622DOI10.2178/jsl.7704090
  28. Horton J. D., 10.1016/0097-3165(74)90069-7, J. Combinatorial Theory Ser. A 16 (1974), 23–33. MR0347641DOI10.1016/0097-3165(74)90069-7
  29. Jenkins P., Embedding a restricted class of partial K 4 designs, Ars Combin. 77 (2005), 295–303. MR2180852
  30. Jenkins P., 10.1002/jcd.20087, J. Combin. Des. 14 (2006), no. 4, 270–276. MR2229878DOI10.1002/jcd.20087
  31. Jenkins P., 10.1017/S0004972700038715, Bull. Austral. Math. Soc. 73 (2006), 159–160. DOI10.1017/S0004972700038715
  32. Keevash P., 10.1007/978-3-662-59204-5_9, I. Bárány, G. Katona, A. Sali eds., Building Bridges II., Bolyai Society Mathematical Studies, 28, Springer, Berlin, 2019. DOI10.1007/978-3-662-59204-5_9
  33. König D., 10.1007/BF01456961, Math. Ann. 77 (1916), no. 4, 453–465 (German). MR1511872DOI10.1007/BF01456961
  34. Luria Z., New bounds on the number of n -queens configurations, available at arXiv: 1705.05225v2 [math.CO] (2017), 12 pages. 
  35. Lindner C. C., 10.4153/CMB-1970-013-x, Canad. Math. Bull. 13 (1970), no. 1, 65–68. MR0262092DOI10.4153/CMB-1970-013-x
  36. Lindner C. C., 10.1016/0097-3165(72)90067-2, J. Combinatorial Theory Ser. A. 13 (1972), 339–345. MR0314649DOI10.1016/0097-3165(72)90067-2
  37. Lindner C. C., 10.1007/BFb0066437, Graphs and Combinatorics, Lecture Notes in Math., 406, Springer, Berlin, 1974, pages 109–152. MR0379211DOI10.1007/BFb0066437
  38. Lindner C. C., 10.1016/0097-3165(75)90046-1, J. Comb. Theory Ser. A. 18 (1975), 349–351. MR0379223DOI10.1016/0097-3165(75)90046-1
  39. Lindner C. C., 10.1090/S0002-9939-1976-0409227-2, Proc. Amer. Math. Soc. 59 (1976), no. 1, 184–186. MR0409227DOI10.1090/S0002-9939-1976-0409227-2
  40. Lindner C. C., Cruse A. B., 10.1112/jlms/s2-12.4.479, J. London Math. Soc. (2) 12 (1976), 479–484. MR0432796DOI10.1112/jlms/s2-12.4.479
  41. Mann H. B., 10.1214/aoms/1177731539, Ann. Math. Statistics 13 (1942), 418–423. MR0007736DOI10.1214/aoms/1177731539
  42. Mann H. B., Ryser H. J., 10.1080/00029890.1953.11988312, Amer. Math. Monthly 60 (1953), no. 6, 397–401. MR0055293DOI10.1080/00029890.1953.11988312
  43. Nosov V. A., Sachkov V. N., Tarakanov V. E., Combinatorial analysis (matrix problems, the theory of sampling), Probability Theory. Mathematical Statistics. Theoretical Cybernetics. 188, Akad. Nauk SSSR, Vsesoyuz. Inst. Nauchn. i Tekhn. Informatsii, Moscow 18 (1981), 53–93, 188 (Russian). MR0625132
  44. Quackenbush R. W., Near vector spaces over GF ( q ) and ( v , q + 1 , 1 ) -BIBDs, Linear Algebra Appl. 10 (1975), 259–266. MR0369099
  45. Rodger C. A., 10.1016/0012-365X(87)90141-5, Discrete Math. 65 (1987), no. 2, 187–196. MR0893080DOI10.1016/0012-365X(87)90141-5
  46. Rodger C. A., Recent results on the embedding of Latin squares and related structures, cycle systems and graph designs, Matematiche (Catania) 47 (1992), no. 2, 295–311. MR1275861
  47. Ryser H. J., 10.1090/S0002-9939-1951-0042361-0, Proc. Amer. Math. Soc. 2 (1951), 550–552. MR0042361DOI10.1090/S0002-9939-1951-0042361-0
  48. Smetaniuk B., A new construction on Latin squares. I. A proof of the Evans conjecture, Ars Combin. 11 (1981), 155–172. MR0629869
  49. Stevens B., Mendelsohn E., 10.1002/(SICI)1520-6610(1999)7:3<185::AID-JCD3>3.0.CO;2-3, J. Combin. Des. 7 (1999), no. 3, 185–203. MR1681504DOI10.1002/(SICI)1520-6610(1999)7:3<185::AID-JCD3>3.0.CO;2-3
  50. Treash A. C., Inverse Property Loops and Related Steiner Triple Systems, Ph.D. Thesis, Emory University, Atlanta, 1969. MR2618359
  51. Treash C., 10.1016/0097-3165(71)90030-6, Combinatorial Theory, Ser. A. 10 (1971), 259–265. MR0274634DOI10.1016/0097-3165(71)90030-6
  52. Vodička M., Zlatoš P., 10.26493/1855-3974.1884.5cb, Ars Math. Contemp. 17 (2019), no. 2, 535–554. MR4041359DOI10.26493/1855-3974.1884.5cb
  53. Van der Waerden B. L., 10.1007/BF02952519, Abh. Math. Sem. Univ. Hamburg 5 (1927), no. 1, 185–188 (German). MR3069474DOI10.1007/BF02952519
  54. Wallis W. D., Zhu L., Orthogonal Latin squares with small subsquares, Combinatorial Mathematics, X, Adelaide, 1982, Lecture Notes in Math., 1036, Springer, Berlin, 1983, pages 398–409. MR0731596
  55. Wanless I. M., Webb B. S., Small partial Latin squares that cannot be embedded in a Cayley table, Australas. J. Combin. 67 (2017), no. 2, 352–363. MR3607832
  56. Zhu L., 10.1016/0012-365X(84)90191-2, Discrete Math. 48 (1984), no. 2–3, 315–321. MR0737274DOI10.1016/0012-365X(84)90191-2
  57. Zhu L., Some results on orthogonal Latin squares with orthogonal subsquares, Utilitas Math. 25 (1984), 241–248. MR0752862
  58. Zhu L., Zhang H., 10.1016/S0012-365X(03)00053-0, Discrete Math. 268 (2003), no. 1–3, 343–349. MR1983294DOI10.1016/S0012-365X(03)00053-0

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.