×

Bounds on the number of autotopisms and subsquares of a Latin square. (English) Zbl 1299.05028

In this paper the authors consider two extremal questions about a Latin square \(L\) of order \(n\): (1) What is the maximum value of \(I_k(L)\) (the number of \(k\times k\) subsquares of \(L\)), and (2) what is the maximum cardinality of the group of autotopisms of L (denoted \(\text{Atp}(L)\))? Regarding the first question, the authors show that \(I_k(L)\leq n^{\Theta (\log k)}\), which is a substantial improvement on the bound \(I_k(L)\leq n^{\Theta (\sqrt{k})}\) given by J. M. Browning et al. [Commentat. Math. Univ. Carol. 51, No. 2, 175–184 (2010; Zbl 1224.05061)]. For the second question, the authors show that \(| \text{Atp}(L)| \leq n^2 \prod_{t=1}^{\lfloor \log _2 n\rfloor}(n-2^{t-1})\). Proof techniques for this theorem bear similarity to those used by G. L. Miller [in: Proceedings of the 10th annual ACM symposium on theory of computing, STOC ’78, San Diego, CA, USA, May 1–3, 1978. New York, NY: Association for Computing Machinery. 51–58 (1978; Zbl 1282.68192)]. This result leads to asymptotic formulas concerning prime power divisors of \(R_n\), the number of reduced Latin squares of order \(n\). For example, if \(p\) is prime and \(\omega _p (n)\) denotes the largest integer such that \(p^{\omega _p (n)}\) divides \(R_n\), then \(\omega _p (n)\geq \frac{n}{p-1}-O(\log ^2 n)\).

MSC:

05B15 Orthogonal arrays, Latin squares, Room squares
20D45 Automorphisms of abstract finite groups
20N05 Loops, quasigroups

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Alter: How many Latin squares are there?, Amer. Math. Monthly82 (1975), 632-634. · Zbl 0302.05014 · doi:10.2307/2319697
[2] R. A. Bailey: Latin squares with highly transitive automorphism groups, J. Aust. Math. Soc.33 (1982), 18-22. · Zbl 0496.05011 · doi:10.1017/S1446788700017560
[3] S. R. Blackburn, P. M. Neumann and G. Venkataraman: Enumeration of finite groups, Cambridge Tracts in Mathematics 173, Cambridge University Press, 2007. · Zbl 1141.20001 · doi:10.1017/CBO9780511542756
[4] J. Browning, P. Vojtěchovský and I. M. Wanless: Overlapping Latin subsquares and full products, Comment. Math. Univ. Carolin.51 (2010), 175-184. · Zbl 1224.05061
[5] P. J. Cameron: Research problems from the BCC22, Discrete Math.13 (2011), 1074-1083. · Zbl 1325.05002 · doi:10.1016/j.disc.2011.02.024
[6] N. J. Cavenagh, C. Greenhill, and I. M. Wanless: The cycle structure of two rows in a random Latin square, Random Structures Algorithms33 (2008), 286-309. · Zbl 1202.05015 · doi:10.1002/rsa.20216
[7] P. M. Cohn: Basic algebra: groups, rings, and fields, Springer, 2003. · Zbl 1003.00001
[8] K. Heinrich and W. D. Wallis: The maximum number of intercalates in a Latin square, Lecture Notes in Math.884, Springer, 1981, 221-233. · Zbl 0475.05014 · doi:10.1007/BFb0091822
[9] A. Hulpke, P. Kaski, and P. R. J. Östergård: The number of Latin squares of order 11, Math. Comp.80 (2011), 1197-1219. · Zbl 1210.05017 · doi:10.1090/S0025-5718-2010-02420-2
[10] D. Kotlar: Parity types, cycle structures and autotopisms of Latin squares, Electron. J. Combin.19(3) (2012), P10. · Zbl 1253.05048
[11] B. Maenhaut, I. M. Wanless, and B. S. Webb: Subsquare-free Latin squares of odd order, European J. Combin.28 (2007), 322-336. · Zbl 1109.05028 · doi:10.1016/j.ejc.2005.07.002
[12] B. D. McKay, A. Meynert, and W. Myrvold: Small Latin squares, quasigroups, and loops, J. Combin. Des.15 (2007), 98-119. · Zbl 1112.05018 · doi:10.1002/jcd.20105
[13] B. D. McKay and I. M. Wanless: Most Latin squares have many subsquares, J. Combin. Theory Ser. A86 (1999), 323-347. · Zbl 0948.05014 · doi:10.1006/jcta.1998.2947
[14] B. D. McKay and I. M. Wanless: On the number of Latin squares: Ann. Comb.9 (2005), 335-344. · Zbl 1073.05013 · doi:10.1007/s00026-005-0261-7
[15] B. D. McKay, I. M. Wanless and X. Zhang: The order of automorphisms of quasigroups, preprint. · Zbl 1327.05043
[16] Miller, G. L., On the nlog n isomorphism technique: A preliminary report, 51-58 (1978) · Zbl 1282.68192 · doi:10.1145/800133.804331
[17] N. J. A. Sloane: The on-line encyclopedia of integer sequences. http://oeis.org/[oeis.org]. · Zbl 1274.11001
[18] D. S. Stones: The parity of the number of quasigroups, Discrete Math.21 (2010), 3033-3039. · Zbl 1231.05037 · doi:10.1016/j.disc.2010.06.027
[19] D. S. Stones: On the Number of Latin Rectangles, PhD thesis, Monash University, 2010. http://arrow.monash.edu.au/hdl/1959.1/167114. · Zbl 1200.05041
[20] D. S. Stones: The many formulae for the number of Latin rectangles, Electron. J. Combin.17 (2010), A1. · Zbl 1193.05042
[21] D. S. Stones, P. Vojtěchovský and I. M. Wanless: Cycle structure of autotopisms of quasigroups and Latin squares, J. Combin. Designs20 (2012), 227-263. · Zbl 1248.05023 · doi:10.1002/jcd.20309
[22] D. S. Stones and I. M. Wanless: Compound orthomorphisms of the cyclic group, Finite Fields Appl.16 (2010), 277-289. · Zbl 1200.05013 · doi:10.1016/j.ffa.2010.04.001
[23] D. S. Stones and I. M. Wanless: A Congruence Connecting Latin Rectangles and Partial Orthomorphisms, Ann. Comb.16 (2012), 349-365. · Zbl 1256.05030 · doi:10.1007/s00026-012-0137-6
[24] 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 · doi:10.1016/j.jcta.2009.03.019
[25] 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
[26] G. H. J. van Rees: Subsquares and transversals in Latin squares, Ars Combin.29 (1990), 193-204. · Zbl 0718.05014
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.