SimplePosets

This module defines a SimplePoset type for Julia. A poset is a pair (X,<) where X is a set of elements and < is a relation on X that is irreflexive, antisymmetric, and transitive.

Basic constructor

Use SimplePoset(T) to create a new SimplePoset with elements having type T (which defaults to Any).

Add/delete elements/relations

Elements and relations can be added to or deleted from a poset using these functions:

• add!(P,x) adds a new element x to the ground set of P.
• add!(P,x,y) inserts the relation x<y into P. If one (or both) of x and y is not in P, it is added as well.
• delete!(P,x) deletes element x from this poset.
• delete!(P,x,y) delete the relation x<y from P and for any z with x < z < y, also delete x<z and z<y.

More detail on element/relation addition/deletion can be found in the document addition-deletion.pdf found in the doc folder.

Basic inspection

• elements(P) returns a list of the elements in P
• card(P) returns the cardinality of P (number of elements).
• relations(P) returns a list of all pairs (x,y) with x<y in this poset.
• incomparables(P) returns a list of all incomparable pairs. If (x,y) is listed, we do not also list (y,x).
• has(P,x) determine if x is an element of P.
• has(P,x,y) determine if x<y in the poset P. Note: Calling has(P,x,x) for an element x of this poset returns false. All our methods concern the strict relation <.
• above(P,x) returns a list of all elements above x in P.
• below(P,x) returns a list of all elements below x in P.
• interval(P,x,y) returns a list of all elements z that satisfy x<z<y.
• maximals(P) returns a list of the maximal elements of P.
• minimals(P) returns a list of the minimal elements of P.

The following functions are not likely to be called by the casual user.

• check(P) returns true provided the internal data structures of P are valid and false otherwise. Note: There should be no reason to use this function if the poset is created and manipulated by the functions provided in this module.

• hash(P) computes a hash value for the poset. This enables SimplePoset objects to serve as keys in dictionaries, and so forth.

• eltype(P) returns the datatype of the elements in this poset. For example:

  julia> P = BooleanLattice(3);
  
  julia> eltype(P)
  SimplePoset{String} (8 elements)

Constructors

• Antichain(n) creates an antichain with elements 1:n. The function IntPoset(n) is a synonym.
• Antichain(list) creates an antichain with elements drawn from list, a one-dimensional array.
• BooleanLattice(n) creates the subsets of an n-set poset in which elements are named as n-long binary strings.
• Chain(n) creates a chain with elements 1:n in which 1<2<3<...<n.
• Chain(list) creates a chain with elements drawn from list (in that order) in.
• Divisors(n) creates the poset whose elements are the divisors of n ordered by divisibility.
• PartitionLattice(n) creates the poset whose elements are the partitions of {1,2,...,n} ordered by refinement.
• RandomPoset(n,d) creates a random d-dimensional poset on n elements.
• SimplePoset(G::SimpleGraph) creates the vertex-edge poset of G.
• StandardExample(n) creates the canonical n-dimensional poset with 2n elements in two layers. The lower layer elements are named from -1 to -n and the upper layer from 1 to n. We have -i<j exactly when i!=j.

Operations

• inv(P) creates the inverse poset of P, i.e., we have x<y in P iff we have y<x in inv(P). We can use P' as a synonym for inv(P).

• intersect(P,Q) creates the intersection of the two posets (which must be of the same element type). Typically the two posets have the same elements, but this is not necessary. The resulting poset's elements is the intersection of the two element sets, and relations in the result are those relations common to both P and Q.

• induce(P,A) forms the induced subposet of P using the elements in the set A.

• P*Q is the Cartesian product of the two posets (that may be of different types).

• P+Q is the disjoint union of two (or more) posets. The posets must all be of the same type. Each summand's elements is extended with an integer (starting at 1) corresponding to its position in the sum. That is, if x is an element of summand number i, then in the sum it becomes the element (x,i). For example:

  julia> P = Chain(2)+Chain(3)+Chain(4)
  SimplePoset{(Int64,Int64)} (9 elements)
  
  julia> elements(P)
  9-element Array{(Int64,Int64),1}:
   (1,1)
   (1,2)
   (1,3)
   (2,1)
   (2,2)
   (2,3)
   (3,2)
   (3,3)
   (4,3)

• stack(Plist...) creates a new poset from the ones in the argument list by stacking one atop the next. The first poset in the list is at the bottom. Element labeling is as in +.

• relabel(P,labels) is used to create a new poset in which the elements have new names (as given by the dictionary labels). Calling relabel(P) gives a new poset in which the new element names are the integers 1 through n. Here's an example:

  julia> P = Chain(3) + Chain(3)
  SimplePoset{(Int64,Int64)} (6 elements)
  
  julia> elements(P)
  6-element Array{(Int64,Int64),1}:
   (1,1)
   (1,2)
   (2,1)
   (2,2)
   (3,1)
   (3,2)
  
  julia> Q = relabel(P)
  SimplePoset{Int64} (6 elements)
  
  julia> elements(Q)
  6-element Array{Int64,1}:
   1
   2
   3
   4
   5
   6

Poset properties

• ComparabilityGraph(P) returns a SimpleGraph whose vertices are the elements of P and in which two distinct vertices are adjacent iff they are comparable in P.
• CoverDigraph(P) returns a directed graph whose vertices are the elements of P in which (x,y) is an edges provided both x<y in P and there is no z for which x<z<y. These are the edges that would appear in a Hasse diagram of P.
• mobius(P) creates the Mobius function for this poset (as a dictionary from pairs of elements to Int values).
• mobius_matrix(P) is the inverse of zeta_matrix(P).
• zeta(P) creates the zeta function for this poset (as a dictionary from pairs of elements to Int values). We have (x,y) ==> 1 provided x==y or x<y, and (x,y) ==> 0 otherwise.
• zeta_matrix(P) produces the zeta matrix. Order of elements is the same as produced by elements(P).
• height(P) returns the maximum size of a chain.

Linear extensions

• linear_extension(P) finds one linear extension of the poset (as an Array).
• random_linear_extension(P) returns a random linear extension. See the help message for more detail.
• all_linear_extensions(P) returns a Set containing all the linear extensions of the poset. This is a very expensive operation in both time and memory. It is memoized to make it more efficient, but the memory it uses is not freed after use.

julia> P = Divisors(12)
SimplePoset{Int64} (6 elements)

julia> linear_extension(P)'
1×6 LinearAlgebra.Adjoint{Int64,Array{Int64,1}}:
 1  2  3  4  6  12

julia> random_linear_extension(P)'
1×6 LinearAlgebra.Adjoint{Int64,Array{Int64,1}}:
 1  3  2  6  4  12

julia> collect(all_linear_extensions(P))
5-element Array{Array{Int64,1},1}:
 [1, 3, 2, 4, 6, 12]
 [1, 3, 2, 6, 4, 12]
 [1, 2, 3, 6, 4, 12]
 [1, 2, 3, 4, 6, 12]
 [1, 2, 4, 3, 6, 12]

Miscellaneous

Under the hood

A SimplePoset is a wrapper around a DirectedGraph object. The functions for creating and manipulating a SimplePoset ensure that the underlying digraph has directed edges (x,y) exactly for those pairs of elements with x<y.