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.

Note

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 — Method

partially_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 elements

partially_ordered_set — Method

partially_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 elements

partially_ordered_set — Method

partially_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 elements

partially_ordered_set_from_inclusions — Method

partially_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 elements

face_poset — Method

face_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 elements

maximal_ranked_poset — Method

maximal_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 elements

lattice_of_flats — Method

lattice_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 elements

lattice_of_cyclic_flats — Method

lattice_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 elements

Auxiliary functions

rank — Method

rank(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)
3

comparability_graph — Method

comparability_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 — Method

maximal_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 — Method

order_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
 12

chain_polytope — Method

chain_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 8

graph — Method

graph(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 — Method

rank(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)))
2

node_ranks — Method

node_ranks(p::PartiallyOrderedSet)

Return a dictionary mapping each node index to its rank.

n_atoms — Method

n_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)
2

n_coatoms — Method

n_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)
3

atoms — Method

atoms(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 — Method

coatoms(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 — Method

least_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 — Method

greatest_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 — Method

element(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 — Method

elements(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))
11

elements_of_rank — Method

elements_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))
4

Visualization

visualize — Method

visualize(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.

Note

This will always show the greatest and least elements even if it does not correspond to an element of the partially ordered set.