×

Refining invariants for computing autotopism groups of partial Latin rectangles. (English) Zbl 1435.05037

A partial Latin rectangle is a partially filled matrix with the property that no symbol is repeated within any row or column. In this paper, an additional requirement is imposed for convenience, namely that no row or column should be empty. An autotopism of a partial Latin rectangle \(R\) is a triple of permutations applied to the rows, columns and symbols of \(R\), respectively, which leaves \(R\) unchanged. The set of such operations is the autotopism group of \(R\). The purpose of the present work is to study how to compute the autotopism group of partial Latin rectangles efficiently. In particular, the authors are interested in autotopism invariants that can be calculated quickly and which partition the rows, column and symbols as finely as possible. The finest possible partitions are those induced by the orbits of the autotopism group, and the authors report some computational evidence that their invariants reach this theoretical limit in almost all cases. However, they do acknowledge that there are some pathological examples, such as atomic Latin squares, for which their invariants perform very badly.
The first invariant that they study is the strong entry invariant introduced by two of the authors in an earlier paper in the same journal [Discrete Math. 340, No. 6, 1242–1260 (2017; Zbl 1422.05027)]. The second invariant is based on the cyclic structure often used for studying Latin squares, but now generalised to partial Latin rectangles.

MSC:

05B15 Orthogonal arrays, Latin squares, Room squares

Citations:

Zbl 1422.05027

Software:

Traces; pls.lib; nauty
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andres, S. D.; Falcón, R. M., Colouring games based on autotopisms of Latin hyper-rectangles, Quaest. Math., 42, 953-975 (2019) · Zbl 1420.05114
[2] Artzy, R., A note on the automorphisms of special loops, Riv. Lemat., 8, 81 (1954), (in Hebrew)
[3] L. Babai, Graph isomorphism in quasipolynomial time, in: Proc. 48th ACM STOC, 2016, pp. 684-697. · Zbl 1376.68058
[4] L. Babai, W.M. Kantor, E.M. Luks, Computational complexity and the classification of finite simple groups, in: Proc. 24th IEEE FOCS, 1983, pp. 162-171.
[5] Bailey, R. A., Latin squares with highly transitive automorphism groups, J. Aust. Math. Soc., 33, 18-22 (1982) · Zbl 0496.05011
[6] Browning, J.; Stones, D. S.; Wanless, I. M., Bounds on the number of autotopisms and subsquares of a Latin square, Combinatorica, 33, 11-22 (2013) · Zbl 1299.05028
[7] Bryant, D.; Buchanan, M.; Wanless, I. M., The spectrum for quasigroups with cyclic automorphisms and additional symmetries, Discrete Math., 304, 4, 821-833 (2009) · Zbl 1221.20047
[8] Cavenagh, N. J.; Stones, D. S., Near-automorphisms of Latin squares, J. Combin. Des., 19, 365-377 (2011) · Zbl 1233.05053
[9] Dörfler, W., Every regular graph is a quasigroup graph, Discrete Math., 10, 181-183 (1974) · Zbl 0288.05116
[10] Drisko, A. A., Loops of order \(p^n + 1\) with transitive automorphism groups, Adv. Math., 128, 36-39 (1997) · Zbl 0879.20039
[11] R.M. Falcón, Latin squares associated to principal autotopisms of long cycles. application in cryptography, in: Proc. Transgressive Computing, 2006, pp. 213-230. · Zbl 1203.05022
[12] Falcón, R. M., Study of critical sets in Latin squares by using the autotopism group, Electron. Notes Discrete Math., 29, 503-507 (2007) · Zbl 1341.05018
[13] Falcón, R. M., Cycle structures of autotopisms of the Latin squares of order up to \(11\), Ars Combin., 103, 239-256 (2012) · Zbl 1265.05077
[14] Falcón, R. M., The set of autotopisms of partial Latin squares, Discrete Math., 313, 11, 1150-1161 (2013) · Zbl 1277.05024
[15] Falcón, R. M.; Andres, S. D., Autoparatopism stabilized colouring games on rook’s graphs, Electron. Notes Discrete Math., 68, 233-238 (2018) · Zbl 1397.05115
[16] Falcón, R. M.; Martín-Morales, J., Gröbner bases and the number of Latin squares related to autotopisms of order \(\leq 7\), J. Symb. Comput., 42, 11-12, 1142-1154 (2007) · Zbl 1129.05007
[17] Falcón, R. M.; Núñez, J., Partial Latin squares having a Santilli’s autotopism in their autotopism groups, J. Dyn. Syst. Geom. Theor., 5, 19-32 (2007) · Zbl 1133.05014
[18] Falcón, R. M.; Stones, R. J., Classifying partial Latin rectangles, Electron. Notes Discrete Math., 49, 765-771 (2015) · Zbl 1346.05021
[19] Falcón, R. M.; Stones, R. J., Partial Latin rectangle graphs and autoparatopism groups of partial Latin rectangles with trivial autotopism groups, Discrete Math., 340, 6, 1242-1260 (2017) · Zbl 1422.05027
[20] R.M. Falcón, R.J. Stones, Enumerating partial Latin rectangles, (Submitted for publication). · Zbl 1346.05021
[21] Flum, J.; Grohe, M., The parameterized complexity of counting problems, SIAM J. Comput., 33, 892-922 (2004) · Zbl 1105.68042
[22] Grätzer, G., General Lattice Theory (2002), Birkhäuser Basel · Zbl 0385.06015
[23] Guibas, L. J.; Sedgewick, R., A dichromatic framework for balanced trees, (19th Annual Symposium on Foundations of Computer Science (Ann Arbor, Mich., 1978) (1978), IEEE: IEEE Long Beach, Calif.), 8-21
[24] Haanpää, H.; Östergård, P. R.J., Counting Hamiltonian cycles in bipartite graphs, Math. Comp., 83, 979-995 (2014) · Zbl 1280.05075
[25] Halford, T. R.; Chugg, K. M., An algorithm for counting short cycles in bipartite graphs, IEEE Trans. Inform. Theory, 52, 287-292 (2004) · Zbl 1316.94108
[26] Halford, T. R.; Chugg, K. M., Enumerating and counting cycles in bipartite graphs (2004)
[27] Ihrig, E. C.; Ihrig, B. M., The recognition of symmetric Latin squares, J. Combin. Des., 16, 4, 291-300 (2008) · Zbl 1146.05010
[28] Jacobson, M.; Matthews, P., Generating uniformly distributed Latin squares, J. Combin. Des., 4, 6, 405-437 (1996) · Zbl 0913.05027
[29] Karimi, M.; Banihashemi, A. H., Message-passing algorithms for counting short cycles in a graph, IEEE Trans. Commun., 61, 485-495 (2013)
[30] A.D. Keedwell, Critical sets and critical partial Latin squares, in: Proc. Third China-USA International Conf. on Graph Theory, Combinatorics, Algorithms and Applications, 1994.
[31] Kerby, B.; Smith, J. D.H., Quasigroup automorphisms and symmetric group characters, Comment. Math. Univ. Carolin., 51, 2, 279-286 (2010) · Zbl 1211.20063
[32] Kerby, B.; Smith, J. D.H., Quasigroup automorphisms and the Norton-Stein complex, Proc. Amer. Math. Soc., 138, 3079-3088 (2010) · Zbl 1227.20062
[33] Kotlar, D., Parity types, cycle structures and autotopisms of Latin squares, Electron. J. Combin., 19, 3 (2012), P10 · Zbl 1253.05048
[34] Kotlar, D., Computing the autotopy group of a Latin square by cycle structure, Discrete Math., 331, 74-82 (2014) · Zbl 1297.05039
[35] J. Li, S. Lin, K. Abdel-Ghaffar, Improved message-passing algorithm for counting short cycles in bipartite graphs, in: Proc. IEEE ISIT, 2015, pp. 416-420.
[36] Maenhaut, B. M.; Wanless, I. M., Atomic Latin squares of order eleven, J. Combin. Des., 1, 12-34 (2004) · Zbl 1036.05014
[37] McKay, B. D., Practical graph isomorphism, Congr. Numer., 30, 45-87 (1980) · Zbl 0521.05061
[38] McKay, B. D.; Meynert, A.; Myrvold, W., Small Latin squares, quasigroups, and loops, J. Combin. Des., 15, 98-119 (2007) · Zbl 1112.05018
[39] McKay, B. D.; Piperno, A., Practical graph isomorphism, II, J. Symb. Comput., 60, 94-112 (2014) · Zbl 1394.05079
[40] McKay, B. D.; Wanless, I. M., On the number of Latin squares, Ann. Comb., 9, 335-344 (2005) · Zbl 1073.05013
[41] McKay, B. D.; Wanless, I. M.; Zhang, X., The order of automorphisms of quasigroups, J. Combin. Des., 23, 275-288 (2015) · Zbl 1327.05043
[42] Mendis, M. J.L.; Wanless, I. M., Autoparatopisms of quasigroups and Latin squares, J. Combin. Des., 25, 51-74 (2017) · Zbl 1362.05027
[43] Meng, H.; Zheng, Y.; Zheng, Y., The classification construction and the non-isomorphism counting of symmetric Latin square, Adv. Stud. Contemp. Math. (Kyungshang), 17, 2, 169-179 (2008) · Zbl 1173.68592
[44] Phelps, K. T., Latin square graphs and their automorphism groups, Ars Combin., 7, 273-299 (1979) · Zbl 0421.05036
[45] Stones, D. S., Symmetries of partial Latin squares, European J. Combin., 34, 7, 1092-1107 (2013) · Zbl 1292.05065
[46] Stones, R. J.; Falcón, R. M.; Kotlar, D.; Marbach, T. G., Computing autotopism groups of partial latin rectangles: a pilot study (2019), arXiv:1910.10103 [math.CO]
[47] Stones, R. J.; Su, M.; Liu, X.; Wang, G.; Lin, S., A Latin square autotopism secret sharing scheme, Des. Codes Cryptogr., 35, 1-16 (2015)
[48] Stones, D. S.; Vojtěchovský, P.; Wanless, I. M., Cycle structure of autotopisms of quasigroups and Latin squares, J. Combin. Des., 20, 227-263 (2012) · Zbl 1248.05023
[49] Tarski, A., A lattice-theoretical fixpoint theorem and its applications, Pac. J. Math., 5, 2, 285-309 (1955) · Zbl 0064.26004
[50] J. Wang, A.W.C. Fu, J. Cheng, Rectangle counting in large bipartite graphs, in: Proc. IEEE International Congress on Big Data, 2014, pp. 17-24.
[51] Wanless, I. M., A generalization of transversals for Latin squares, Electron. J. Combin., 9 (2002), R12 · Zbl 0993.05033
[52] Wanless, I. M., Atomic Latin squares based on cyclotomic orthomorphisms, Electron. J. Combin., 12 (2005), R22 · Zbl 1079.05016
[53] Wanless, I. M.; Ihrig, E. C., Symmetries that Latin squares inherit from \(1\)-factorizations, J. Combin. Des., 13, 157-172 (2005) · Zbl 1067.05061
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.