Abstract
An algorithm is presented for generating finite modular, semimodular, graded, and geometric lattices up to isomorphism. Isomorphic copies are avoided using a combination of the general-purpose graph-isomorphism tool nauty and some optimizations that handle simple cases directly. For modular and semimodular lattices, the algorithm prunes the search tree much earlier than the method of Jipsen and Lawless, leading to a speedup of several orders of magnitude. With this new algorithm modular lattices are counted up to 30 elements, semimodular lattices up to 25 elements, graded lattices up to 21 elements, and geometric lattices up to 34 elements. Some statistics are also provided on the typical shape of small lattices of these types.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Brinkmann, G., McKay, B.D.: Posets on up to 16 points. Order 19(2), 147–179 (2002)
Erné, M., Heitzig, J., Reinhold, J.: On the number of distributive lattices. Electron. J. Comb. 9(1), #R24 (2002)
Gebhardt, V., Tawn, S.: Constructing unlabelled lattices. ArXiv e-prints (2016)
Heitzig, J., Reinhold, J.: Counting finite lattices. Algebra Univers. 48(1), 43–53 (2002)
Jipsen, P., Lawless, N.: Generating all finite modular lattices of a given size. Algebra Univers. 74(3), 253–264 (2015)
Kleitman, D.J., Winston, K.J.: The asymptotic number of lattices. Ann. Discrete Math. 6, 243–249 (1980)
Kohonen, J.: Lists of finite lattices (graded, n = 21 elements, c = 2 coatoms). https://b2share.eudat.eu/records/dda62689eb724e9ea6a40b9cd280cfed
Kohonen, J.: Listsoffinitelattices(graded,n = 21elements,c>2coatoms).https://b2share.eudat.eu/records/9fa46c3cc366477cb3894ea14a83f7de
Kohonen, J.: Listsoffinitelattices(modular,semimodular,gradedandgeometric).https://b2share.eudat.eu/records/dbb096da4e364b5e9e37b982431f41de
Malandro, M.: Theunlabeledlatticeson≤15nodes.http://www.shsu.edu/mem037/Lattices.html (2013)
McKay, B.D., Piperno, A.: Practicalgraphisomorphism,II. J.Symb.Comput. 60, 94–112 (2014)
McKay, B.D., Piperno, A.: NautyandTracesUser’sGuide(Version2.6).http://pallini.di.uniroma1.it/Guide.html (2016)
Sloane, N.J.A.: Theon-lineencyclopediaofintegersequences.https://oeis.org
Stanley, R.P.: EnumerativeCombinatorics, vol. 1. Wadsworth&Brooks, Belmont (1986)
Acknowledgements
The author wants to thank Nathan Lawless for providing the program code described in [5], and the anonymous referee for several valuable remarks.
The research that led to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement 338077 “Theory and Practice of Advanced Search and Enumeration.”
Computational resources were provided by CSC – IT Center for Science, Finland, and the Aalto Science-IT project.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kohonen, J. Generating Modular Lattices of up to 30 Elements. Order 36, 423–435 (2019). https://doi.org/10.1007/s11083-018-9475-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-018-9475-2