The number of Latin squares of order 11
HTML articles powered by AMS MathViewer
- by Alexander Hulpke, Petteri Kaski and Patric R. J. Östergård PDF
- Math. Comp. 80 (2011), 1197-1219 Request permission
Abstract:
Constructive and nonconstructive techniques are employed to enumerate Latin squares and related objects. It is established that there are (i) $2036029552582883134196099$ main classes of Latin squares of order $11$$;$ (ii) $6108088657705958932053657$ isomorphism classes of one-factorizations of $K_{11,11}$$;$ (iii) $12216177315369229261482540$ isotopy classes of Latin squares of order $11$$;$ (iv) $1478157455158044452849321016$ isomorphism classes of loops of order $11$$;$ and (v) $19464657391668924966791023043937578299025$ isomorphism classes of quasigroups of order $11$. The enumeration is constructive for the $1151666641$ main classes with an autoparatopy group of order at least $3$.References
- Charles J. Colbourn and Jeffrey H. Dinitz (eds.), Handbook of combinatorial designs, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2007. MR 2246267
- Jeffrey H. Dinitz, David K. Garnick, and Brendan D. McKay, There are $526,915,620$ nonisomorphic one-factorizations of $K_{12}$, J. Combin. Des. 2 (1994), no. 4, 273–285. MR 1276829, DOI 10.1002/jcd.3180020406
- The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.4.12; 2008. (http://www.gap-system.org)
- GNU Multiple Precision Arithmetic Library, Version 4.2.1. (http://gmplib.org/)
- Petteri Kaski, Isomorph-free exhaustive generation of designs with prescribed groups of automorphisms, SIAM J. Discrete Math. 19 (2005), no. 3, 664–690. MR 2191287, DOI 10.1137/S0895480104444788
- Petteri Kaski and Patric R. J. Östergård, Classification algorithms for codes and designs, Algorithms and Computation in Mathematics, vol. 15, Springer-Verlag, Berlin, 2006. With 1 DVD-ROM (Windows, Macintosh and UNIX). MR 2192256
- Petteri Kaski and Patric R. J. Östergård, There are $1,132,835,421,602,062,347$ nonisomorphic one-factorizations of $K_{14}$, J. Combin. Des. 17 (2009), no. 2, 147–159. MR 2489440, DOI 10.1002/jcd.20188
- P. Kaski and O. Pottonen, libexact User’s Guide, Version 1.0, HIIT Technical Reports 2008-1, Helsinki Institute for Information Technology HIIT, 2008.
- G. Kolesova, C. W. H. Lam, and L. Thiel, On the number of $8\times 8$ Latin squares, J. Combin. Theory Ser. A 54 (1990), no. 1, 143–148. MR 1051788, DOI 10.1016/0097-3165(90)90015-O
- B.D. McKay, nauty User’s Guide (Version $1.5$), Technical Report TR-CS-90-02, Computer Science Department, Australian National University, Canberra, 1990.
- B.D. McKay, autoson – A Distributed Batch System for UNIX Workstation Networks (Version 1.3), Technical Report TR-CS-96-03, Computer Science Department, Australian National University, 1996.
- Brendan D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998), no. 2, 306–324. MR 1606516, DOI 10.1006/jagm.1997.0898
- Brendan D. McKay, Alison Meynert, and Wendy Myrvold, Small Latin squares, quasigroups, and loops, J. Combin. Des. 15 (2007), no. 2, 98–119. MR 2291523, DOI 10.1002/jcd.20105
- Brendan D. McKay and Ian M. Wanless, On the number of Latin squares, Ann. Comb. 9 (2005), no. 3, 335–344. MR 2176596, DOI 10.1007/s00026-005-0261-7
- H. W. Norton, The 7 x 7 squares, Ann. Eugenics 9 (1939), 269–307. MR 1220
- Joseph J. Rotman, An introduction to the theory of groups, 4th ed., Graduate Texts in Mathematics, vol. 148, Springer-Verlag, New York, 1995. MR 1307623, DOI 10.1007/978-1-4612-4176-8
- Albert Sade, An omission in Norton’s list of $7\times 7$ squares, Ann. Math. Statistics 22 (1951), 306–307. MR 40254, DOI 10.1214/aoms/1177729654
- Douglas S. Stones and Ian M. Wanless, Divisors of the number of Latin rectangles, J. Combin. Theory Ser. A 117 (2010), no. 2, 204–215. MR 2557890, DOI 10.1016/j.jcta.2009.03.019
- Douglas B. West, Introduction to graph theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996. MR 1367739
Additional Information
- Alexander Hulpke
- Affiliation: Department of Mathematics, Colorado State University, 1874 Campus Delivery, Fort Collins, Colorado 80523-1874
- MR Author ID: 600556
- ORCID: 0000-0002-5210-6283
- Email: hulpke@math.colostate.edu
- Petteri Kaski
- Affiliation: Helsinki Institute for Information Technology HIIT, University of Helsinki, Department of Computer Science, P.O. Box 68, 00014 University of Helsinki, Finland
- Email: petteri.kaski@cs.helsinki.fi
- Patric R. J. Östergård
- Affiliation: Department of Communications and Networking, Aalto University, P.O. Box 13000, 00076 Aalto, Finland
- Email: patric.ostergard@tkk.fi
- Received by editor(s): September 18, 2009
- Received by editor(s) in revised form: February 4, 2010
- Published electronically: September 13, 2010
- © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 80 (2011), 1197-1219
- MSC (2010): Primary 05B15, 05A15, 05C30, 05C70
- DOI: https://doi.org/10.1090/S0025-5718-2010-02420-2
- MathSciNet review: 2772119