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 elementx
to the ground set ofP
.add!(P,x,y)
inserts the relationx<y
intoP
. If one (or both) ofx
andy
is not inP
, it is added as well.delete!(P,x)
deletes elementx
from this poset.delete!(P,x,y)
delete the relationx<y
fromP
and for anyz
withx < z < y
, also deletex<z
andz<y
.
More detail on element/relation addition/deletion can be found in the
document additiondeletion.pdf
found in the doc
folder.
Basic inspection
elements(P)
returns a list of the elements inP
card(P)
returns the cardinality ofP
(number of elements).relations(P)
returns a list of all pairs(x,y)
withx<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 ifx
is an element ofP
.has(P,x,y)
determine ifx<y
in the posetP
. Note: Callinghas(P,x,x)
for an elementx
of this poset returnsfalse
. All our methods concern the strict relation<
.above(P,x)
returns a list of all elements abovex
inP
.below(P,x)
returns a list of all elements belowx
inP
.interval(P,x,y)
returns a list of all elementsz
that satisfyx<z<y
.maximals(P)
returns a list of the maximal elements ofP
.minimals(P)
returns a list of the minimal elements ofP
.
The following functions are not likely to be called by the casual user.

check(P)
returnstrue
provided the internal data structures ofP
are valid andfalse
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 enablesSimplePoset
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 elements1:n
. The functionIntPoset(n)
is a synonym.Antichain(list)
creates an antichain with elements drawn fromlist
, a onedimensional array.BooleanLattice(n)
creates the subsets of ann
set poset in which elements are named asn
long binary strings.Chain(n)
creates a chain with elements1:n
in which1<2<3<...<n
.Chain(list)
creates a chain with elements drawn fromlist
(in that order) in.Divisors(n)
creates the poset whose elements are the divisors ofn
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 randomd
dimensional poset onn
elements.SimplePoset(G::SimpleGraph)
creates the vertexedge poset ofG
.StandardExample(n)
creates the canonicaln
dimensional poset with2n
elements in two layers. The lower layer elements are named from1
ton
and the upper layer from1
ton
. We havei<j
exactly wheni!=j
.
Operations

inv(P)
creates the inverse poset ofP
, i.e., we havex<y
inP
iff we havey<x
ininv(P)
. We can useP'
as a synonym forinv(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 bothP
andQ
. 
induce(P,A)
forms the induced subposet ofP
using the elements in the setA
. 
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, ifx
is an element of summand numberi
, 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) 9element 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 dictionarylabels
). Callingrelabel(P)
gives a new poset in which the new element names are the integers1
throughn
. Here's an example:julia> P = Chain(3) + Chain(3) SimplePoset{(Int64,Int64)} (6 elements) julia> elements(P) 6element 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) 6element Array{Int64,1}: 1 2 3 4 5 6
Poset properties
ComparabilityGraph(P)
returns aSimpleGraph
whose vertices are the elements ofP
and in which two distinct vertices are adjacent iff they are comparable inP
.CoverDigraph(P)
returns a directed graph whose vertices are the elements ofP
in which(x,y)
is an edges provided bothx<y
inP
and there is noz
for whichx<z<y
. These are the edges that would appear in a Hasse diagram ofP
.mobius(P)
creates the Mobius function for this poset (as a dictionary from pairs of elements toInt
values).mobius_matrix(P)
is the inverse ofzeta_matrix(P)
.zeta(P)
creates the zeta function for this poset (as a dictionary from pairs of elements toInt
values). We have(x,y) ==> 1
providedx==y
orx<y
, and(x,y) ==> 0
otherwise.zeta_matrix(P)
produces the zeta matrix. Order of elements is the same as produced byelements(P)
.height(P)
returns the maximum size of a chain.
Linear extensions
linear_extension(P)
finds one linear extension of the poset (as anArray
).random_linear_extension(P)
returns a random linear extension. See the help message for more detail.all_linear_extensions(P)
returns aSet
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))
5element 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
.