Posets

Partially ordered sets for Julia based on Graphs. See HasseDiagrams for functions to draw posets.

Introduction: Partially Ordered Sets

A partially ordered set, or poset for short, is a pair $(V,\prec)$ where $V$ is a set and $\prec$ is a binary relation on $V$ that is

• irreflexive (for all $v \in V$, it is never the case that $v \prec v$),
• antisymmetric (for all $v,w \in V$, we never have both $v \prec w$ and $w \prec v$), and
• transitive (for all $u,v,w \in V$, if $u \prec v$ and $v \prec w$ then $u \prec w$).

Posets are naturally represented as transitively closed, directed, acyclic graphs. This is how this module implements posets using the DiGraph type in Graphs.

The design philosophy for this module is modeled exactly on Graphs. In particular, the vertex set of a poset is necessarily of the form {1,2,...,n}.

Basics

Constructing new posets

Create a new poset with no elements using Poset() or a poset with a specified number of elements with Poset(n).

Given a poset p, use Poset(p) to create an independent copy of p.

Given a directed graph d, use Poset(d) to create a new poset from the transitive closure of d. An error is thrown if d has cycles. (Self loops in d are ignored.)

Given a square matrix A, create a poset in which i < j exactly when the i,j-entry of A is nonzero. Diagonal entries are ignored. If this matrix would create a cycle, an error is thrown.

Adding vertices (elements)

For consistency with Graph, we call the elements of a Poset vertices and the functions add_vertex! and add_vertices! work exactly as in the Graphs module.

julia> using Posets

julia> p = Poset()
{0, 0} Int64 poset

julia> add_vertex!(p)
true

julia> add_vertices!(p,5)
5

julia> p
{6, 0} Int64 poset

Use nv(p) to return the number of elements (vertices) in p.

Adding a relation

To add a relation to a poset, use add_relation!. This returns true when successful.

julia> p = Poset(4)
{4, 0} Int64 poset

julia> add_relation!(p,1,2)
true

julia> add_relation!(p,2,3)
true

julia> add_relation!(p,3,1)
false

Let's look at this carefully to understand why the third call to add_relation! does not succeed:

• The first call to add_relation! causes the relation 1 < 2 to hold in p.
• The second call to add_relation! causes the relation 2 < 3 to be added to p. Given that 1 < 2 and 2 < 3, by transitivity we automatically have 1 < 3 in p.
• Therefore, we cannot add 3 < 1 as a relation to this poset as that would violate antisymmetry.

The add_relation! function may also be called as add_relation!(p, (a,b)) or add_relation!(p, a => b). Both are equivalent to add_relations(p, a, b).

Adding multiple relations (Danger!)

The addition of a relation to a poset can be somewhat slow. Each addition involves error checking and calculations to ensure the integrity of the underlying data structure. See the Implementation section at the end of this document. Adding a list of relations one at a time can be inefficient, but it is safe. We also provide the function add_relations! (plural) that is more efficient, but can cause serious problems.

To underscore the risk, this function is not exported, but needs to be invoked as Posets.add_relations!(p, rlist) where rlist is a list of either tuples (a,b) or pairs a => b.

Here is a good application of this function (although using chain(10) is safer):

julia> p = Poset(10)
{10, 0} Int64 poset

julia> rlist = ((i,i+1) for i=1:9)
Base.Generator{UnitRange{Int64}, var"#13#14"}(var"#13#14"(), 1:9)

julia> Posets.add_relations!(p, rlist)

julia> p == chain(10)
true

Here is what happens with misuse:

julia> p = Poset(5)
{5, 0} Int64 poset

julia> rlist = [ 1=>2, 2=>3, 3=>1 ]
3-element Vector{Pair{Int64, Int64}}:
 1 => 2
 2 => 3
 3 => 1

julia> Posets.add_relations!(p, rlist)
ERROR: This poset has been become corrupted!

Removing an element

The function rem_vertex! behaves exactly as in Graphs. It removes the given vertex from the poset. For example:

julia> p = Poset(5)
{5, 0} Int64 poset

julia> add_relation!(p,1,5)
true

julia> rem_vertex!(p,2)
true

julia> has_relation(p,1,2)
true

When element 2 is removed from p, element 5 takes its place. Because of this renumbering, we have some unexpected behavior:

julia> p = subset_lattice(4)
{16, 65} Int64 poset

julia> q = Poset(p)   # make a copy of p
{16, 65} Int64 poset

julia> rem_vertex!(q, 9)
true

julia> q
{15, 57} Int64 poset

julia> q ⊆ p
false

julia> maximals(p) |> collect
1-element Vector{Int64}:
 16

julia> maximals(q) |> collect
1-element Vector{Int64}:
 9

One might expect that deleting a vertex from a poset results in a poset that is a subset of the original. However, when vertex 9 was removed from (a copy of) p, the vertex 16 is relabeled 9. Hence vertex 9 in p is not maximal, but it is maximal in q.

For a more extensive explanation, see poset-deletion.pdf in the delete-doc folder.

Removing a relation

Removing relations from a poset is accomplished with rem_relation!(p,a,b). Assuming a<b in p, this deletes the relation a<b from p, but also deletes all relations a<x and x<b for vertices x that lie between a and b.

julia> p = chain(5)
{5, 10} Int64 poset

julia> rem_relation!(p, 2, 4)
true

julia> collect(relations(p))
8-element Vector{Relation{Int64}}:
 Relation 1 < 2
 Relation 1 < 3
 Relation 1 < 4
 Relation 1 < 5
 Relation 2 < 4
 Relation 2 < 5
 Relation 3 < 5
 Relation 4 < 5

Note that relations 2<3 and 3<4 have been removed.

For a more extensive explanation, see poset-deletion.pdf in the delete-doc folder.

poset_builder function

Posets are a collection of objects and a $\prec$ relation. The poset_builder function takes a list of objects and a function the determines if they obey a $\prec$ relation, and returns the resulting poset.

The function is invoked as poset_builder(list, comp_func) where

• list is a list (vector) of objects and
• comp_func is a function that takes a pair of objects and returns true if they satisfy a $\prec$ relation.

For example, suppose we want to construct a poset consisting of the integers 1 to 100 which $a \prec b$ provided $a$ is a divisor of $b$. Here is how to do that:

julia> nums = collect(1:100);

julia> divs(a,b) = mod(b,a)==0    # return true if a divides b
divs (generic function with 1 method)

julia> p = poset_builder(nums, divs)
{100, 382} Int64 poset

The elements that cover 1 are the primes less than 100:

julia> [ x for x in 1:100 if covered_by(p,1,x) ]
25-element Vector{Int64}:
  2
  3
  5
  7
 11
 13
 17
 19
  ⋮
 67
 71
 73
 79
 83
 89
 97

Inspection

Vertices

Use nv(p) to return the number of vertices in the poset p. As in Graphs, the elements of the poset are integers from 1 to n.

Use in(a, p) [or a ∈ p] to determine if a is an element of p. This is equivalent to 1 <= a <= nv(p).

Relations

There are three ways to check if elements are related in a poset.

First, to see if 1 < 3 in p we use the has_relation function:

julia> has_relation(p,1,3)
true

Second, the syntax p(a,b) is equivalent to has_relation(p,a,b):

julia> p(1,3)
true

julia> p(3,1)
false

There is a third way to determine the relation between elements a and b in a poset p. Instead of has_relation(p,a,b) or p(a,b) we may use this instead: p[a] < p[b].

julia> has_relation(p,1,3)
true

julia> p[1] < p[3]
true

julia> p[3] < p[1]
false

The other comparison operators (<=, >, >=, ==, !=) works as expected.

julia> p[3] > p[1]
true

Neither has_relation(p,a,b) nor p(a,b) generate errors; they return false even if a or b are not elements of p.

julia> p(-2,9)
false

However, the expression p[a] < p[b] throws an error in either of these situations:

• Using the syntax p[a] if a is not an element of p.
• Trying to compare elements of different posets (even if the two posets are equal).

Comparability check

The functions are_comparable(p,a,b) and are_incomparable(p,a,b) behave as follows:

• are_comparable(p,a,b) returns true exactly when a and b are both in the poset, and one of the following is true: a<b, a==b, or a>b.
• are_incompable(p,a,b) returns true exactly when a and b are both in the poset, but none of the follower are true: a<b, a==b, or a>b.

Alternatively, use p[a] ⟂ p[b] to test if a and b are comparable, and use p[a] ∥ p[b] to test if a and b are incomparable.

Chain/antichain check

Given a list of elements vlist of a poset p:

• is_chain(p, vlist) returns true if the elements of vlist form a chain in p.
• is_antichain(p, vlist) returns true if the elements of vlist form an antichain in p.

Both return false if an element of vlist is not in p.

Counting/listing relations

Use nr to return the number of relations in the poset (this is analogous to ne in Graphs):

julia> nr(p)
3

The function relations returns an iterator for all the relations in a poset.

julia> p = chain(4)
{4, 6} Int64 poset

julia> collect(relations(p))
6-element Vector{Relation{Int64}}:
 Relation 1 < 2
 Relation 1 < 3
 Relation 1 < 4
 Relation 2 < 3
 Relation 2 < 4
 Relation 3 < 4

The functions src and dst return the lesser and greater elements of a relation, respectively:

julia> r = first(relations(p))
Relation 1 < 2

julia> src(r), dst(r)
(1, 2)

Subset

• issubset(p,q) (or p ⊆ q) returns true exactly when `nv(p) ≤ n