Partially Ordered Sets
Introduction
Partially ordered sets (a.k.a. posets) describe a finite set of elements with a partial ordering. All such objects in OSCAR need to have a rank function but it is not required that it is graded, i.e., adjacent nodes may have a rank difference larger than one.
Internally, posets are encoded in terms of their Hasse diagrams. The latter object is the directed graph whose nodes are the elements, and the oriented edges are given by the covering relations. Usually, the direction is from bottom to top; but there are exceptions, e.g., due to lazy evaluation.
Posets are static in the sense that they are born once, and then they remain immutable. This is different from Graphs.
Unique maximal and minimal elements are also required but in some cases this is realized by adding an extra artificial top node which covers all maximal elements and an artificial top node which is covered by all minimal elements. These nodes are suppressed in most functions except for the visualization.
Construction
partially_ordered_set — Methodpartially_ordered_set(covrels::Union{SMat, AbstractMatrix{<:IntegerUnion}})Construct a partially ordered set from covering relations covrels, given in the form of the adjacency matrix of a Hasse diagram. The covering relations must be given in topological order, i.e., covrels must be strictly upper triangular.
The construction only distinguishes zero coefficients (to indicate the absence) and nonzero coefficients (to indicate the presence of a covering relation).
Examples
julia> a2_adj_cov = [
0 1 1 0 0 0
0 0 0 1 1 0
0 0 0 1 1 0
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 0 0 0
];
julia> pa2 = partially_ordered_set(a2_adj_cov)
Partially ordered set of rank 3 on 6 elementspartially_ordered_set — Methodpartially_ordered_set(g::Graph{Directed})Construct a partially ordered set from a directed graph describing the Hasse diagram. The graph must be acyclic, edges must be directed from minimal to maximal elements.
If there is no unique minimal (maximal) element in the graph, an artificial least (greatest) element is added to the internal datastructure.
Examples
julia> g = graph_from_edges(Directed, [[2,1],[2,4],[1,3],[4,3]])
Directed graph with 4 nodes and the following edges:
(1, 3)(2, 1)(2, 4)(4, 3)
julia> pos = partially_ordered_set(g)
Partially ordered set of rank 2 on 4 elementspartially_ordered_set — Methodpartially_ordered_set(g::Graph{Directed}, node_ranks::Dict{Int,Int})Construct a partially ordered set from a directed graph describing the Hasse diagram. The graph must be acyclic. The dictionary node_ranks must give a valid rank for each node in the graph, strictly increasing from the minimal elements to maximal elements. The rank difference between two adjacent nodes may be larger than one.
If there is no unique minimal (maximal) element in the graph, an artificial least (greatest) element is added to the internal datastructure.
Examples
julia> g = graph_from_edges(Directed, [[2,1],[2,4],[1,3],[4,3],[3,6],[2,5],[5,6]])
Directed graph with 6 nodes and the following edges:
(1, 3)(2, 1)(2, 4)(2, 5)(3, 6)(4, 3)(5, 6)
julia> pos = partially_ordered_set(g, Dict(2=>0, 1=>1, 4=>2, 3=>3, 5=>2, 6=>4))
Partially ordered set of rank 4 on 6 elementspartially_ordered_set_from_inclusions — Methodpartially_ordered_set_from_inclusions(I::IncidenceMatrix)Construct an inclusion based partially ordered with rows of I as co-atoms. That is, the elements of the poset are the given sets, their intersections, and the union of all rows as greatest element.
Examples
julia> im = vertex_indices(facets(simplex(3)))
4×4 IncidenceMatrix
[1, 3, 4]
[1, 2, 4]
[1, 2, 3]
[2, 3, 4]
julia> partially_ordered_set_from_inclusions(im)
Partially ordered set of rank 4 on 16 elementsface_poset — Methodface_poset(p::Union{Polyhedron,Cone,PolyhedralFan,PolyhedralComplex,SimplicialComplex})Return a partially ordered set encoding the face inclusion relations of a polyhedral object.
Note that a polyhedron has the entire polyhedron as the greatest element while the normal fan does not have a greatest element.
Examples
julia> p = face_poset(dodecahedron())
Partially ordered set of rank 4 on 64 elements
julia> pf = face_poset(normal_fan(dodecahedron()))
Partially ordered set of rank 3 on 63 elementsmaximal_ranked_poset — Methodmaximal_ranked_poset(v::AbstractVector{Int})Return a maximal ranked partially ordered set with number of nodes per rank given in v, from bottom to top and excluding the least and greatest elements.
See [AFJ25] for details.
Examples
julia> pos = maximal_ranked_poset([2,4,3])
Partially ordered set of rank 4 on 11 elementslattice_of_flats — Methodlattice_of_flats(m::Matroid)Return the lattice of flats of a matroid.
Examples
julia> p = lattice_of_flats(fano_matroid())
Partially ordered set of rank 3 on 16 elementslattice_of_cyclic_flats — Methodlattice_of_cyclic_flats(m::Matroid)Return the lattice of cyclic flats of a matroid.
Examples
julia> p = lattice_of_cyclic_flats(fano_matroid())
Partially ordered set of rank 3 on 9 elementsAuxiliary functions
rank — Methodrank(p::PartiallyOrderedSet)Return the rank of a partially ordered set, i.e., the rank of a maximal element.
Examples
julia> p = face_poset(simplex(2))
Partially ordered set of rank 3 on 8 elements
julia> rank(p)
3comparability_graph — Methodcomparability_graph(pos::PartiallyOrderedSet)Return an undirected graph which has an edge for each pair of comparable elements in a partially ordered set.
Examples
julia> p = face_poset(simplex(2))
Partially ordered set of rank 3 on 8 elements
julia> comparability_graph(p)
Undirected graph with 8 nodes and the following edges:
(2, 1)(3, 1)(4, 1)(5, 1)(5, 2)(5, 4)(6, 1)(6, 2)(6, 3)(7, 1)(7, 3)(7, 4)(8, 1)(8, 2)(8, 3)(8, 4)(8, 5)(8, 6)(8, 7)maximal_chains — Methodmaximal_chains([::Type{Int},] p::PartiallyOrderedSet)Return the maximal chains of a partially ordered set as a vector of sets of elements (or node ids of Int is passed as first argument).
Examples
julia> pos = face_poset(cube(2))
Partially ordered set of rank 3 on 10 elements
julia> maximal_chains(Int, pos)
8-element Vector{Vector{Int64}}:
[1, 2, 6, 10]
[1, 2, 8, 10]
[1, 3, 7, 10]
[1, 3, 8, 10]
[1, 4, 6, 10]
[1, 4, 9, 10]
[1, 5, 7, 10]
[1, 5, 9, 10]
julia> pos = face_poset(simplex(2))
Partially ordered set of rank 3 on 8 elements
julia> maximal_chains(pos)
6-element Vector{Vector{Oscar.PartiallyOrderedSetElement}}:
[Poset element <Int64[]>, Poset element <[1]>, Poset element <[1, 3]>, Poset element <[1, 2, 3]>]
[Poset element <Int64[]>, Poset element <[1]>, Poset element <[1, 2]>, Poset element <[1, 2, 3]>]
[Poset element <Int64[]>, Poset element <[2]>, Poset element <[1, 2]>, Poset element <[1, 2, 3]>]
[Poset element <Int64[]>, Poset element <[2]>, Poset element <[2, 3]>, Poset element <[1, 2, 3]>]
[Poset element <Int64[]>, Poset element <[3]>, Poset element <[1, 3]>, Poset element <[1, 2, 3]>]
[Poset element <Int64[]>, Poset element <[3]>, Poset element <[2, 3]>, Poset element <[1, 2, 3]>]
order_polytope — Methodorder_polytope(p::PartiallyOrderedSet)Return the order polytope of a poset, see [Sta86].
Examples
julia> p = face_poset(simplex(2))
Partially ordered set of rank 3 on 8 elements
julia> op = order_polytope(p)
Polytope in ambient dimension 6
julia> f_vector(op)
6-element Vector{ZZRingElem}:
18
73
129
116
54
12chain_polytope — Methodchain_polytope(p::PartiallyOrderedSet)Return the chain polytope of a poset, see [Sta86].
Examples
julia> p = face_poset(cube(2))
Partially ordered set of rank 3 on 10 elements
julia> cp = chain_polytope(p)
Polytope in ambient dimension 8graph — Methodgraph(p::PartiallyOrderedSet)Return the directed graph of covering relations in a partially ordered set. To keep the node ids consistent this will include artificial top and bottom nodes.
Examples
julia> pos = maximal_ranked_poset([2,4,3])
Partially ordered set of rank 4 on 11 elements
julia> graph(pos)
Directed graph with 11 nodes and the following edges:
(1, 2)(1, 3)(2, 4)(2, 5)(2, 6)(2, 7)(3, 4)(3, 5)(3, 6)(3, 7)(4, 8)(4, 9)(4, 10)(5, 8)(5, 9)(5, 10)(6, 8)(6, 9)(6, 10)(7, 8)(7, 9)(7, 10)(8, 11)(9, 11)(10, 11)rank — Methodrank(pe::PartiallyOrderedSetElement)Return the rank of an element in a partially ordered set.
Examples
julia> p = face_poset(simplex(2))
Partially ordered set of rank 3 on 8 elements
julia> rank(greatest_element(p))
3
julia> rank(first(coatoms(p)))
2node_ranks — Methodnode_ranks(p::PartiallyOrderedSet)Return a dictionary mapping each node index to its rank.
n_atoms — Methodn_atoms(p::PartiallyOrderedSet)Return the number of atoms in a partially ordered set.
Examples
julia> pos = maximal_ranked_poset([2,4,3])
Partially ordered set of rank 4 on 11 elements
julia> n_atoms(pos)
2n_coatoms — Methodn_coatoms(p::PartiallyOrderedSet)Return the number of co-atoms in a partially ordered set.
Examples
julia> pos = maximal_ranked_poset([2,4,3])
Partially ordered set of rank 4 on 11 elements
julia> n_coatoms(pos)
3atoms — Methodatoms(p::PartiallyOrderedSet)Return the atoms in a partially ordered set.
Examples
julia> pos = maximal_ranked_poset([2,4,3])
Partially ordered set of rank 4 on 11 elements
julia> atoms(pos)
2-element Vector{Oscar.PartiallyOrderedSetElement}:
Poset element <[1]>
Poset element <[2]>coatoms — Methodcoatoms(p::PartiallyOrderedSet)Return the co-atoms in a partially ordered set.
Examples
julia> pos = maximal_ranked_poset([2,4,3])
Partially ordered set of rank 4 on 11 elements
julia> coatoms(pos)
3-element Vector{Oscar.PartiallyOrderedSetElement}:
Poset element <[7]>
Poset element <[8]>
Poset element <[9]>least_element — Methodleast_element(p::PartiallyOrderedSet)Return the unique minimal element in a partially ordered set, if it exists. Throws an error otherwise.
Examples
julia> pos = maximal_ranked_poset([2,4,3])
Partially ordered set of rank 4 on 11 elements
julia> least_element(pos)
Poset element <[0]>greatest_element — Methodgreatest_element(p::PartiallyOrderedSet)Return the unique maximal element in a partially ordered set, if it exists. Throws an error otherwise.
Examples
julia> pos = maximal_ranked_poset([2,4,3])
Partially ordered set of rank 4 on 11 elements
julia> greatest_element(pos)
Poset element <[10]>element — Methodelement(p::PartiallyOrderedSet, i::Int)Return the element in a partially ordered set with give node id.
Examples
julia> fl = face_poset(cube(2))
Partially ordered set of rank 3 on 10 elements
julia> element(fl,7)
Poset element <[2, 4]>elements — Methodelements(p::PartiallyOrderedSet)Return all elements in a partially ordered set.
Examples
julia> pos = maximal_ranked_poset([2,4,3])
Partially ordered set of rank 4 on 11 elements
julia> length(elements(pos))
11elements_of_rank — Methodelements_of_rank(p::PartiallyOrderedSet, rk::Int)Return the elements in a partially ordered set with a given rank.
Examples
julia> pos = maximal_ranked_poset([2,4,3])
Partially ordered set of rank 4 on 11 elements
julia> length(elements_of_rank(pos, 2))
4Visualization
visualize — Methodvisualize(p::PartiallyOrderedSet; AtomLabels=[], filename=nothing)Visualize a partially ordered set. The labels will be either the ids from the original input data or integer sets when the poset was created from inclusion relations. For inclusion based partially ordered sets the keyword AtomLabels can be used to specify a vector of strings with one label per atom to override the default 1:n_atoms(p) labeling. The labels of the least and greatest elements are not shown. The filename keyword argument allows writing TikZ visualization code to filename.