I'm planning out a project that involves lattices in the order theory sense of "lattice". I am assuming the number of vertices is known ahead of time.

Unfortunately I have only found resources related to lattices in a crystal or (undirected) graph embedding sense.

As such it would not be difficult to sample uniformly from Bernoulli variables indicating whether an edge exists and then reject those that do not match the structure of a lattice. This seems inefficient, and possibly non-uniform. Even more non-uniform but possibly more efficient would be to incrementally sample edges to build out the lattice.

I was reading in Deleu et al. 2022 that some improvements have been made in sampling directed acyclic graphs due to a general interest in structural learning. But this only gets as far as directed acyclic graphs in its current state. Maybe with considerably more work I could figure out how their method works and adapt it to lattices, but I am hoping something already exists for my use case.

For a really small number of vertices I could generate all of them and explicitly assign probabilities to them. While lattices are a subset of partial orders, OEIS A001035 is suggestive that this approach will fail for even modest problems. Rather, I need something that generates the lattice as part of the sampling.

Are there algorithms for uniformly-sampling lattices given that the number of vertices is known?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.