| Title:
|
Constructing and embedding mutually orthogonal Latin squares: reviewing both new and existing results (English) |
| Author:
|
Donovan, Diane M. |
| Author:
|
Grannell, Mike |
| Author:
|
Yazıcı, Emine Ş. |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
61 |
| Issue:
|
4 |
| Year:
|
2020 |
| Pages:
|
437-457 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
embedding |
| Keyword:
|
mutually orthogonal Latin square |
| MSC:
|
05B15 |
| idZBL:
|
Zbl 07332721 |
| idMR:
|
MR4230952 |
| DOI:
|
10.14712/1213-7243.2021.003 |
| . |
| Date available:
|
2021-02-25T12:36:45Z |
| Last updated:
|
2023-01-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148657 |
| . |
| Reference:
|
[1] Abel R. J. R., Li Y.: Some constructions for $t$ pairwise orthogonal diagonal Latin squares based on difference matrices.Discrete Math. 338 (2015), no. 4, 593–607. MR 3300747, 10.1016/j.disc.2014.11.018 |
| Reference:
|
[2] Andersen L. D., Hilton A. J. W.: Thanks Evans!.Proc. London Math. Soc. (3) 47 (1983), no. 3, 507–522. MR 0716801 |
| Reference:
|
[3] Andersen L. D., Hilton A. J. W., Rodger C. A.: A solution to the embedding problem for partial idempotent Latin squares.J. London Math. Soc. (2) 26 (1982), no. 1, 21–27. MR 0667240, 10.1112/jlms/s2-26.1.21 |
| Reference:
|
[4] Barber B., Kühn D., Lo A., Osthus D., Taylor A.: Clique decompositions of multipartite graphs and completion of Latin squares.J. Combin. Theory Ser. A. 151 (2017), 146–201. MR 3663493, 10.1016/j.jcta.2017.04.005 |
| Reference:
|
[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 $n$-arnykh Kvazigrupp 83 (1985), 26–38 (Russian). MR 0807271 |
| Reference:
|
[6] Bryant D., Buchanan M.: Embedding partial totally symmetric quasigroups.J. Combin. Theory Ser. A 114 (2007), no. 6, 1046–1088. MR 2337238, 10.1016/j.jcta.2006.10.009 |
| Reference:
|
[7] Bryant D., Horsley D.: A proof of Lindner's conjecture on embeddings of partial Steiner triple systems.J. Comb. Des. 17 (2009), no. 1, 63–89. MR 2475426, 10.1002/jcd.20189 |
| Reference:
|
[8] Colbourn C. J.: The complexity of completing partial Latin squares.Discrete Appl. Math. 8 (1984), 25–30. MR 0739595, 10.1016/0166-218X(84)90075-1 |
| Reference:
|
[9] Colbourn C. J., Dinitz J. H.: Handbook of Combinatorial Designs.Chapman and Hall/CRC, 2007. MR 2246267 |
| Reference:
|
[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. MR 1366841 |
| Reference:
|
[11] Cruse A. B.: On embedding incomplete symmetric Latin squares.J. Combinatorial Theory Ser. A. 16 (1974), 18–22. MR 0329925, 10.1016/0097-3165(74)90068-5 |
| Reference:
|
[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. MR 0716802 |
| Reference:
|
[13] Dietrich H., Wanless I. M.: Small partial Latin squares that embed in an infinite group but not into any finite group.J. Symbolic Comput. 86 (2018), 142–152. MR 3725217, 10.1016/j.jsc.2017.04.002 |
| Reference:
|
[14] Donovan D., Grannell M., Yazıcı E. Ş.: Embedding partial Latin squares in Latin squares with many mutually orthogonal mates.Discrete Math. 343 (2020), no. 6, 111835, 6 pages. MR 4062293, 10.1016/j.disc.2020.111835 |
| Reference:
|
[15] Donovan D. M., Yazıcı E. Ş.: A polynomial embedding of pairs of orthogonal partial Latin squares.J. Combin. Theory Ser. A 126 (2014), 24–34. MR 3213305, 10.1016/j.jcta.2014.04.003 |
| Reference:
|
[16] Drake D. A., Lenz H.: Orthogonal Latin squares with orthogonal subsquares.Arch. Math. (Basel) 34 (1980), no. 6, 565–576. MR 0596867, 10.1007/BF01225000 |
| Reference:
|
[17] Evans A. B.: Orthomorphism Graphs of Groups.Lecture Notes in Mathematics, 1535, Springer, Berlin, 1992. MR 1222645 |
| Reference:
|
[18] Evans T.: Embedding incomplete latin squares.Amer. Math. Monthly 67 (1960), 958–961. MR 0122728, 10.1080/00029890.1960.11992032 |
| Reference:
|
[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. |
| Reference:
|
[20] Ganter B.: Endliche Vervollständigung endlicher partieller Steinerscher Systeme.Arch. Math. (Basel) 22 (1971), 328–332 (German). MR 0294145, 10.1007/BF01222584 |
| Reference:
|
[21] Ganter B.: Partial pairwise balanced designs.Colloq. Int. Sulle Teorie Combinatorie, Rome, 1973, Tomo II, Accad. Naz. Lincei, 1976, pages 377–380. MR 0472553 |
| Reference:
|
[22] Gustavsson T.: Decompositions of Large Graphs and Digraphs with High Minimum Degree.Ph.D. Thesis, Stockholm University, Stockholm, 1991. |
| Reference:
|
[23] Hall M.: An existence theorem for Latin squares.Bull. Amer. Math. Soc. 51 (1945), 387–388. MR 0013111, 10.1090/S0002-9904-1945-08361-X |
| Reference:
|
[24] Hall P.: On representative subsets.Classic Papers in Combinatorics, Birkhäuser, Boston, 1987, pages 58–62. |
| Reference:
|
[25] Heinrich K., Zhu L.: Existence of orthogonal Latin squares with aligned subsquares.Discrete Math. 59 (1986), no. 1–2, 69–78. MR 0837956, 10.1016/0012-365X(86)90070-1 |
| Reference:
|
[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. MR 1160067 |
| Reference:
|
[27] Hirsch R., Jackson M.: Undecidability of representability as binary relations.J. Symbolic Logic 77 (2012), no. 4, 1211–1244. MR 3051622, 10.2178/jsl.7704090 |
| Reference:
|
[28] Horton J. D.: Sub-latin squares and incomplete orthogonal arrays.J. Combinatorial Theory Ser. A 16 (1974), 23–33. MR 0347641, 10.1016/0097-3165(74)90069-7 |
| Reference:
|
[29] Jenkins P.: Embedding a restricted class of partial $K_4$ designs.Ars Combin. 77 (2005), 295–303. MR 2180852 |
| Reference:
|
[30] Jenkins P.: Embedding a Latin square in a pair of orthogonal Latin squares.J. Combin. Des. 14 (2006), no. 4, 270–276. MR 2229878, 10.1002/jcd.20087 |
| Reference:
|
[31] Jenkins P.: Partial graph design embeddings and related problems.Bull. Austral. Math. Soc. 73 (2006), 159–160. 10.1017/S0004972700038715 |
| Reference:
|
[32] Keevash P.: Coloured and directed designs.I. Bárány, G. Katona, A. Sali eds., Building Bridges II., Bolyai Society Mathematical Studies, 28, Springer, Berlin, 2019. 10.1007/978-3-662-59204-5_9 |
| Reference:
|
[33] König D.: Über Graphen und ihre Anwendungen auf Determinantentheorie und Mengenlehre.Math. Ann. 77 (1916), no. 4, 453–465 (German). MR 1511872, 10.1007/BF01456961 |
| Reference:
|
[34] Luria Z.: New bounds on the number of $n$-queens configurations.available at arXiv: 1705.05225v2 [math.CO] (2017), 12 pages. |
| Reference:
|
[35] Lindner C. C.: On completing latin rectangles.Canad. Math. Bull. 13 (1970), no. 1, 65–68. MR 0262092, 10.4153/CMB-1970-013-x |
| Reference:
|
[36] Lindner C. C.: Finite embedding theorems for partial Latin squares, quasi-groups, and loops.J. Combinatorial Theory Ser. A. 13 (1972), 339–345. MR 0314649, 10.1016/0097-3165(72)90067-2 |
| Reference:
|
[37] Lindner C. C.: A survey of finite embedding theorems for partial Latin squares and quasigroups.Graphs and Combinatorics, Lecture Notes in Math., 406, Springer, Berlin, 1974, pages 109–152. MR 0379211, 10.1007/BFb0066437 |
| Reference:
|
[38] Lindner C. C.: A partial Steiner triple system of order $n$ can be embedded in a Steiner triple system of order $6n+3$.J. Comb. Theory Ser. A. 18 (1975), 349–351. MR 0379223, 10.1016/0097-3165(75)90046-1 |
| Reference:
|
[39] Lindner C. C.: Embedding orthogonal partial Latin squares.Proc. Amer. Math. Soc. 59 (1976), no. 1, 184–186. MR 0409227, 10.1090/S0002-9939-1976-0409227-2 |
| Reference:
|
[40] Lindner C. C., Cruse A. B.: Small embeddings for partial semisymmetric and totally symmetric quasigroups.J. London Math. Soc. (2) 12 (1976), 479–484. MR 0432796, 10.1112/jlms/s2-12.4.479 |
| Reference:
|
[41] Mann H. B.: The construction of orthogonal Latin squares.Ann. Math. Statistics 13 (1942), 418–423. MR 0007736, 10.1214/aoms/1177731539 |
| Reference:
|
[42] Mann H. B., Ryser H. J.: Systems of distinct representatives.Amer. Math. Monthly 60 (1953), no. 6, 397–401. MR 0055293, 10.1080/00029890.1953.11988312 |
| Reference:
|
[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). MR 0625132 |
| Reference:
|
[44] Quackenbush R. W.: Near vector spaces over GF$(q)$ and $(v,q+1,1)$-BIBDs.Linear Algebra Appl. 10 (1975), 259–266. MR 0369099 |
| Reference:
|
[45] Rodger C. A.: Embedding partial Mendelsohn triple systems.Discrete Math. 65 (1987), no. 2, 187–196. MR 0893080, 10.1016/0012-365X(87)90141-5 |
| Reference:
|
[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. MR 1275861 |
| Reference:
|
[47] Ryser H. J.: A combinatorial theorem with an application to Latin rectangles.Proc. Amer. Math. Soc. 2 (1951), 550–552. MR 0042361, 10.1090/S0002-9939-1951-0042361-0 |
| Reference:
|
[48] Smetaniuk B.: A new construction on Latin squares. I. A proof of the Evans conjecture.Ars Combin. 11 (1981), 155–172. MR 0629869 |
| Reference:
|
[49] Stevens B., Mendelsohn E.: New recursive methods for transversal covers.J. Combin. Des. 7 (1999), no. 3, 185–203. MR 1681504, 10.1002/(SICI)1520-6610(1999)7:3<185::AID-JCD3>3.0.CO;2-3 |
| Reference:
|
[50] Treash A. C.: Inverse Property Loops and Related Steiner Triple Systems.Ph.D. Thesis, Emory University, Atlanta, 1969. MR 2618359 |
| Reference:
|
[51] Treash C.: The completion of finite incomplete Steiner triple systems with application to loop theory.Combinatorial Theory, Ser. A. 10 (1971), 259–265. MR 0274634, 10.1016/0097-3165(71)90030-6 |
| Reference:
|
[52] Vodička M., Zlatoš P.: The finite embeddability property for IP loops and local embeddability of groups into finite IP loops.Ars Math. Contemp. 17 (2019), no. 2, 535–554. MR 4041359, 10.26493/1855-3974.1884.5cb |
| Reference:
|
[53] Van der Waerden B. L.: Ein Satz über Klasseneinteilungen von endlichen Mengen.Abh. Math. Sem. Univ. Hamburg 5 (1927), no. 1, 185–188 (German). MR 3069474, 10.1007/BF02952519 |
| Reference:
|
[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. MR 0731596 |
| Reference:
|
[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. MR 3607832 |
| Reference:
|
[56] Zhu L.: Orthogonal Latin squares with subsquares.Discrete Math. 48 (1984), no. 2–3, 315–321. MR 0737274, 10.1016/0012-365X(84)90191-2 |
| Reference:
|
[57] Zhu L.: Some results on orthogonal Latin squares with orthogonal subsquares.Utilitas Math. 25 (1984), 241–248. MR 0752862 |
| Reference:
|
[58] Zhu L., Zhang H.: Completing the spectrum of $r$-orthogonal latin squares.Discrete Math. 268 (2003), no. 1–3, 343–349. MR 1983294, 10.1016/S0012-365X(03)00053-0 |
| . |
