Previous |  Up |  Next

Article

Keywords:
embedding; mutually orthogonal Latin square
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$.
References:
[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. DOI 10.1016/j.disc.2014.11.018 | MR 3300747
[2] Andersen L. D., Hilton A. J. W.: Thanks Evans!. Proc. London Math. Soc. (3) 47 (1983), no. 3, 507–522. MR 0716801
[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. DOI 10.1112/jlms/s2-26.1.21 | MR 0667240
[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. DOI 10.1016/j.jcta.2017.04.005 | MR 3663493
[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
[6] Bryant D., Buchanan M.: Embedding partial totally symmetric quasigroups. J. Combin. Theory Ser. A 114 (2007), no. 6, 1046–1088. DOI 10.1016/j.jcta.2006.10.009 | MR 2337238
[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. DOI 10.1002/jcd.20189 | MR 2475426
[8] Colbourn C. J.: The complexity of completing partial Latin squares. Discrete Appl. Math. 8 (1984), 25–30. DOI 10.1016/0166-218X(84)90075-1 | MR 0739595
[9] Colbourn C. J., Dinitz J. H.: Handbook of Combinatorial Designs. Chapman and Hall/CRC, 2007. MR 2246267
[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
[11] Cruse A. B.: On embedding incomplete symmetric Latin squares. J. Combinatorial Theory Ser. A. 16 (1974), 18–22. DOI 10.1016/0097-3165(74)90068-5 | MR 0329925
[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
[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. DOI 10.1016/j.jsc.2017.04.002 | MR 3725217
[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. DOI 10.1016/j.disc.2020.111835 | MR 4062293
[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. DOI 10.1016/j.jcta.2014.04.003 | MR 3213305
[16] Drake D. A., Lenz H.: Orthogonal Latin squares with orthogonal subsquares. Arch. Math. (Basel) 34 (1980), no. 6, 565–576. DOI 10.1007/BF01225000 | MR 0596867
[17] Evans A. B.: Orthomorphism Graphs of Groups. Lecture Notes in Mathematics, 1535, Springer, Berlin, 1992. MR 1222645
[18] Evans T.: Embedding incomplete latin squares. Amer. Math. Monthly 67 (1960), 958–961. DOI 10.1080/00029890.1960.11992032 | MR 0122728
[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.: Endliche Vervollständigung endlicher partieller Steinerscher Systeme. Arch. Math. (Basel) 22 (1971), 328–332 (German). DOI 10.1007/BF01222584 | MR 0294145
[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
[22] Gustavsson T.: Decompositions of Large Graphs and Digraphs with High Minimum Degree. Ph.D. Thesis, Stockholm University, Stockholm, 1991.
[23] Hall M.: An existence theorem for Latin squares. Bull. Amer. Math. Soc. 51 (1945), 387–388. DOI 10.1090/S0002-9904-1945-08361-X | MR 0013111
[24] Hall P.: On representative subsets. Classic Papers in Combinatorics, Birkhäuser, Boston, 1987, pages 58–62.
[25] Heinrich K., Zhu L.: Existence of orthogonal Latin squares with aligned subsquares. Discrete Math. 59 (1986), no. 1–2, 69–78. DOI 10.1016/0012-365X(86)90070-1 | MR 0837956
[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
[27] Hirsch R., Jackson M.: Undecidability of representability as binary relations. J. Symbolic Logic 77 (2012), no. 4, 1211–1244. DOI 10.2178/jsl.7704090 | MR 3051622
[28] Horton J. D.: Sub-latin squares and incomplete orthogonal arrays. J. Combinatorial Theory Ser. A 16 (1974), 23–33. DOI 10.1016/0097-3165(74)90069-7 | MR 0347641
[29] Jenkins P.: Embedding a restricted class of partial $K_4$ designs. Ars Combin. 77 (2005), 295–303. MR 2180852
[30] Jenkins P.: Embedding a Latin square in a pair of orthogonal Latin squares. J. Combin. Des. 14 (2006), no. 4, 270–276. DOI 10.1002/jcd.20087 | MR 2229878
[31] Jenkins P.: Partial graph design embeddings and related problems. Bull. Austral. Math. Soc. 73 (2006), 159–160. DOI 10.1017/S0004972700038715
[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. DOI 10.1007/978-3-662-59204-5_9
[33] König D.: Über Graphen und ihre Anwendungen auf Determinantentheorie und Mengenlehre. Math. Ann. 77 (1916), no. 4, 453–465 (German). DOI 10.1007/BF01456961 | MR 1511872
[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.: On completing latin rectangles. Canad. Math. Bull. 13 (1970), no. 1, 65–68. DOI 10.4153/CMB-1970-013-x | MR 0262092
[36] Lindner C. C.: Finite embedding theorems for partial Latin squares, quasi-groups, and loops. J. Combinatorial Theory Ser. A. 13 (1972), 339–345. DOI 10.1016/0097-3165(72)90067-2 | MR 0314649
[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. DOI 10.1007/BFb0066437 | MR 0379211
[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. DOI 10.1016/0097-3165(75)90046-1 | MR 0379223
[39] Lindner C. C.: Embedding orthogonal partial Latin squares. Proc. Amer. Math. Soc. 59 (1976), no. 1, 184–186. DOI 10.1090/S0002-9939-1976-0409227-2 | MR 0409227
[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. DOI 10.1112/jlms/s2-12.4.479 | MR 0432796
[41] Mann H. B.: The construction of orthogonal Latin squares. Ann. Math. Statistics 13 (1942), 418–423. DOI 10.1214/aoms/1177731539 | MR 0007736
[42] Mann H. B., Ryser H. J.: Systems of distinct representatives. Amer. Math. Monthly 60 (1953), no. 6, 397–401. DOI 10.1080/00029890.1953.11988312 | MR 0055293
[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
[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
[45] Rodger C. A.: Embedding partial Mendelsohn triple systems. Discrete Math. 65 (1987), no. 2, 187–196. DOI 10.1016/0012-365X(87)90141-5 | MR 0893080
[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
[47] Ryser H. J.: A combinatorial theorem with an application to Latin rectangles. Proc. Amer. Math. Soc. 2 (1951), 550–552. DOI 10.1090/S0002-9939-1951-0042361-0 | MR 0042361
[48] Smetaniuk B.: A new construction on Latin squares. I. A proof of the Evans conjecture. Ars Combin. 11 (1981), 155–172. MR 0629869
[49] Stevens B., Mendelsohn E.: New recursive methods for transversal covers. J. Combin. Des. 7 (1999), no. 3, 185–203. DOI 10.1002/(SICI)1520-6610(1999)7:3<185::AID-JCD3>3.0.CO;2-3 | MR 1681504
[50] Treash A. C.: Inverse Property Loops and Related Steiner Triple Systems. Ph.D. Thesis, Emory University, Atlanta, 1969. MR 2618359
[51] Treash C.: The completion of finite incomplete Steiner triple systems with application to loop theory. Combinatorial Theory, Ser. A. 10 (1971), 259–265. DOI 10.1016/0097-3165(71)90030-6 | MR 0274634
[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. DOI 10.26493/1855-3974.1884.5cb | MR 4041359
[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). DOI 10.1007/BF02952519 | MR 3069474
[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
[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
[56] Zhu L.: Orthogonal Latin squares with subsquares. Discrete Math. 48 (1984), no. 2–3, 315–321. DOI 10.1016/0012-365X(84)90191-2 | MR 0737274
[57] Zhu L.: Some results on orthogonal Latin squares with orthogonal subsquares. Utilitas Math. 25 (1984), 241–248. MR 0752862
[58] Zhu L., Zhang H.: Completing the spectrum of $r$-orthogonal latin squares. Discrete Math. 268 (2003), no. 1–3, 343–349. DOI 10.1016/S0012-365X(03)00053-0 | MR 1983294
Partner of
EuDML logo