Constructing unlabelled lattices

DOI10.1016/J.JALGEBRA.2018.10.017MaRDI QIDQ2282992zbMATH OpenOpenAlexWikidataFDO

Authors Volker Gebhardt, Stephen Tawn

Publication date 27 December 2019

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.08255

zbMATH Keywords

enumerationorderly algorithmunlabelled lattice

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to combinatorics (05-04) Exact enumeration problems, generating functions (05A15) Combinatorics of partially ordered sets (06A07) Structure theory of lattices (06B05)

Abstract: We present an improved orderly algorithm for constructing all unlabelled lattices up to a given size, that is, an algorithm that constructs the minimal element of each isomorphism class relative to some total order. Our algorithm employs a stabiliser chain approach for cutting branches of the search space that cannot contain a minimal lattice; to make this work, we grow lattices by adding a new layer at a time, as opposed to adding one new element at a time, and we use a total order that is compatible with this modified strategy. The gain in speed is between one and two orders of magnitude. As an application, we compute the number of unlabelled lattices on 20 elements.

Recommendations

• Counting finite lattices.
• Generating modular lattices of up to 30 elements
• A fast incremental algorithm for building lattices
• A fast algorithm for building lattices
• The structure of finite distributive lattices.

Cites work

• Counting finite lattices.
• Endliche Verbände.
• Generating all finite modular lattices of a given size
• scientific article; zbMATH DE number 1261512 (Why is no real title available?)
• Isomorph-Free Exhaustive Generation
• Practical graph isomorphism. II.
• The art of computer programming. Vol. 4, Fasc. 0--4. Fasc. 0: Introduction to combinatorial algorithms and Boolean functions. Fasc. 1: Bitwise tricks \& techniques, binary decision diagrams. Fasc. 2: Generating all tuples and permutations. Fasc. 3: Genera
• The Asymptotic Number of Lattices
• The on-line encyclopedia of integer sequences

Cited in

(8)

• Exponential lower bounds of lattice counts by vertical sum and 2-sum
• Cartesian lattice counting by the vertical 2-sum
• Generating modular lattices of up to 30 elements
• Counting graded lattices of rank 3 that have few coatoms
• Basic retracts and counting of lattices
• Counting of lattices containing up to four comparable reducible elements and having nullity up to three
• Counting of lattices containing up to 5 reducible elements and having nullity up to 3
• On distributive triads

Describes a project that uses

Uses Software

• nauty
• Traces
• OEIS

This page was built for publication: Constructing unlabelled lattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2282992)