This new (registered) package is at FinitePosets. Here is the README
“”"
This package deals with finite posets.
There are two types of posets. A “canonical poset” or CPoset is on the
elements 1:n where n=length(P). A Poset is on a given list of
elements which can be of any type. A Poset internally contains aCPoset
which works on the indices of the elements, which is more efficient than
working with the elements themselves. For efficiency, many functions work
on the internal CPoset by transforming their input to indices and their
output to elements.
A CPoset has the field:
-
hasse: a list representing the Hasse diagram of the poset: thei-th entry is the list of elements which cover (are immediate successors of)i, that is the list ofjsuch thati<jand there is noksuch thati<k<j.
The following is cached when computed to speed up subsequent computations:
-
incidence: a boolean matrix such thatincidence[i,j]==trueiffi<=j. This is sometimes called the ζ-matrix of the poset.
There are several ways of defining a poset. By entering the Hasse diagram:
julia> p=CPoset([[2,3],[4],[4],Int[]])
1<2,3<4
As seen above, p is shown as a list of covering maximal chains; elements
which are equivalent for the poset are printed together separated by
commas.
julia> length(p) # the number of elements of `p`
4
julia> incidence(p)
4×4 Matrix{Bool}:
1 1 1 1
0 1 0 1
0 0 1 1
0 0 0 1
julia> linear_extension(p) # a total order compatible with p
4-element Vector{Int64}:
1
2
3
4
A Poset is constructed from a CPoset and a list of elements
julia> P=Poset(p,[:a,:b,:c,:d])
a<b,c<d
julia> P.C # the CPoset attached to P
1<2,3<4
A convenient constructor for Posets takes a function representing
isless for the poset and the list of elements and constructs the poset
from the incidence matrix, computed by applying the function to each pair
of elements. For isless one can give either a function implementing <
or a function implementing ≤ (it is or-ed with == in any case).
julia> l=vec(collect(Iterators.product(1:2,1:2)))
4-element Vector{Tuple{Int64, Int64}}:
(1, 1)
(2, 1)
(1, 2)
(2, 2)
julia> P=Poset((x,y)->all(map(<=,x,y)),l)
(1, 1)<(2, 1),(1, 2)<(2, 2)
julia> eltype(P) # the type of the elements of P
Tuple{Int64, Int64}
julia> summary(P) # useful for big posets
"Poset{Tuple{Int64, Int64}} of length 4"
A poset can also be constructed from an incidence matrix so the last
example could also be entered as
julia> P=Poset(CPoset([all(map(<=,x,y)) for x in l, y in l]),l)
(1, 1)<(2, 1),(1, 2)<(2, 2)
Flexibility on printing a Poset is obtained by setting the function
show_element which takes as arguments an IO, the poset, and the index
of the element to print:
julia> P.show_element=(io,p,n)->join(io,p.elements[n],".");
julia> P
1.1<2.1,1.2<2.2
julia> delete!(P,:show_element); # back to default
The above fancy printing applies only when printing at the REPL or in pluto
or Jupyter. The default printing gives a form which can be input back in
Julia
julia> print(P)
Poset(CPoset([[2, 3], [4], [4], Int64[]]),[(1, 1), (2, 1), (1, 2), (2, 2)])
A poset can be specified by a list of tuples specifying order relations.
The transitive closure of these relations is computed, resulting in an
incidence matrix from which the poset is constructed. The elements of the
poset, if not specified separately, are all the elements that appear in the
tuples.
julia> Poset([(:a,:b),(:c,:d)])
a<b
c<d
julia> CPoset([(1,3),(2,5)]) # the CPoset is on 1:maximum(entries)
4
1<3
2<5
To get the order relation ≤ of the poset p between elements
i and j just call ≤(p,i,j).
julia> ≤(P,(1,1),(2,1))
true
julia> ≤(P.C,1,2) # the same
true
Intervals in a poset can be computed with strict or not bounds.
julia> interval(P,≤,(1,2)) # elements below (1,2)
2-element Vector{Tuple{Int64, Int64}}:
(1, 1)
(1, 2)
julia> interval(P,≥,(1,2)) # elements above (1,2)
2-element Vector{Tuple{Int64, Int64}}:
(1, 2)
(2, 2)
julia> interval(P,<,(1,2)) # elements strictly below (1,2)
1-element Vector{Tuple{Int64, Int64}}:
(1, 1)
julia> interval(P,≥,(2,1),≤,(2,2)) # elements between (2,1) and (2,2)
2-element Vector{Tuple{Int64, Int64}}:
(2, 1)
(2, 2)
julia> interval(P,>,(1,1),<,(2,2)) # elements strictly between
2-element Vector{Tuple{Int64, Int64}}:
(2, 1)
(1, 2)
julia> interval(P.C,>,1,<,4) # in terms of indices
2-element Vector{Int64}:
2
3
A sample of other functions available on posets:
julia> maximal_chains(P)
2-element Vector{Vector{Tuple{Int64, Int64}}}:
[(1, 1), (2, 1), (2, 2)]
[(1, 1), (1, 2), (2, 2)]
julia> height(P) # the length of a maximal chain
3
julia> moebiusmatrix(P)
4×4 Matrix{Int64}:
1 -1 -1 1
0 1 0 -1
0 0 1 -1
0 0 0 1
julia> minima(P)
1-element Vector{Tuple{Int64, Int64}}:
(1, 1)
julia> maxima(P)
1-element Vector{Tuple{Int64, Int64}}:
(2, 2)
julia> Q=CPoset(:chain,3)
1<2<3
julia> P1=Poset(Q) # transformed to a Poset with elements 1:3
1<2<3
julia> P⊕ P1 # the ordinal sum
(1, 1)<(2, 1),(1, 2)<(2, 2)<1<2<3
julia> P1*P1
(1, 1)<(2, 1)<(3, 1)<(3, 2)<(3, 3)
(1, 1)<(1, 2)<(2, 2)<(3, 2)
(2, 1)<(2, 2)
(1, 2)<(1, 3)<(2, 3)<(3, 3)
(2, 2)<(2, 3)
julia> P1⊗ P1 # the ordinal product
(1, 1)<(1, 2)<(1, 3)<(2, 1)<(2, 2)<(2, 3)<(3, 1)<(3, 2)<(3, 3)
Finally showpic(p) where p is a CPoset or a Poset gives a graphical
display of the poset (on Linux) provided you have the command dot and the
command display of imagemagick installed. It may work on MacOs and
Windows but I did not test it.
see the on-line help on
⊕, ⊗, +, *, chains, chainpoly, covering_chains, coxetermatrix, dual, hasse, height, incidence, induced, interval, isjoinlattice, ismeetlattice, linear_extension, maxima, maximal_chains, minima, moebius, moebiusmatrix, partition, showpic, transitive_closure
for more information
“”"