Constructing unlabelled lattices

Volker Gebhardt, Stephen Tawn

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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment