×

Enumerating partial Latin rectangles. (English) Zbl 1443.05026

The object of this paper is to enumerate PLR\((r,s,n;m)\) which is defined to be the set of \(r\times s\) partial Latin rectangles on \(n\) symbols, with \(m\) non-empty cells. In other words, PLR\((r,s,n;m)\) is the set of \(r\times s\) partial matrices with \(m\) filled cells and \(rs-m\) empty cells, in which each entry is a symbol from \(\{1,2,\dots,n\}\) and no symbol is ever repeated within a row or within a column. These objects are counted and classified (up to several different notions of equivalence) for all small values of the parameters. The computations are extensively crosschecked to ensure accuracy. An interesting variety of methods are used, including inclusion-exclusion, chromatic polynomials and algebraic geometry.

MSC:

05B15 Orthogonal arrays, Latin squares, Room squares
05A15 Exact enumeration problems, generating functions

Software:

Traces; nauty; GRAPE; gmp; GAP; MINION; bliss
PDFBibTeX XMLCite
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Number of species of partial Latin squares of size n.

References:

[1] P. Adams, R. Bean, and A. Khodkar,A census of critical sets in the Latin squares of order at most six, Ars Comb.68(2003), 203-223. · Zbl 1072.05511
[2] W. Adams and P. Loustaunau,An introduction to Gr¨obner bases, Graduate Studies in Mathematics3, Am. Math. Soc., 1994. · Zbl 0803.13015
[3] S. D. Andres, H. Bergold, and R. M. Falc´on,Autoparatopism stabilized colouring games on rook’s graphs, Electron. Notes Discret. Math.68(2018), 233-238. · Zbl 1397.05115
[4] S. D. Andres and R. M. Falc´on,Autotopism stabilized colouring games on rook’s graphs, Discrete Appl. Math.266(2019), 200-212. · Zbl 1464.05264
[5] S. D. Andres and R. M. Falc´on,Colouring games based on autotopisms of Latin hyper-rectangles, Quaest. Math.42(2019), 953-975. · Zbl 1420.05114
[6] G. E. Andrews,The theory of partitions, Cambridge University Press, 1984. · Zbl 0655.10001
[7] E. Arnold, S. Lucas, and L. Taalman,Gr¨obner basis representations of sudoku, College Mathematics Journal41(2010), 101-112. · Zbl 1272.97031
[8] R. Artzy,A note on the automorphisms of special loops, Riveon Lematematika8 (1954), 81, In Hebrew.
[9] R. A. Bailey,Latin squares with highly transitive automorphism groups, J. Aust. Math. Soc.33(1982), 18-22. · Zbl 0496.05011
[10] S. E. Bammel and J. Rothstein,The number of9×9Latin squares, Discrete Math. 11(1975), 93-95. · Zbl 0304.05007
[11] D. Bayer,The division algorithm and the Hilbert scheme, Ph.D. Thesis, Harvard University, 1982.
[12] A. Bj¨orklund, T. Husfeldt, P. Kaski, and M. Koivisto,Computing the Tutte polynomial in vertex-exponential time, Proc. IEEE Foundations of Computer Science, 2008, pp. 677-686.
[13] J. Browning, D. S. Stones, and I. M. Wanless,Bounds on the number of autotopisms and subsquares of a Latin square, Combinatorica33(2013), 11-22. · Zbl 1299.05028
[14] D. Bryant, M. Buchanan, and I. M. Wanless,The spectrum for quasigroups with cyclic automorphisms and additional symmetries, Discrete Math.304(2009), 821-833. · Zbl 1221.20047
[15] N. J. Cavenagh and D. S. Stones,Near-automorphisms of Latin squares, J. Combin. Des.19(2011), 365-377. · Zbl 1233.05053
[16] D. A. Cox, J. B. Little, and D. O’Shea,Ideals, varieties, and algorithms. an introduction to computational algebraic geometry and commutative algebra, Springer, New York, 2007. · Zbl 1118.13001
[17] E. Danan, R. M. Falc´on, D. Kotlar, T. G. Marbach, and R. J. Stones,Two-line graphs of partial Latin rectangles, Electron. Notes Discret. Math.68(2018), 53-58. · Zbl 1397.05027
[18] E. Danan, R. M. Falc´on, D. Kotlar, T. G. Marbach, and R. J. Stones,Refining invariants for computing autotopism groups of partial Latin rectangles, Discrete Math. 343(2020), paper 111812. · Zbl 1435.05037
[19] W. Decker, G.-M. Greuel, G. Pfister, and H. Sch¨onemann,Singular4-1-2 — A computer algebra system for polynomial computations, 2019, http://www.singular.uni-kl.de.
[20] H. Dietrich and I. M. Wanless,Small partial Latin squares that embed in an infinite group but not into any finite group, J. Symbolic Comput.86(2018), 142-152. · Zbl 1380.05019
[21] A. A. Drisko,Loops of orderpn+ 1with transitive automorphism groups, Adv. Math. 128(1997), 36-39. · Zbl 0879.20039
[22] O. J. Falc´on, R. M. Falc´on, J. N´u˜nez, A. M. Pacheco, and M. T. Villar,Computation of isotopisms of algebras over finite fields by means of graph invariants, J. Comput. Appl. Math318(2017), 307-315. · Zbl 1355.05125
[23] R. M. Falc´on,Latin squares associated to principal autotopisms of long cycles. Application in cryptography, Proc. Transgressive Computing, 2006, pp. 213-230. · Zbl 1203.05022
[24] R. M. Falc´on,Study of critical sets in Latin squares by using the autotopism group, Electron. Notes Discret. Math.29(2007), 503-507. · Zbl 1341.05018
[25] R. M. Falc´on,0/1-polytopes related to Latin squares autotopisms, Proc. VI Jornadas de Matem´atica Discreta y Algor´ıtmica, 2008, pp. 311-319.
[26] R. M. Falc´on,Cycle structures of autotopisms of the Latin squares of order up to11, Ars Combin.103(2012), 239-256. · Zbl 1265.05077
[27] R. M. Falc´on,The set of autotopisms of partial Latin squares, Discrete Math.313 (2013), 1150-1161. · Zbl 1277.05024
[28] R. M. Falc´on,Enumeration and classification of self-orthogonal partial Latin rectangles by using the polynomial method, European J. Combin.48(2015), 215-223. · Zbl 1315.05023
[29] R. M. Falc´on,Using a CAS/DGS to analyze computationally the configuration of planar bar linkage mechanisms based on partial Latin squares, Math. Comput. Sci. 14(2020), 375-389. · Zbl 1455.05014
[30] R. M. Falc´on, O. J. Falc´on, and J. N´u˜nez,Counting and enumerating partial Latin rectangles by means of computer algebra systems and CSP solvers, Math. Methods Appl. Sci.41(2018), 7236-7262. · Zbl 1409.05039
[31] R. M. Falc´on, O. J. Falc´on, and J. N´u˜nez,A historical perspective of the theory of isotopisms, Symmetry10(2018), paper 322. · Zbl 1423.17018
[32] R. M. Falc´on and J. Mart´ın-Morales,Gr¨obner bases and the number of Latin squares related to autotopisms of order67, J. Symbolic Comput.42(2007), 1142-1154. · Zbl 1129.05007
[33] R. M. Falc´on and J. N´u˜nez,Partial Latin squares having a Santilli’s autotopism in their autotopism groups, J. Dyn. Syst. Geom. Theor.5(2007), 19-32. · Zbl 1133.05014
[34] R. M. Falc´on and R. J. Stones,Classifying partial Latin rectangles, Electronic Notes in Discrete Mathematics49(2015), 765-771. · Zbl 1346.05021
[35] R. M. Falc´on and R. J. Stones,Enumerating partial Latin rectangles, Mendeley Data, v1 (2017),http://dx.doi.org/10.17632/4c559g2xny.1.
[36] R. M. Falc´on and R. J. Stones,Partial Latin rectangle graphs and autoparatopism groups of partial Latin rectangles with trivial autotopism groups, Discrete Math.340 (2017), 1242-1260. · Zbl 1422.05027
[37] J. Gago-Vargas, I. Hartillo-Hermoso, J. Mart´ın-Morales, and J. M. Ucha-Enr´ıquez, Sudokus and Gr¨obner bases not only a divertimento, Lect. Notes Comput. Sc.4194 (2006), 155-165. · Zbl 1141.68686
[38] The GAP Group,GAP- Groups, algorithms, programming - A system for computational discrete algebra, (2017),http://www.gap-system.org/.
[39] I. P. Gent, C. Jefferson, and I. Miguel,Minion: a fast scalable constraint solver, Proc. European Conference on Artificial Intelligence (G. Brewka, S. Coradeschi, A. Perini, and P. Traverso., eds.), 2006, pp. 98-102.
[40] T. Granlund et al.,GNU multiple precision arithmetic library, (2017),http:// gmplib.org/.
[41] A. Hulpke, P. Kaski, and P. R. J. ¨Osterg˚ard,The number of Latin squares of order 11, Math. Comp.80(2011), 1197-1219. · Zbl 1210.05017
[42] E. C. Ihrig and B. M. Ihrig,The recognition of symmetric Latin squares, J. Combin. Des.16(2008), 291-300. · Zbl 1146.05010
[43] T. Junttila and P. Kaski,Engineering an efficient canonical labeling tool for large and sparse graphs, Proc. Workshop on Algorithm Engineering and Experiments and the Workshop on Analytic Algorithms and Combinatorics, 2007, pp. 135-149. · Zbl 1428.68222
[44] B. Kerby and J. D. H. Smith,Quasigroup automorphisms and symmetric group characters, Comment. Math. Univ. Carol.51(2010), 279-286. · Zbl 1211.20063
[45] B. Kerby and J. D. H. Smith,Quasigroup automorphisms and the Norton-Stein complex, Proc. Amer. Math. Soc.138(2010), 3079-3088. · Zbl 1227.20062
[46] M. Kreuzer and L. Robbiano,Computational commutative algebra, Springer-Verlag Berlin Heidelberg, 2000. · Zbl 0956.13008
[47] C. F. Laywine and G. L. Mullen,Discrete Mathematics using Latin squares, Series in Discrete Mathematics and Optimization, Wiley-Interscience, 1998. · Zbl 0957.05002
[48] B. D. McKay,Practical graph isomorphism, Congr. Numer.30(1981), 45-87. · Zbl 0521.05061
[49] B. D. McKay,nauty- Graph isomorphic software, (2017), http://cs.anu.edu.au/ bdm/nauty/.
[50] B. D. McKay, A. Meynert, and W. Myrvold,Small Latin squares, quasigroups, and loops, J. Combin. Des.15(2007), 98-119. · Zbl 1112.05018
[51] B. D. McKay and A. Piperno,Practical graph isomorphism, II, J. Symbolic Computation60(2014), 94-112. · Zbl 1394.05079
[52] B. D. McKay and E. Rogoyski,Latin squares of order ten, Electron. J. Combin.2 (1995), #N3. · Zbl 0824.05010
[53] B. D. McKay and I. M. Wanless,On the number of Latin squares, Ann. Comb.9 (2005), 335-344. · Zbl 1073.05013
[54] B. D. McKay, I. M. Wanless, and X. Zhang,The order of automorphisms of quasigroups, J. Combin. Des.23(2015), 275-288. · Zbl 1327.05043
[55] M. J. L. Mendis and I. M. Wanless,Latin squares with a unique intercalate, J. Combin. Des.24(2016), 79-293. · Zbl 1338.05025
[56] M. J. L. Mendis and I. M. Wanless,Autoparatopisms of quasigroups and Latin squares, J. Combin. Des.25(2017), 51-74. · Zbl 1362.05027
[57] H. Meng, Y. Zheng, and Y. Zheng,The classification construction and the nonisomorphism counting of symmetric Latin square, Adv. Stud. Contemp. Math. (Kyungshang)17(2008), 169-179. · Zbl 1173.68592
[58] A. A. Sade,Enum´´eration des Carr´es Latins, Application au7eOrdre, Conjecture pour les Ordres Sup´erieurs, privately published (1948), 8 pp. · Zbl 0035.28902
[59] Y. Sato, S. Inoue, A. Suzuki, K. Nabeshi, and K. Sakai,Boolean Gr¨obner bases, J. Sym. Comp.46(2011), 622-632. · Zbl 1211.68519
[60] L. H. Soicher,GRAPE- A GAP package for computing with graphs and groups, (2017),http://www.maths.qmul.ac.uk/ leonard/grape/.
[61] D. S. Stones,The many formulae for the number of Latin rectangles, Electron. J. Combin.17(2010), #A1. · Zbl 1193.05042
[62] D. S. Stones,On the number of Latin rectangles, Ph.D. thesis, Monash University, 2010,http://arrow.monash.edu.au/hdl/1959.1/167114. · Zbl 1200.05041
[63] D. S. Stones,Symmetries of partial Latin squares, European J. Combin.34(2013), 1092-1107. · Zbl 1292.05065
[64] D. S. Stones, P. Vojtˇechovsk´y, and I. M. Wanless,Cycle structure of autotopisms of quasigroups and Latin squares, J. Combin. Des.20(2012), 227-263. · Zbl 1248.05023
[65] D. S. Stones and I. M. Wanless,Divisors of the number of Latin rectangles, J. Combin. Theory Ser. A117(2010), 204-215. · Zbl 1230.05065
[66] D. S. Stones and I. M. Wanless,A congruence connecting Latin rectangles and partial orthomorphisms, Ann. Comb.16(2012), 349-365. · Zbl 1256.05030
[67] D. S. Stones and I. M. Wanless,How not to prove the Alon-Tarsi Conjecture, Nagoya Math. J.205(2012), 1-24. · Zbl 1245.05011
[68] R. J. Stones,K-plex2-erasure codes and blackburn partial Latin squares, IEEE Trans. Inf. TheoryEarly access(2020), 1-1, https://doi.org/10.1109/TIT.2020.2967758.
[69] R. J. Stones, R. M. Falc´on, D. Kotlar, and T. G. Marbach,Computing autotopism groups of partial latin rectangles: a pilot study, Comput. Math. Method.Early view (2020), paper e1094,https://doi.org/10.1002/cmm4.1094.
[70] R. J. Stones, S. Lin, X. Liu, and G. Wang,On computing the number of Latin rectangles, Graphs. Combin.32(2016), 1187-1202. · Zbl 1338.05026
[71] R. J. Stones, M. Su, X. Liu, G. Wang, and S. Lin,A Latin square autotopism secret sharing scheme, Des. Codes Cryptogr.35(2015), 1-16. · Zbl 1347.05023
[72] I. M. Wanless and E. C. Ihrig,Symmetries that Latin squares inherit from1factorizations, J. Combin. Des.13(2005), 157-172. · Zbl 1067.05061
[73] I. M. Wanless and B. S. Webb,Small partial Latin squares that cannot be embedded in a Cayley table, Australas. J. Combin.67(2017), 352-363. · Zbl 1375.05041
[74] M. B. Wells,The number of Latin squares of order eight, J. Combin. Theory3(1967), 98-99. · Zbl 0166.01001
[75] M. Yan, J. Feng, T. G. Marbach, R. J. Stones, G. Wang, and X. Liu,Gecko: A resilient dispersal scheme for multi-cloud storage, IEEE Access7(2019), 77387- 77397.
[76] L.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.