Rust code for manipulating finite partially ordered sets.
Finite posets are combinatorially intricate structures. They can be represented computationally in different way, and the chosen representation affects, some times quite strongly, the computational complexity of algorithms that compute, create, or manipulate posets. The aim of this repository is to provide code to support different representations of finite posets, together with implementations of algorithms for each form of presentation, and functionality to convert between the different forms.
Broadly speaking, there are three (somehwat overlapping) activities related to posets.
There are numerous classes of posets that are described by one, or more, simple parameters. For instance, a chain is a poset in which all elements are comparable. A chain is determined (up to isomorphism) by its number of elements. Similarly, an anti-chain (where no two distinct elements are comparable), is also characterised by its number of elements. Other classes include various free constructions (e.g., the free distributive lattice on
A given poset can give rise to other posets by directly manipulating it. For instance, forming subposets of a given poset, or adjoining a bottom or top (or both) element to an existing poset.
A poset has various invariants, such as whether it has a bottom element, the number of its minimal elements, its width, its Mobius function, etc.
By exhibiting functionality across different representations for all three main activities revolving around posets, we aim to provide:
- A playground for working with posets in an exploratory fashion.
- A robust framework to test algorithms that rely on posets.
- A reliable computational engine to be used in applications.
This list is not exhaustive!
-
FinitePosets - providing some poset functionality for Julia.
-
Macaulay2 a package providing poset functionality for algebra and geometry (journal publication article).