The Posets Package
Help Texts for the Vanilla Edition of posets 2.4
For a detailed introduction to the package, see
A Maple Package for Posets (PDF).
After loading the vanilla edition of posets, each package function may be
accessed using the calling sequence posets[functionname](arguments). In
order to use the abbreviated form functionname(arguments), run the command
'withposets()'. If there is a conflict between the names of one of the
package functions and a previously assigned name, a warning is printed.
To use the abbreviated form for a subset of the procedures in the package
(e.g., to avoid conflicts), run the command 'withposets(name1,name2,...)'.
The functions &u, &+, and &* are neutral operators for disjoint union,
ordinal sum, and Cartesian product. For general information on neutral
operators, see the Maple help text for 'neutral'.
This document provides help texts for each of the functions in posets:
- antichains - list/count antichains in a partially ordered set
- atomic - test whether a lattice is atomic
- autgroup - automorphism group of a poset (or directed graph)
- canon - canonically relabel a poset (or directed graph)
- chain - total order of specified length
- chains - list/count chains in a partially ordered set
- char_poly - characteristic polynomial of a (graded) poset
- closure - transitive closure of an acyclic digraph
- connected - connected components and poset connectivity test
- covers - covering relation of an acyclic digraph
- &u - disjoint union of posets
- distributive - test distributivity of lattices
- dual - dual of a poset (or directed graph)
- eulerian - test whether a poset is Eulerian
- extensions - linear extensions of a poset (or acyclic digraph)
- filter - filtration of a poset (or directed graph)
- flag_f - flag f-polynomial of a bounded, ranked poset
- flag_h - flag h-polynomial of a bounded, ranked poset
- f_poly - f-polynomial of a bounded poset
- h_poly - h-polynomial of a bounded poset
- ideals - list/count order ideals in a partially ordered set
- isom - test posets (or directed graphs) for isomorphism
- J - lattice of order ideals of a poset
- lattice - test whether a poset is a lattice or semi-lattice
- Lattices - list nonisomorphic lattices
- meet - compute meets in lattices, maximal lower bounds in posets
- mobius - Mobius function of a poset
- modular - test modularity and semi-modularity of lattices
- omega - order polynomial of a poset
- &+ - ordinal sum of posets
- plot_poset - plot posets (or acyclic directed graphs)
- Posets - list nonisomorphic posets
- &* - direct product of posets
- rand_poset - random poset generator
- ranked - test whether a poset is ranked
- rm_isom - remove isomorphic copies from a list of posets
- strongcomps - strongly connected components of a digraph
- subinterval - extract a subinterval from a poset
- subposet - extract an induced subposet from a poset
- W - W-polynomial of a poset
- zeta - zeta polynomial of a poset
FUNCTION: antichains - list/count antichains in a partially ordered set
CALLING SEQUENCE: antichains(P,<option>);
antichains(P,n,<option>);
antichains(P,X,<option>);
PARAMETERS: P = a poset
X = a set (the vertex set); or, a linear extension of P
n = a positive integer (the number of vertices)
<option> = at most one of the following:
(1) a range, such as 2..7
(2) the name 'max'
(3) a variable name, such as q
SYNOPSIS:
Let P be a poset with vertex set X. An antichain in P is a subset A
of X such that no pair x,y in A satisfies x < y in P. The number of
antichains in P equals the number of order ideals of P.
antichains(P,X) returns a list of all antichains in the poset P.
antichains(P,n) does the same, if the vertex set of P is {1,2,...,n}.
antichains(P) does the same, assuming that P has no isolated vertices.
The antichains are listed in a lexicographic order so that antichain A
precedes antichain B if B contains the "last" vertex of the symmetric
difference of A and B. Here, "last" is determined by some linear
extension of P; i.e., a linear ordering of X such that if x < y in P,
then x precedes y in the linear ordering. So for example, all antichains
that contain the last vertex appear after all antichains that do not.
In order to force the use of the lexordering induced by a particular
linear extension of P, the vertex set X may be specified as a list in
the desired order, rather than as a set.
Optionally, if the last argument is a range a..b, then only those
antichains whose sizes fit within this range are listed.
Optionally, if the last argument is the name 'max', then only maximal
antichains are listed.
Optionally, if the last argument is a variable name, such as q, then
the result is the generating series for antichains; i.e., the sum
of q^nops(A) over all antichains A in P.
EXAMPLES:
antichains({[a,b],[b,c]},{a,b,c});
yields [{},{a},{b},{c}]
antichains({[a,b]},[a,b,c]); yields [{},{a},{b},{c},{a,c},{b,c}]
antichains({[a,b]},[c,a,b]); yields [{},{c},{a},{a,c},{b},{b,c}]
P:=chain(2) &* chain(3);
antichains(P,7,q); yields 1+7*q+9*q^2+3*q^3
antichains(P,'max'); yields [{1},{2,3},{2,5},{4,5},{6}]
P:=chain(3) &* chain(4);
antichains(P,3..3); yields
[{3,5,7},{3,5,10},{3,8,10},{6,8,10}]
SEE ALSO: chains, extensions, ideals, J
FUNCTION: atomic - test whether a lattice is atomic
CALLING SEQUENCE: atomic(L);
atomic(L,X);
atomic(L,n);
PARAMETERS: L = a lattice
X = a set (the vertex set)
n = a positive integer (the number of vertices)
SYNOPSIS:
The atoms of a lattice are the elements that cover the minimum element.
A lattice is atomic if every element is expressible as a join of atoms,
or equivalently, every element that covers only one element is an atom.
A lattice is geometric if and only if it is atomic and upper semimodular.
atomic(L) returns true or false according to whether the lattice L is
atomic. The procedure *does not* test whether L is a lattice.
atomic(L,X) does the same, if the vertex set of L is X.
atomic(L,n) does the same, if the vertex set of L is {1,...,n}.
EXAMPLES:
L:=({},1) &+ ({},3) &+ ({},1);
atomic(L); yields true
L:=J(chain(2),3);
atomic(L); yields false
SEE ALSO: lattice, meet, modular
FUNCTION: autgroup - automorphism group of a poset (or directed graph)
CALLING SEQUENCE: autgroup(P,<options>);
autgroup(P,X,<options>);
autgroup(P,n,<options>);
PARAMETERS: P = a poset (or directed graph)
X = a set (the vertex set)
n = a positive integer (the number of vertices)
<options> = 'permgroup' or 'gap'
SYNOPSIS:
An automorphism of a poset P with vertex set X is a bijection x -> x'
from X to X such that x < y in P if and only if x' < y' in P.
autgroup(P,X) returns a list of generators of the automorphism group
of P. Each automorphism is expressed as a set of equations of the form
{x_1=y_1, x_2=y_2,...}, meaning that x_1 -> y_1, x_2 -> y_2,... is an
automorphism.
autgroup(P,n) does the same, if the vertex set of P is {1,...,n}.
autgroup(P) does the same, assuming there are no isolated vertices.
If the last argument is 'permgroup' and the vertex set is {1,...,n},
then the output is expressed as a "permgroup" (see group[permgroup]).
More explicitly, the result is an unevaluated procedure call
permgroup(n, {<perm1>, <perm2>,...}),
where the terms <perm_i> are generators of the automorphism group of P,
expressed as permutations in disjoint cycle format. For a description
of this format, see group[permgroup].
If the last argument is 'gap' and the vertex set is {1,...,n}, then a
sequence of commands that defines the automorphism group of P in the
GAP language is output via printf. These commands may be pasted into a
GAP session. For more on GAP, see <http://www-gap.dcs.st-and.ac.uk/>.
More generally, P may be the edge set of any directed graph without
multiple edges.
EXAMPLES:
P:=({},3) &+ ({},2);
autgroup(P,6); yields [{2=3,3=2},{1=2,2=1},{5=4,4=5}]
P:=J({},3);
G:=autgroup(P,'permgroup'); yields
permgroup(8,{[[2,3],[6,7]],[[3,5],[4,6]]})
group[grouporder](G); yields 6
SEE ALSO: canon, isom, group[permgroup]
FUNCTION: canon - canonically relabel a poset (or directed graph)
CALLING SEQUENCE: canon(P); canon(P,'natural');
canon(P,X); canon(P,X,'natural');
canon(P,n); canon(P,n,'natural');
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
SYNOPSIS:
Two posets P and Q with vertex sets X and Y are isomorphic if there is
a bijection x -> x' from X to Y so that [x,y] is a relation in P if and
only if [x',y'] is a relation in Q.
Given a poset P with a vertex set X of size n, canon(P,X) returns a new
poset isomorphic to P, with vertex set {1,...,n}, such that if (Q,Y)
is any other poset isomorphic to (P,X), then canon(Q,Y) = canon(P,X).
The output is a poset that need not be naturally labeled--there may be
relations [i,j] with i>j.
canon(P,n) does the same, if the vertex set of P is {1,...,n}.
canon(P) does the same, assuming there are no isolated vertices.
The algorithm operates correctly with arbitrary directed graphs.
If the optional flag 'natural' is supplied, then the output will be a
canonical relabeling of the poset P that is natural. More generally,
this option can be used with any acyclic directed graph.
EXAMPLES:
P:=chain(2) &* chain(3);
canon(P,6); yields {[6,2],[4,1],[2,1],[5,3],[6,4],[3,4],[5,6]}
canon(dual(P)); yields {[6,2],[4,1],[2,1],[5,3],[6,4],[3,4],[5,6]}
P:={[a,b],[c,b],[c,d]};
canon(P,'natural'); yields {[2,4],[1,4],[2,3]}
SEE ALSO: autgroup, isom, rm_isom
FUNCTION: chain - total order of specified length
CALLING SEQUENCE : chain(n);
PARAMETERS: n = a positive integer
SYNOPSIS:
chain(n) returns the covering relation of the chain 1 < 2 < ... < n.
In the exceptional case n=1, it returns the poset structure {},1
(representing a poset with no relations and vertex set {1}).
EXAMPLES:
chain(4); yields {[1,2],[2,3],[3,4]}
chain(1); yields {},1
SEE ALSO: chains
FUNCTION: chains - list/count chains in a partially ordered set
CALLING SEQUENCE: chains(P,<option>);
chains(P,n,<option>);
chains(P,X,<option>);
PARAMETERS: P = a poset
X = a set (the vertex set); or, a linear extension of P
n = a positive integer (the number of vertices)
<option> = at most one of the following:
(1) a range, such as 2..7
(2) the name 'max'
(3) a variable name, such as q
SYNOPSIS:
A chain in a poset P with vertex set X is a list [x_1,x_2,...,x_k] of
vertices such that x_1 < x_2 < ... < x_k in P.
chains(P,X) returns a list of all chains in the poset P.
chains(P,n) does the same, if the vertex set of P is {1,2,...,n}.
chains(P) does the same, assuming that P has no isolated vertices.
The chains are listed in a lexicographic order so that chain C precedes
chain D if D contains the "last" vertex of the symmetric difference of C
and D. Here, "last" is determined by some linear extension of P; i.e.,
a linear ordering of X such that if x < y in P, then x precedes y in the
linear ordering. So for example, all chains that include the last vertex
of the linear extension appear after all chains that do not.
In order to force the use of the lexordering induced by a particular
linear extension of P, the vertex set X may be specified as a list in
the desired order, rather than as a set.
Optionally, if the last argument is a range a..b, then only those chains
whose sizes fit within this range are listed.
Optionally, if the last argument is the name 'max', then only maximal
chains are listed.
Optionally, if the last argument is a variable name, such as q, then
the result is the generating series for chain sizes (not lengths); i.e.,
the sum of q^nops(C) over all chains C in P. Note that the f-polynomial
of the poset obtained by adjoining maximum and minimum elements to P
is q*chains(P,X,q) (see 'f_poly').
EXAMPLES:
chains({[a,b],[b,c]},{a,b,c}); yields
[[],[a],[b],[a,b],[c],[a,c],[b,c],[a,b,c]]
P:={[1,2],[3,4]};
chains(P,[1,3,2,4]); yields [[],[1],[3],[2],[1,2],[4],[3,4]]
chains(P,[1,2,3,4]); yields [[],[1],[2],[1,2],[3],[4],[3,4]]
P:=({},1) &+ ({[1,2]},3) &+ ({},1);
chains(P,'max'); yields [[1,4,5],[1,2,3,5]]
chains(P,6,q); yields 1+6*q+8*q^2+5*q^3+q^4
chains(P,[1,2,3,4,5],3..3); yields
[[1,2,3],[1,2,5],[1,3,5],[2,3,5],[1,4,5]]
SEE ALSO: antichains, extensions, f_poly, ideals, zeta
FUNCTION: char_poly - characteristic polynomial of a (graded) poset
CALLING SEQUENCE: char_poly(P,q);
char_poly(P,X,q);
char_poly(P,n,q);
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
q = a variable name or expression
SYNOPSIS:
Let P be a ranked poset with vertex set X and a minimum element
(call it 0) such that all maximal elements of P have rank r.
The characteristic polynomial of P is the generating series
r-rank(x)
F(q) = SUM M[0,x] * q ,
summed over all vertices x in X, where M is the Mobius function of P.
The coefficients of the characteristic polynomial are known as the
Whitney numbers of P of the first kind.
char_poly(P,X,q) returns the characteristic polynomial of the poset P.
char_poly(P,n,q) does the same, if the vertex set of P is {1,...,n}.
char_poly(P,q) does the same, assuming P has no isolated vertices.
If P does not have a minimum element, an error is signaled. However,
no error is signaled if P is not ranked or not all maximal elements
have the same rank. In this case, the result is a fake characteristic
polynomial relative to the quasi-rank function provided by the
filtration of P (see 'filter').
EXAMPLES:
char_poly(J({},3),z); yields z^3 - 3*z^2 + 3*z - 1
P:=({},1) &+ ({},3) &+ ({},1);
factor(char_poly(P,5,q)); yields (q-1)*(q-2)
SEE ALSO: filter, mobius, ranked
FUNCTION: closure - transitive closure of an acyclic digraph
CALLING SEQUENCE: closure(R);
closure(R,X);
closure(R,n);
PARAMETERS: R = an acyclic relation or digraph
X = a set (the vertex set)
n = a positive integer (the number of vertices)
SYNOPSIS:
If R is a set of ordered pairs [a,b] representing the edge set of an
acyclic digraph, then closure(R) returns the transitive closure of R;
i.e., the smallest set S containing R such that whenever [a,b] and
[b,c] belong to S, then so does [a,c].
More generally, if R is the edge set of any digraph D, then closure(R)
returns the transitive closure of the acyclic subgraph of D induced by
the vertices that cannot reach a cycle of D via some directed path.
closure(R,X) does the same, if the vertex set of R is X.
closure(R,n) does the same, if the vertex set of R is {1,...,n}.
EXAMPLES:
closure({[1,2],[2,4],[1,3],[3,5],[4,6]}); yields
{[3,5],[1,2],[2,6],[1,4],[1,3],[4,6],[2,4],[1,5],[1,6]}
closure({[a,b],[a,c]},{a,b,c,d}); yields {[a,b],[a,c]}
SEE ALSO: covers
FUNCTION: connected - connected components and poset connectivity test
CALLING SEQUENCE: connected(P); connected(P,'C');
connected(P,X); connected(P,X,'C');
connected(P,n); connected(P,n,'C');
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
C = a name (optional)
SYNOPSIS:
If P is a poset with vertex set X, then connected(P,X) returns true or
false according to whether P is connected. More generally, if P is the
edge set of any directed graph, connected(P,X) determines whether the
graph is weakly connected.
connected(P,n) does the same, if the vertex set of P is {1,...,n}.
connected(P) does the same, assuming that P has no isolated vertices.
Optionally, if the last argument is an unassigned name, such as C,
then in addition to testing the weak connectivity of P, the procedure
assigns to C the set of vertex sets of the connected components of P.
For extracting the subposet of P induced by one of its connected
components, use the 'subposet' function.
EXAMPLES:
P:=chain(2) &u chain(3);
connected(P,'C'),C; yields false, {{1,2}, {3,4,5}}
P:=chain(2) &* chain(3);
connected(P); yields true
connected(P,7); yields false
SEE ALSO: ranked, subposet
FUNCTION: covers - covering relation of an acyclic digraph
CALLING SEQUENCE: covers(R);
covers(R,X);
covers(R,n);
PARAMETERS: R = an acyclic relation or digraph
X = a set (the vertex set)
n = a positive integer (the number of vertices)
SYNOPSIS:
If R is an acyclic set of ordered pairs [a,b], then covers(R) returns
the covering relation of R, i.e., the smallest subset C of R with the
property that for every pair [a,b] in R, there exists a directed path
[a,c_0], [c_0,c_1], ..., [c_k,b] to a from b through edges in C.
More generally, if R is the edge set of any digraph D, then covers(R)
returns the covering relation of the acyclic subgraph of D induced by
the vertices that cannot reach a cycle of D via some directed path.
covers(R,X) does the same, if the vertex set of R is X.
covers(R,n) does the same, if the vertex set of R is {1,...,n}.
EXAMPLES:
covers({[a,b],[b,d],[d,e],[a,e],[c,d]});
yields {[a,b],[b,d],[d,e],[c,d]}
Q:=closure(chain(4));
covers(Q,5); yields {[1,2],[2,3],[3,4]}
SEE ALSO: closure
FUNCTION: &u - disjoint union of posets
CALLING SEQUENCE: S1 &u S2 &u S3 ...;
&u(S1, S2, S3,...);
PARAMETERS: S1, S2, ... = a sequence of two or more poset "structures"
A poset structure S is any one of the following:
P where P is a poset--i.e., a set of covering relations
(P,X) where P is a poset with vertex set X
(P,n) where P is a poset with vertex set {1,2,...,n}
SYNOPSIS:
If P and Q are posets with disjoint vertex sets X and Y, their union
(or direct sum) is defined to be the poset with vertex set X union Y,
with x < y if and only if both are in X and satisfy x < y in P, or both
are in Y and satisfy x < y in Q.
Whenever the posets package is loaded via the 'with' command, a neutral
operator &u for constructing disjoint unions is defined. Assuming
that P and Q are posets without isolated vertices, the operation P &u Q
(and more generally, P &u Q &u R, etc.) will produce the disjoint union
of P and Q (and R ...). The output of this computation will be a poset
that is *isomorphic* to the union of P and Q, not necessarily *equal*
to the union of P and Q. In particular, the vertex set of the result
will be {1,2,...,p+q} if P has p vertices and Q has q vertices.
Whether or not the vertex sets of P and Q are actually disjoint, they
are treated as if they were.
To allow for posets with isolated vertices, the operator &u also
accepts poset structures of the form (P,X) or (P,n). The former is used
to indicate that the vertex set of P is X, and the latter to indicate
that the vertex set is {1,...,n}. If any of the arguments passed to &u
are of this form, then the result returned will also be of this form.
EXAMPLES:
chain(2) &u chain(3); yields {[1,2],[3,4],[4,5]}
({[a,b],[b,c]},{a,b,c,d}) &u chain(2);
yields {[1,2],[2,4],[5,6]}, 6
S:=chain(2),3; &u(S,S,S,S); yields {[1,2],[4,5],[7,8],[10,11]}, 12
SEE ALSO: &+, &*
FUNCTION: distributive - test distributivity of lattices
CALLING SEQUENCE: distributive(L); distributive(L,'S');
distributive(L,X); distributive(L,X,'S');
distributive(L,n); distributive(L,n,'S');
PARAMETERS: L = a lattice
X = a set (the vertex set)
n = a positive integer (the number of vertices)
S = a name (optional)
SYNOPSIS:
A lattice L is distributive if the meet and join operations satisfy
the distributive laws, or equivalently, if L is isomorphic to J(P),
where P is the subposet of L formed by its join-irreducible elements.
distributive(L) returns true or false according to whether the lattice L
is distributive. The procedure *does not* verify whether L is a lattice.
distributive(L,X) does the same, if X is the vertex set of L.
distributive(L,n) does the same, if {1,...,n} is the vertex set of L.
If the last argument is an unassigned name S, then the procedure will
return true or false as above, and in addition, assign to S the set of
join-irreducible elements of L.
The algorithm for testing distributivity is based on a criterion of
Greene and Markowsky: L is distributive if and only if it is (a) ranked,
and (b) the rank of L equals both the number of join irreducibles and
the number of meet irreducibles.
EXAMPLES:
L:=chain(3) &* chain(2);
distributive(L,'S'),S; yields true, {2,3,4}
P:=subposet(L,S);
isom(J(P,S),L); yields true
L:=({},1) &+ ({},3) &+ ({},1);
distributive(L); yields false
SEE ALSO: J, lattice, meet, modular, ranked, subposet
FUNCTION: dual - dual of a poset (or directed graph)
CALLING SEQUENCE: dual(P); dual(P,X); dual(P,n);
PARAMETERS: P = a poset (or any set of ordered pairs)
X = a set (the vertex set)
n = a positive integer (the number of vertices)
SYNOPSIS:
If P is a set of ordered pairs, then dual(P) returns the set in which
each member [a,b] of P is replaced with [b,a].
Any additional arguments are ignored.
EXAMPLES:
P:={[1,2],[1,3],[3,4]};
dual(P); yields {[2,1], [3,1], [4,3]}
dual(P,5); yields {[2,1], [3,1], [4,3]}
SEE ALSO:
FUNCTION: eulerian - test whether a poset is Eulerian
CALLING SEQUENCE: eulerian(P); eulerian(P,'R');
eulerian(P,X); eulerian(P,X,'R');
eulerian(P,n); eulerian(P,n,'R');
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
R = a name (optional)
SYNOPSIS:
A poset P with vertex set X is Eulerian if it is bounded (i.e., has
a maximum and minimum element), ranked, and the Mobius function of P
at [x,y] is (-1)^(rank(y)-rank(x)) for all x <= y in P (see 'mobius').
eulerian(P,X) returns true or false according to whether P is Eulerian.
eulerian(P,n) does the same, if the vertex set of P is {1,2,...,n}.
eulerian(P) does the same, assuming that P has no isolated vertices.
Optionally, if the last argument is an unassigned name R and the poset
is ranked and bounded, then as a side effect the procedure assigns to R
a list [X_0, X_1, ..., X_m], where X_i is the set of vertices of rank i.
EXAMPLES:
P:=({},1) &+ ({},2) &+ ({},2) &+ ({},1);
eulerian(P); yields true
eulerian(P,7); yields false
eulerian(J({[1,2]},3),'R'),R; yields false, [{1},{2,3},{4,5},{6}]
SEE ALSO: mobius, ranked
FUNCTION: extensions - linear extensions of a poset (or acyclic digraph)
CALLING SEQUENCE: extensions(P);
extensions(P,X);
extensions(P,n);
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
SYNOPSIS:
A linear extension of a poset P with vertex set X is a linear ordering
[x_1,...,x_n] of X so that x_i < x_j in P implies i < j.
extensions(P,X) returns a list of all linear extensions of the poset P.
extensions(P,n) does the same, if the vertex set of P is {1,...,n}.
extensions(P) does the same, assuming that P has no isolated vertices.
The procedure also operates correctly on acyclic digraphs.
To quickly generate a single linear extension, use map(op,filter(P,X)).
To quickly count the linear extensions of P, use W(P,X,1,1).
EXAMPLES:
extensions({[1,2]},3); yields [[1,2,3], [1,3,2], [3,1,2]]
extensions({[1,2]}); yields [[1, 2]]
extensions({[a,b],[a,c]},{a,b,c}); yields [[a,b,c], [a,c,b]]
SEE ALSO: filter, W
FUNCTION: filter - filtration of a poset (or directed graph)
CALLING SEQUENCE: filter(P);
filter(P,X);
filter(P,n);
PARAMETERS: P = a poset (or more generally, an acyclic digraph)
X = a set (the vertex set)
n = a positive integer (the number of vertices)
SYNOPSIS:
The filtration of a poset P is an ordered partition [F_1,...,F_r] of
the vertex set of P defined recursively as follows: F_1 is the set of
minimal elements of P, and [F_2,...,F_r] is the filtration of P - F_1.
filter(P,X) returns the filtration of a poset P with vertex set X.
filter(P,n) does the same, if the vertex set of P is {1,...,n}.
filter(P) does the same, assuming that P has no isolated vertices.
Note that map(op,filter(P,X)) is a linear extension of P.
More generally, if D is a directed graph with vertex set X and F_1 is
the set of vertices of D with out-degree 0, then filter(D,X) returns
either [] (if F_1 is empty) or [F_1,F_2,...,F_r] (if F_1 is nonempty),
where [F_2,...,F_r] is the filtration of D - F_1.
Note that D is acyclic if and only if every vertex of D occurs in the
filtration of D.
The algorithm is based on a variation of topological sort.
See Knuth, TAOCP Volume I, Section 2.2.3.
EXAMPLES:
filter(J({},3)); yields [{1}, {2,3,5}, {4,6,7}, {8}]
filter({[a,b],[b,e],[c,e]},{a,b,c,d,e});
yields [{a,c,d}, {b}, {e}]
SEE ALSO: extensions, ranked, strongcomps
FUNCTION: flag_f - flag f-polynomial of a bounded, ranked poset
flag_h - flag h-polynomial of a bounded, ranked poset
CALLING SEQUENCE: flag_f(P,z); flag_h(P,z);
flag_f(P,X,z); flag_h(P,X,z);
flag_f(P,n,z); flag_h(P,n,z);
PARAMETERS: P = a bounded, ranked poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
z = a variable name
SYNOPSIS:
Let P be a ranked poset with vertex set X, and assume it is bounded;
i.e., P has a minimum and a maximum element. The flag f-polynomial
of P is defined to be the sum of
z[rank(x_1)] * z[rank(x_2)] * ... * z[rank(x_k)],
where x_0 < x_1 < ... < x_k ranges over all chains in P of any length
k such that x_0 is the minimum element of P and x_k is the maximum
element of P. In particular, if the maximum element has rank r>0, then
every term in the sum includes the factor z[r].
The flag h-polynomial of P may be expressed in terms of the flag
f-polynomial F(z[1],...,z[r]) as follows:
(1-z[1])* ... *(1-z[r]) * F( z[1]/(1-z[1]), ..., z[r]/(1-z[r]) ).
flag_f(P,X,z) returns the flag f-polynomial of the poset P, expressed
in terms of the variables z[1], z[2],..., z[r], where r=rank(P).
flag_f(P,n,z) does the same, if the vertex set of P is {1,...,n}.
flag_f(P,z) does the same, assuming that P has no isolated vertices.
The syntax for computing the flag h-polynomial is the same.
If the poset is not ranked or not bounded, an error is signaled.
In particular, a poset with isolated vertices and nops(X)>1 will
always trigger an error.
If the variables z[1],...,z[r] are all specialized to the same value,
the flag f-polynomial specializes to the f-polynomial and the flag
h-polynomial specializes to the h-polynomial (see 'f_poly').
The W-polynomial W(Q,Y,q,t) is the flag h-polynomial of J(Q,Y) with
the variables z[1],...,z[r] specialized so that z[i]=q^i*t.
EXAMPLES:
P:=({},1) &+ ({},3) &+ chain(2);
flag_f(P,z); yields
z[3]+3*z[1]*z[3]+z[2]*z[3]+3*z[1]*z[2]*z[3]
flag_h(P,z); yields z[3]+2*z[1]*z[3]
flag_h(chain(4),4,q); yields q[3]
SEE ALSO: chains, f_poly, h_poly, ranked, omega, W, zeta
FUNCTION: f_poly - f-polynomial of a bounded poset
h_poly - h-polynomial of a bounded poset
CALLING SEQUENCE: f_poly(P,z); h_poly(P,z);
f_poly(P,X,t); h_poly(P,X,t);
f_poly(P,n,t); h_poly(P,n,t);
PARAMETERS: P = a bounded poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
t = a variable name or expression
SYNOPSIS:
Let P be a poset with vertex set X, and assume that P is bounded;
i.e., P has a minimum and a maximum element. The f-polynomial of P is
defined to be the sum of f_k * t^k, where f_k denotes the number of
chains of length k from the minimum element to the maximum element
(i.e., 0 < x[1] < ... < x[k-1] < 1, if 0 is the minimum and 1 is the
maximum). In particular, f_2 is the number of non-extreme vertices,
and except for the case of a singleton poset, f_1=1 and f_0=0.
The h-polynomial of P is related to the f-polynomial f(P,t) by the
rule h(P,t) = (1-t)^d * f(P,t/(1-t)), where d = degree(f).
f_poly(P,X,t) returns the f-polynomial of the poset P, evaluated at t.
f_poly(P,n,t) does the same, if the vertex set of P is {1,...,n}.
f_poly(P,t) does the same, assuming that P has no isolated vertices.
The syntax for computing the h-polynomial is the same.
If the poset is not bounded, an error is signaled. In particular, a
poset with isolated vertices and nops(X)>1 always triggers an error.
The f-polynomial f(P,t) and the chain polynomial C(P,t) (see 'chains')
are related: (1+t)^2 * f(P,t) = t * C(P,t), unless P is a singleton.
The f-polynomial is also related to the zeta polynomial (see 'zeta').
The h-polynomial of J(P) at t is the W-polynomial of P at (q,t)=(1,t).
That is, h_poly(J(P,X),t) = W(P,X,1,t) (see 'W').
EXAMPLES:
P:=({},1) &+ (chain(2) &u chain(3)) &+ ({},1);
f_poly(P,t); yields t+5*t^2+4*t^3+t^4
h_poly(J({},3),z); yields z+4*z^2+z^3
SEE ALSO: chains, flag_f, flag_h, W, zeta
FUNCTION: ideals - list/count order ideals in a partially ordered set
CALLING SEQUENCE: ideals(P,<option>);
ideals(P,n,<option>);
ideals(P,X,<option>);
PARAMETERS: P = a poset
X = a set (the vertex set); or, a linear extension of P
n = a positive integer (the number of vertices)
<option> = at most one of the following:
(1) a range, such as 2..7
(2) a variable name, such as q
SYNOPSIS:
Let P be a poset with vertex set X. An order ideal of P is a subset I
of X such that if x is in I and y < x in P, then y is in I.
ideals(P,X) returns a list of all order ideals of P.
ideals(P,n) does the same, if the vertex set of P is {1,2,...,n}.
ideals(P) does the same, assuming that P has no isolated vertices.
The ideals are listed in a lexicographic order with ideal I preceding
ideal J if J contains the "last" vertex of the symmetric difference of
I and J. Here, "last" is determined by some linear extension of P;
i.e., a linear ordering of the vertex set X such that if x < y in P,
then x precedes y in the linear ordering. So for example, all ideals
that contain the last vertex appear after all ideals that do not.
In order to force the use of the lexordering induced by a particular
linear extension of P, the vertex set X may be specified as a list in
the desired order, rather than as a set.
Optionally, if the last argument is a range a..b, then only those
order ideals whose sizes fit within this range are listed.
Optionally, if the last argument is a name, such as q, then the result
is the generating series for order ideals; i.e., the sum of q^nops(I)
over all order ideals I of P.
Note that ideals(P,X,q) is the rank generating function for J(P,X).
EXAMPLES:
ideals(chain(3)); yields [{},{1},{1,2},{1,2,3}]
ideals({},[a,b,c]); yields
[{},{a},{b},{a,b},{c},{a,c},{b,c},{a,b,c}]
ideals({[1,3],[2,3]},4,3..4); yields [{1,2,4},{1,2,3},{1,2,3,4}]
ideals({[1,3],[2,3]},[1,2,3,4],3..4);
yields [{1,2,3},{1,2,4},{1,2,3,4}]
ideals(chain(2) &* chain(3),q); yields 1+q+2*q^2+2*q^3+2*q^4+q^5+q^6
SEE ALSO: antichains, extensions, J
FUNCTION: isom - test posets (or directed graphs) for isomorphism
CALLING SEQUENCE: isom(S1,S2);
isom(S1,S2,'f');
PARAMETERS: S1,S2 = poset structures (or directed graphs)
f = a name (optional)
A poset structure S is any one of the following:
P where P is a poset--i.e., a set of covering relations
(P,X) where P is a poset with vertex set X
(P,n) where P is a poset with vertex set {1,2,...,n}
SYNOPSIS:
Two posets P and Q with vertex sets X and Y are isomorphic if there is
a bijection x -> x' from X to Y so that [x,y] is a relation in P if and
only if [x',y'] is a relation in Q.
isom(P,X,Q,Y) returns true or false according to whether the posets P
and Q are isomorphic. More generally, P and Q may be edge sets of
arbitrary directed graphs without multiple edges. If the vertex set of
P (or Q) is {1,...,n}, then one may substitute n for X (or Y) in the
argument list. If P (or Q) has no isolated vertices, then X (or Y) may
be omitted.
isom(P,X,Q,Y,'f') does the same, and additionally, if P and Q do turn
out to be isomorphic, assigns to f an isomorphism X -> Y. The isomorphism
is expressed as a set of equations {x_1=y_1, x_2=y_2, ...}, meaning that
x_1 -> y_1, x_2 -> y_2,... is an isomorphism. In particular, subs(f,P)=Q.
The algorithm works by repeatedly refining ordered partitions of X
and Y so that P and Q are isomorphic only if there is an isomorphism
that respects the partitions. It terminates when the blocks of the
partitions are singletons. It is similar to the algorithm used in Nauty
(see <http://cs.anu.edu.au:80/people/bdm/nauty/>).
Reference: B. McKay, Congressus Numerantium 30 (1981), 45--87.
EXAMPLES:
P:=chain(2) &* chain(3); Q:=chain(3) &* chain(2);
isom(P,Q); yields true
isom(P,Q,8); yields false
isom(P,7,Q,7,'f'): f; yields {1=1,2=4,3=2,5=3,4=5,6=6,7=7}
P:=J({[a,b],[a,c]});
isom(P,dual(P)); yields false
SEE ALSO: autgroup, canon, rm_isom
FUNCTION: J - lattice of order ideals of a poset
CALLING SEQUENCE: J(P); J(P,X); J(P,n);
PARAMETERS: P = a poset
X = a set (the vertex set); or, a linear extension of P
n = a positive integer (the number of vertices)
SYNOPSIS:
Let P be a poset with vertex set X. An order ideal of P is a subset I
of X such that if x is in I and y < x in P, then y is in I. The set of
all order ideals of P forms a partial order (in fact, a distributive
lattice) with respect to inclusion.
J(P,X) returns (the covering relation of) an abstract poset that is
isomorphic to the lattice of order ideals of P. The vertex set of the
output is {1,2,...,m} for some m, and corresponds to the listing order
used by 'ideals'. That is, ideals(P,X)[i] is vertex i of J(P,X).
J(P,n) does the same, if the vertex set of P is {1,...,n}.
J(P) does the same, assuming that there are no isolated vertices.
The listing order used by 'ideals' is controlled by the choice of a
linear extension of P; i.e., a linear ordering of the vertices such that
if x < y in P, then x precedes y in the linear ordering. In order to
force a specific choice for the linear extension, the vertex set X may
be specified as a list in the desired order, rather than as a set.
The order ideals of P are in bijection with the antichains of P.
EXAMPLES:
J({},3); yields {[1,2],[1,3],[1,5],[2,4],[2,6],[3,4],
[3,7],[4,8],[5,6],[5,7],[6,8],[7,8]}
L:=J(J({},2)); yields {[1,2],[2,3],[2,4],[3,5],[4,5],[5,6]}
distributive(L); yields true
J({[a,b],[b,c]},{a,b,c});
yields {[1,2],[2,3],[3,4]}
J({[a,b]},[a,b,c]); yields
{[1,2],[1,4],[2,3],[2,5],[3,6],[4,5],[5,6]}
J({[a,b]},[c,a,b]); yields
{[1,2],[1,3],[2,4],[3,4],[3,5],[4,6],[5,6]}
SEE ALSO: antichains, ideals, distributive, extensions, lattice
FUNCTION: lattice - test whether a poset is a lattice or semi-lattice
CALLING SEQUENCE: lattice(P); lattice(P,'semi');
lattice(P,X); lattice(P,X,'semi');
lattice(P,n); lattice(P,n,'semi');
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
SYNOPSIS:
A poset P is a lattice if every pair of elements has a greatest lower
bound (the meet) and a least upper bound (the join).
lattice(P,X) returns true or false according to whether the poset P
with vertex set X is a lattice.
lattice(P,n) does the same, if the vertex set of P is {1,...,n}.
lattice(P) does the same, assuming that P has no isolated vertices.
If the final argument is the name 'semi', then the procedure returns
true or false according to whether P is a meet semi-lattice; i.e.,
whether every pair of elements has a greatest lower bound.
Use the dual of P to test whether P is a join semi-lattice.
The algorithm used for lattice-testing relies on the fact that it
suffices to check that there is a maximum element and that the meet
of x and y exists when there is a z covering x and y. Reference:
Bjorner-Edelman-Ziegler, Discrete Comput. Geom. 5 (1990), p. 265.
To compute meets (or joins) in lattices, use the 'meet' function.
EXAMPLES:
L:=chain(2) &* chain(3);
lattice(L,6); yields true
lattice(L,7); yields false
M:=({},3) &+ L;
lattice(M); yields false
lattice(dual(M),'semi'); yields true
SEE ALSO: distributive, dual, meet, modular
FUNCTION: Lattices - list nonisomorphic lattices
CALLING SEQUENCE: Lattices(n);
Lattices(n,<property>);
PARAMETERS: n = a positive integer (must be <= 10)
<property> = a Boolean procedure
SYNOPSIS:
For n <= 10, Lattices(n) returns a complete list of (covering relations
of) nonisomorphic lattices on n vertices. Each lattice in the list uses
the vertex set {1,2,...,n}, and is naturally labeled--every relation
[i,j] that occurs satisfies i<j. The lattices are stored in a partially
compressed format--there may be a noticeable delay in producing the list.
n nops(Lattices(n)) length(Lattices(n))
1 1 7
2 1 15
3 1 23
4 2 67
5 5 223
6 15 839
7 53 3599
8 222 17803
9 1078 99995
10 5994 647783
If <property> is a Boolean (i.e., true/false-valued) procedure, then
Lattices(n,<property>) will return the sublist of Lattices(n) consisting
of those lattices L such that <property>(L) is true. Built-in examples
of such procedures include: atomic, distributive, modular, and ranked.
Any additional arguments beyond the second will be passed on to the
testing procedure. Thus for example, Lattices(6,f,a,b,...) will produce
the list of lattices L on 6 vertices such that f(L,a,b,...) is true.
EXAMPLES:
Lattices(3); yields [{[1,2],[2,3]}]
Lattices(7)[26]; yields
{[1,2],[2,3],[6,7],[4,6],[3,5],[4,5],[1,4],[5,7]}
nops(Lattices(6,ranked)); yields 9
SEE ALSO: Posets, atomic, distributive, modular, ranked
FUNCTION: meet - compute meets in lattices, maximal lower bounds in posets
CALLING SEQUENCE: meet(P); meet(P,V);
meet(P,X); meet(P,X,V);
meet(P,n); meet(P,n,V);
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
V = a list of vertices of P (optional)
SYNOPSIS:
Given elements a,b,... of a poset P, their meet is defined to be the
greatest lower bound of a,b,..., if one exists. Otherwise, the meet is
undefined.
If P is a poset with vertex set X, meet(P,X) returns a symmetric table as
follows. For each pair of vertices i,j of P that possess a lower bound
(not necessarily a *greatest* lower bound), there is a table index (i,j)
whose corresponding entry is *some* maximal lower bound for i and j. The
procedure does not determine if there is only one maximal lower bound--
i.e., a true meet.
meet(P,n) does the same, if the vertex set of P is {1,...,n}.
meet(P) does the same, assuming that P has no isolated vertices.
In the second form, if the final argument is a list V of vertices of P,
the procedure returns a maximal lower bound for the vertices in V, if one
exists. If V has no lower bounds in P, then the value NULL is returned.
Use the dual of P to compute joins or minimal upper bounds in P.
EXAMPLES:
M:=meet(J({},3));
M[4,6], M[3,6]; yields 2, 1
P:={[a,b],[c,b],[d,c]};
meet(P,[a,c,d]); yields NULL
P:=({},2) &+ ({},2);
M:=meet(P,5);
M[1,5], M[3,4]; yields M[1, 5], 2
SEE ALSO: distributive, dual, lattice, modular
FUNCTION: mobius - Mobius function of a poset
CALLING SEQUENCE: mobius(P); mobius(P,[a,b]);
mobius(P,X); mobius(P,X,[a,b]);
mobius(P,n); mobius(P,n,[a,b]);
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
a,b = vertices of P (optional)
SYNOPSIS:
The Mobius function of a poset P is an integer-valued function on the set
of pairs (a,b) such that a <= b in P (or equivalently, on the intervals
of P). Its defining property is that for all a <= b in P, the sum of
mobius(a,c) over a <= c <= b is 0 for a < b, and 1 for a = b.
mobius(P,X) returns the Mobius function of the poset P with vertex set X,
in the form of a 'sparse' table; indices of the table are the pairs (a,b)
such that a <= b in P.
mobius(P,n) does the same, if the vertex set of P is {1,...,n}.
mobius(P) does the same, assuming that P has no isolated vertices.
In the second form, if the final argument is a list [a,b] of two vertices
of P, the procedure returns the Mobius function of P at (a,b). If it is
not true that a <= b in P, then 0 is returned.
If P has a minimum element 0 and maximum element 1, then
mobius(P,[0,1])=zeta(P,-1).
EXAMPLES:
mobius({[a,b],[a,c]},{a,b,c}); yields
table(sparse,[(a,a)=1,(a,b)=-1,(a,c)=-1,(b,b)=1,(c,c)=1])
P:=({},1) &+ ({},4) &+ ({},1);
mobius(P,[1,6]); yields 3
mo:=mobius(J({},3));
mo[1,8], mo[2,3]; yields -1, 0
SEE ALSO: char_poly, eulerian, subinterval, zeta
FUNCTION: modular - test modularity and semi-modularity of lattices
CALLING SEQUENCE:
modular(L); modular(L,'lower'); modular(L,'upper');
modular(L,X); modular(L,X,'lower'); modular(L,X,'upper');
modular(L,n); modular(L,n,'lower'); modular(L,n,'upper');
PARAMETERS: L = a lattice
X = a set (the vertex set)
n = a positive integer (the number of vertices)
SYNOPSIS:
A lattice L is upper (resp., lower) semi-modular if it is ranked, and the
rank function r satisfies r[a] + r[b] >= r[meet(a,b)] + r[join(a,b)] for
all vertices a and b (resp., with <= in place of >=). L is modular if it
is both upper and lower semi-modular. L is geometric if and only if it is
atomic and upper semi-modular.
modular(L) returns true or false according to whether the lattice L is
modular. If the final argument is 'upper' (resp., 'lower'), the procedure
tests only for upper (resp., lower) semi-modularity.
modular(L,X) does the same, if the vertex set of L is X.
modular(L,n) does the same, if the vertex set of L is {1,...,n}.
The procedure *does not* test to see whether L is actually a lattice.
EXAMPLES:
L:=({},1) &+ ({},3) &+ ({},1);
modular(L); yields true
L:=({},1) &+ (chain(2),3) &+ ({},1);
modular(L); yields false
L:=({},1) &+ {[1,2],[1,3],[4,3],[4,5]} &+ ({},1);
modular(L,'upper'); yields true
modular(L,'lower'); yields false
SEE ALSO: atomic, distributive, lattice, meet, ranked
FUNCTION: omega - order polynomial of a poset
CALLING SEQUENCE: omega(P,z,<options>);
omega(P,X,z,<options>);
omega(P,n,z,<options>);
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
z = a variable name or expression
<options> = any of the following, in any order:
(1) 'ideals' or 'linear' (specifying an algorithm)
(2) a subset of P (specifying descent positions)
SYNOPSIS:
The order polynomial of a poset P with vertex set X is the unique
polynomial F(z) such that for all integers m>0, F(m) equals the number
of order-preserving maps from P to an m-element chain.
omega(P,X,z) returns the order polynomial of P, evaluated at z.
omega(P,n,z) does the same, if the vertex set of P is X={1,...,n}.
omega(P,z) does the same, assuming that P has no isolated vertices.
Note that omega(P,X,z) = zeta(J(P,X),z).
Two algorithms are provided for computing order polynomials: 'linear'
and 'ideals'. The 'linear' algorithm has minimal space requirements and
a running time that is linear in the number of linear extensions of P.
The 'ideals' algorithm is more appropriate for larger posets, and has
worst-case time and space requirements that are quadratic in the number
of order ideals of P. If neither algorithm is specified, the default is
to use the 'linear' option for posets with <= 6 vertices, and the
'ideals' option otherwise.
The second optional argument is a subset S of P. This option is for
computing the order polynomials of *labeled* posets, in the following
sense. Let L be a labeling of the poset P with vertex set X; that is,
an integer numbering of the vertex set X without repetitions. Let S be
the subset of the covering relation of P consisting of all pairs [a,b]
such that b covers a in P and L[a] > L[b]. The order polynomial of P
with respect to L is the unique polynomial F(z) such that for all
integers m>0, F(m) equals the number of order-preserving maps f from P
to an m-element chain such that f(a) < f(b) whenever [a,b] is in S.
If S = {}, we obtain the usual order polynomial as defined above.
If there does not exist a labeling L of P for which S is the set of
covering pairs [a,b] such that L[a] > L[b], then S is inadmissible and
an error is signaled.
EXAMPLES:
f:=omega(chain(4),5,z);
factor(f); yields 1/24*z^2*(z+3)*(z+2)*(z+1)
f:=omega(chain(4),z,{[3,4]});
factor(f); yields 1/24*z*(z-1)*(z+2)*(z+1)
f:=omega(chain(4),6,z,'ideals');
factor(f); yields 1/24*z^3*(z+3)*(z+2)*(z+1)
omega({[a,b],[a,c]},{a,b,c,d},3); yields 42
P:=chain(9); S:=chain(5);
9!*omega(P,q,'linear',S); yields
q^9 - 30*q^7 + 273*q^5 - 820*q^3 + 576*q
SEE ALSO: extensions, ideals, J, W, zeta
FUNCTION: &+ - ordinal sum of posets
CALLING SEQUENCE: S1 &+ S2 &+ S3 ...;
&+(S1,S2,S3,...);
PARAMETERS: S1, S2, ... = a sequence of two or more poset "structures"
A poset structure S is any one of the following:
P where P is a poset--i.e., a set of covering relations
(P,X) where P is a poset with vertex set X
(P,n) where P is a poset with vertex set {1,2,...,n}
SYNOPSIS:
If P and Q are posets with disjoint vertex sets X and Y, their ordinal
sum is defined to be the poset with vertex set X union Y, with x < y if
and only if x < y in P, or x < y in Q, or x is in X and y is in Y.
Whenever the posets package is loaded via the 'with' command, a neutral
operator &+ for constructing ordinal sums is defined. Assuming that P
and Q are posets without isolated vertices, the operation P &+ Q (and
more generally, P &+ Q &+ R, etc) will compute the ordinal sum of P and
Q (and R ...). The output of this computation will be a poset that is
*isomorphic* to the ordinal sum of P and Q, but not necessarily *equal*
to the ordinal sum of P and Q. In particular, the vertex set of the
result will be {1,2,...,p+q} if P has p vertices and Q has q vertices.
Whether or not the vertex sets of P and Q are actually disjoint, they
are treated as if they were.
To allow for posets with isolated vertices, the operator &+ also
accepts poset structures of the form (P,X) or (P,n). The former is used
to indicate that the vertex set of P is X, and the latter to indicate
that the vertex set is {1,...,n}.
EXAMPLES:
one:=({},1); two:=({},2);
P:=two &+ two; yields {[1,3],[1,4],[2,3],[2,4]}
&+(one,P,one,one); yields
{[1,2],[1,3],[2,4],[2,5],[3,4],[3,5],[4,6],[5,6],[6,7]}
SEE ALSO: &u, &*
FUNCTION: plot_poset - plot posets (or acyclic directed graphs)
CALLING SEQUENCE: plot_poset(P,<options>);
plot_poset(P,X,<options>);
plot_poset(P,n,<options>);
PARAMETERS: P = a poset (or acyclic directed graph)
X = a set (the vertex set)
n = a positive integer (the number of vertices)
<options> = any of the following, in any order:
(1) 'dot', or dot=<filename>
(2) 'proportional'
(3) levels=<list>
(4) stretch=<number>
(5) ecolor=<color>, or ecolor=<table>
(6) vcolor=<color>
(7) 'labels', or labels=<table>
(8) any options known to plots[display]
SYNOPSIS:
plot_poset(P,X) plots the Hasse diagram of a poset P with vertex set X
using Maple 2D graphics or (optionally) writes a description of P in
the "dot" language for external processing by the Graphviz package.
For information about dot and Graphviz, see <http://www.graphviz.org/>.
plot_poset(P,n) does the same, if {1,...,n} is the vertex set of P.
plot_poset(P) does the same, assuming that P has no isolated vertices.
The procedure also operates correctly on acyclic directed graphs.
The default layout algorithm for Maple 2D plots proceeds as follows.
First, the vertex set is partitioned into levels according to 'filter',
and the vertices within each level are ordered left-to-right by 'sort'.
An initial layout is then chosen, with equal horizontal spacing between
the vertices in each level and edges represented by straight lines.
Finally, an adjustment algorithm is used to horizontally shift the
positions of vertices until there are no "phantom" relations
(i.e., line segments that pass through vertices of P).
For dot plots, the default layout algorithm is dependent on the external
software used to process the output.
There are several options for controlling the form of the plot:
'dot'
Write to the terminal a description of the plot in the dot language,
suitable for use by the Graphviz package. The default is a Maple plot.
dot=<filename>
Same as above, except that the output is written to the named file
using a Maple 'writeto' command. If there is an existing file with the
same name, it is overwritten.
'proportional'
Force the horizontal spacing between vertices in each level to be
inversely proportional to the number of vertices in that level. This
tends to produce better-looking plots for posets in which there is
extreme variation in the number of vertices in consecutive levels.
This option is ignored in dot plots.
levels=<list>
Use the given list to partition the vertex set into levels. The i-th
item of the list must be a set or list that specifies which vertices
should appear at the i-th level. An error is signaled if the vertex
set of P does not coincide with the union of the level sets. Another
error is signaled if there is an edge [x,y] such that vertex x is in
a level at or above the level of vertex y.
In Maple plots, if the i-th level is specified as a list, then the
left-to-right ordering of the list is preserved in the layout; if it
is a set, the left-to-right ordering is determined by applying 'sort'.
The default is levels=filter(P,X).
In dot plots, the left-to-right ordering within each level is
determined by the external software used to process the output.
stretch=<number>
Stretch the vertical axis by the indicated factor. In some versions
of Maple, similar effects may be achieved by selecting 'Unconstrained'
from the 'Projection' menu of a plot, and then reshaping the window.
This option is ignored in dot plots.
ecolor=<color>
Specify the color of the edges in the plot. The default color is set
by the global variable `posets/default`[ecolor] and may be redefined
by the user. The initial default value is 'red'.
ecolor=<table>
Specify individual colors for each (covering) edge of P. The entries
of the table should be subsets of the covering edges of P, and the
index corresponding to a given entry should be the desired color for
the given set of edges. Any edge of P not occurring in one of the
color-sets will be assigned the default edge color.
vcolor=<color>
Specify the color of the vertices and text labels in the plot. The
default color is set by the global variable `posets/default`[vcolor]
and may be redefined by the user. The initial default value is 'black'
(in Maple V R4 or later) or 'white' (in Maple V R3 or earlier).
Note that in dot plots, 'white' is probably not what you want.
'labels'
Specify that the vertices of P should be represented in the plot by
their names, rather than by points (the default).
labels=<table>
Specify a label for each vertex of P. The indices of the table should
be the vertices of P, and the corresponding entries are the desired
labels. The entries must be of type 'string' (not names or numbers).
If any vertex of P is missing from the table, an error is signaled.
In Maple plots, any options not recognized by plot_poset are passed as
arguments to plots[display]. In dot plots, these options are ignored.
EXAMPLES:
P:=J({},4);
plot_poset(P,stretch=0.9,title=`Boolean Algebra on 4 Points`);
Q:=subinterval(P,[1,12]);
C:=table([green=Q]);
plot_poset(P,ecolor=C,labels);
P:={[1,2],[2,3],[4,3],[4,5],[5,6]};
ranked(P,6,'R'),R;
plot_poset(P,levels=R,vcolor=blue);
P:=({},1) &+ rand_poset(20,0.3);
plot_poset(P,stretch=1.5);
plot_poset(P,vcolor=black,'dot');
M:=mobius(P):
L:=table([seq(i=convert(M[1,i],'string'),i=1..21)]);
plot_poset(P,labels=L);
plot_poset(P,labels=L,vcolor=black,dot=`myplot.dot`);
P:=({},1) &+ ({},2) &+ ({},10) &+ ({},2) &+ ({},1);
plot_poset(P,proportional);
P:=J(chain(4),5); P:={op(P),[3,11],[11,8],[5,12],[12,9]};
plot_poset(P,labels);
F:=filter(P); F:=subsop(2=[3,2],3={4,5},4=[11,6,7,12],F);
plot_poset(P,levels=F,labels);
SEE ALSO: colors, filter, plot[options], plots[display], writeto
FUNCTION: Posets - list nonisomorphic posets
CALLING SEQUENCE: Posets(n);
Posets(n,<property>);
PARAMETERS: n = a positive integer (must be <= 8)
<property> = a Boolean procedure
SYNOPSIS:
For n <= 8, Posets(n) returns a complete list of (covering relations of)
nonisomorphic posets on n vertices. Each poset in the list uses the
vertex set {1,2,...,n}, and is naturally labeled--every relation [i,j]
that occurs satisfies i<j.
n nops(Posets(n)) length(Posets(n))
1 1 7
2 2 19
3 5 79
4 16 395
5 63 2239
6 318 15131
7 2045 124367
8 16999 1277063
If <property> is a Boolean (i.e., true/false-valued) procedure, then
Posets(n,<property>) will return the sublist of Posets(n) consisting of
those posets P such that <property>(P) is true. Built-in examples of
such procedures include: connected, lattice, and ranked.
Any additional arguments beyond the second will be passed on to the
testing procedure. Thus for example, Posets(6,f,a,b,...) will produce
the list of posets P on 6 vertices such that f(P,a,b,...) is true.
EXAMPLES:
Posets(2); yields [{}, {[1,2]}]
Posets(5)[15]; yields {[1,3],[2,3],[3,5],[1,4]}
nops(Posets(4,connected,4)); yields 10
nops(Posets(4,connected)); yields 14
SEE ALSO: Lattices, connected, lattice, ranked
FUNCTION: &* - direct product of posets
CALLING SEQUENCE: S1 &* S2 &* S3 ...;
&*(S1,S2,S3,...);
PARAMETERS: S1, S2, ... = a sequence of two or more poset "structures"
A poset structure S is any one of the following:
P where P is a poset--i.e., a set of covering relations
(P,X) where P is a poset with vertex set X
(P,n) where P is a poset with vertex set {1,2,...,n}
SYNOPSIS:
If P and Q are posets with vertex sets X and Y, their direct product is
defined to be the poset with vertex set X x Y (Cartesian product), with
(x1,y1) <= (x2,y2) if and only if x1 <= x2 in P and y1 <= y2 in Q.
Whenever the posets package is loaded via the 'with' command, a neutral
operator &* for constructing direct products is defined. If P and Q
are posets without isolated vertices, the operation P &* Q (and more
generally, P &* Q &* R, etc) will compute the direct product of P and Q
(and R ...). The output of this computation will be a poset that is
*isomorphic* to the direct product of P and Q, but not necessarily
*equal* to the product of P and Q. In particular, the vertex set of the
result will be {1,2,...,p*q} if P has p vertices and Q has q vertices.
To allow for posets with isolated vertices, the operator &* also
accepts poset structures of the form (P,X) or (P,n). The former is used
to indicate that the vertex set of P is X, and the latter to indicate
that the vertex set is {1,...,n}. If all of the arguments passed to &*
are of this form, then the result returned will also be of this form.
EXAMPLES:
Q:=chain(2); P:=Q &* Q &* Q;
isom(P,J({},3)); yields true
Q &* ({[a,b]},{a,b,c}); yields {[1,2],[1,3],[2,4],[3,4],[5,6]}
(Q,3) &* (Q,3); yields
{[1,2],[1,4],[2,5],[3,6],[4,5],[7,8]}, 9
SEE ALSO: &u, &+
FUNCTION: rand_poset - random poset generator
CALLING SEQUENCE: rand_poset(n);
rand_poset(n,p);
rand_poset(n,coin);
PARAMETERS: n = a positive integer
p = a number specifying edge probabilities (0 < p < 1)
coin = a procedure for generating random coin tosses
SYNOPSIS:
rand_poset(n) uses the Maple pseudo random number generator 'rand' to
create a random poset on the vertex set {1,...,n} by the following
algorithm: for each ordered pair (i,j) such that 1 <= i < j <= n, the
procedure chooses to include or not include the relation i < j with
equal probability. The covering relation of the poset generated by
these relations is then returned.
The distribution of posets induced by this algorithm is far from uniform.
It tends to favor "long-and-stringy" posets.
If the optional second argument is a numeric value p (0 < p < 1), the
relation i < j with be included with probability p. Values of p less than
1/2 will tend to counteract the "long-and-stringy" effect.
If the optional second argument is a procedure 'coin', then random
values are generated by calls to coin(). If coin() returns the value 1,
then the relation i<j will be included; if any other value is returned,
the relation will be omitted.
EXAMPLES:
#results depend on the current state of the random number generator
rand_poset(10); yields {[1,3],[1,2],[2,6],[3,4],[4,6],
[4,8],[5,7],[6,7],[6,9],[8,9],[9,10]}
rand_poset(9,0.3); yields
{[1,5],[2,8],[3,5],[3,6],[4,5],[5,7],[6,9],[7,9]}
coin:=rand(1..4):
rand_poset(10,coin); yields {[1,5],[1,2],[2,6],[3,4],[3,5],
[5,7],[6,8],[6,9],[7,9],[7,10],[8,10]}
SEE ALSO: covers, rand
FUNCTION: ranked - test whether a poset is ranked
CALLING SEQUENCE: ranked(P); ranked(P,'R');
ranked(P,X); ranked(P,X,'R');
ranked(P,n); ranked(P,n,'R');
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
R = a name (optional)
SYNOPSIS:
A poset P with vertex set X is ranked if there exists an integer-valued
function r on X (the rank function) such that if y covers x in P, then
r[y]-r[x]=1. Note that the rank function is not unique.
ranked(P,X) returns true or false according to whether P is ranked.
ranked(P,n) does the same, if the vertex set of P is {1,2,...,n}.
ranked(P) does the same, assuming that P has no isolated vertices.
Optionally, if P is ranked and the last argument is an unassigned name,
such as R, then as a side effect the procedure will assign to R a list
[X_0, X_1, ..., X_m], where X_i is the set of vertices of rank i, using
the (unique) rank function with the property that the minimum rank in
every connected component of P is 0.
A poset P is graded if all maximal chains have the same length,
or equivalently, if the poset ({},1) &+ (P,X) &+ ({},1) obtained by
adjoining a maximum and minimum element is ranked.
EXAMPLES:
P:=({},1) &+ (chain(2),3) &+ ({},1);
ranked(P,6); yields false
P:={[1,2],[2,3],[4,3],[4,5]};
ranked(P); yields true
ranked(P &u dual(P),'R'),R; yields
true, [{1,8,10},{2,4,7,9},{3,5,6}]
SEE ALSO: connected, filter
FUNCTION: rm_isom - remove isomorphic copies from a list of posets
CALLING SEQUENCE: rm_isom(L);
PARAMETERS: L = a list or set of posets (or directed graphs)
SYNOPSIS:
Two posets P and Q are isomorphic if there is a bijection x -> x' from
the vertices of P to the vertices of Q so that [x,y] is a relation of P
if and only if [x',y'] is a relation of Q.
If L is a list or set of posets (viewed as sets of covering pairs, then
rm_isom(L) returns a sublist (or subset) of L with isomorphic copies
"pruned out". That is, every member of L will be isomorphic to exactly
one member of the returned list or set. If L is a list, then the result
returned will be the sublist of L formed by the first representative
from each isomorphism class that occurs. If L is a set, then the result
returned will be a subset of L.
There is no allowance for the specification of vertex sets; each poset
is treated as if it has no isolated vertices.
The procedure may also be applied to lists or sets of directed graphs.
EXAMPLES:
L:=subs({1=a,2=b,3=c,4=d},Posets(4));
L:=[op(Posets(4)),op(L)];
nops(rm_isom(L)); yields 16
SEE ALSO: autgroup, canon, isom
FUNCTION: strongcomps - strongly connected components of a digraph
CALLING SEQUENCE: strongcomps(G); strongcomps(G,'Q');
strongcomps(G,X); strongcomps(G,X,'Q');
strongcomps(G,n); strongcomps(G,n,'Q');
PARAMETERS: G = the edge set of a directed graph
X = a set (the vertex set of G)
n = a positive integer (the number of vertices)
Q = a name (optional)
SYNOPSIS:
If G is a directed graph with vertex set X, strongcomps(G,X) returns
a list of sets that partition X into strongly connected components.
Two vertices x and y belong to the same strongly connected component if
and only if there is a directed path in G from x to y and y to x.
The components are listed in an order consistent with G: if there is
an edge [x,y] in which x belongs to the i-th component and y belongs to
the j-th component, then i <= j (as integers).
strongcomps(G,n) does the same, if the vertex set of G is {1,...,n}.
strongcomps(G) does the same, assuming that G has no isolated vertices.
Optionally, if the last argument is an unassigned name, such as Q, then
in addition to returning a list of strongly connected components of G,
the procedure assigns to Q the edge set of the acyclic directed graph
induced by G on the components: [i,j] is an edge in Q if i<>j and there
is an edge [x,y] of G such that x belongs to the i-th component and y
belongs to the j-th component.
Use 'covers' to extract the covering relation of the poset Q generates.
EXAMPLES:
G:={[a,b],[b,c],[c,a],[0,a],[c,1]};
strongcomps(G,'Q'),Q; yields [{0},{a,b,c},{1}], {[1,2],[2,3]}
P:=J({},3); P:={op(P),[8,3],[2,1]};
strongcomps(P); yields [{1,2},{5},{6},{3,4,7,8}]
strongcomps(P,9,'Q'); yields [{9},{1,2},{5},{6},{3,4,7,8}]
covers(Q); yields {[2,3],[3,4],[4,5]}
SEE ALSO: connected, covers
FUNCTION: subinterval - extract a subinterval from a poset
CALLING SEQUENCE: subinterval(P,[a,b]);
subinterval(P,X,[a,b]);
subinterval(P,n,[a,b]);
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
a,b = vertices of P, or a = -infinity, or b = infinity
SYNOPSIS:
Let P be a poset with vertex set X. If a and b are vertices in X such
that a <= b in P, then subinterval(P,X,[a,b]) returns the subposet of P
formed by the vertices c in X such that a <= c <= b.
If a = -infinity (resp., b = +infinity), then the subposet formed by
the vertices c <= b (resp., c >= a) is returned.
Otherwise, if either a or b is not a vertex in X, or if it is not true
that a <= b in P, then NULL is returned.
If the subposet Q to be returned has no relations (and thus has a single
vertex c), then the poset structure {},{c} is returned.
subinterval(P,n,[a,b]) does the same, if P has vertex set {1,...,n}.
subinterval(P,[a,b]) does the same, if P has no isolated vertices.
EXAMPLES:
P:=chain(2) &* chain(3);
subinterval(P,[1,4]); yields {[1,2],[1,3],[2,4],[3,4]}
subinterval(P,[-infinity,5]); yields {[1,3],[3,5]}
subinterval(P,[2,5]); yields NULL
subinterval(P,7,[7,infinity]); yields {}, {7}
SEE ALSO: subposet
FUNCTION: subposet - extract an induced subposet from a poset
CALLING SEQUENCE: subposet(P,Y);
subposet(P,X,Y);
subposet(P,n,Y);
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
Y = a subset of the vertex set
SYNOPSIS:
Let P be a poset with vertex set X. If Y is a subset of X, then the
subposet of P induced by Y is the poset with vertex set Y and relations
x < y for every x,y in Y such that x < y in P.
subposet(P,X,Y) returns (the covering relation of) the subposet of P
induced by Y. An error is signaled if Y is not a subset of X.
subposet(P,n,Y) does the same, if {1,...,n} is the vertex set of P.
subposet(P,Y) does the same, assuming P has no isolated vertices.
EXAMPLES:
P:=chain(2) &* chain(3);
subposet(P,{1,2,4,5}); yields {[1,2],[2,4],[1,5]}
subposet(P,8,{1,4,5,7}); yields {[1,4],[1,5]}
SEE ALSO: subinterval
FUNCTION: W - W-polynomial of a poset
CALLING SEQUENCE: W(P,q,t,<options>);
W(P,X,q,t,<options>);
W(P,n,q,t,<options>);
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
q,t = variable names or expressions
<options> = any of the following, in any order:
(1) 'ideals' or 'linear' (specifying an algorithm)
(2) a subset of P (specifying descent positions)
SYNOPSIS:
Let P be a poset with a vertex set X of size n. A labeling L of P may
be viewed as an assignment of distinct integers to the vertices in P.
The labeling is "natural" if x < y in P implies L[x] < L[y].
For each linear extension w of P (see 'extensions'), define
D(L,w) = { 1 <= i <= n : L[w[i]] > L[w[i+1]] },
using the convention that L[w[n+1]] = -infinity.
It follows that D(L,w) always includes n (assuming n>0).
The W-polynomial of (P,L) may be defined as the generating series
W(q,t) = SUM q^Sum(D(L,w)) * t^|D(L,w)|,
where w ranges over all linear extensions of P.
The W-polynomial depends only on P and the "descent set" of L; i.e.,
the set of all covering pairs x < y in P such that L[x] > L[y].
In other words, two labelings of P with the same descent set yield the
same W-polynomial. In particular, all natural labelings of P (the case
of an empty descent set) yield the same W-polynomial.
W(P,X,q,t) returns the W-polynomial of P evaluated at q,t, relative
to a natural labeling of P.
W(P,n,q,t) does the same, if the vertex set of P is {1,...,n}.
W(P,q,t) does the same, assuming that P has no isolated vertices.
To compute the W-polynomial of P relative to an arbitrary labeling L,
the descent set S of the labeling may be optionally provided as an
additional argument. This set must be a subset of P (i.e., a subset of
the covering relation of the poset). If there is no labeling of P
corresponding to the given descent set S, an error is signaled.
Two algorithms are provided for computing W-polynomials: 'linear' and
'ideals'. The 'linear' algorithm has minimal space requirements and a
running time that is linear in the number of linear extensions of P.
The 'ideals' algorithm is more appropriate for larger posets, and has
worst-case running times that are quadratic in the number of order
ideals of P. If neither algorithm is specified, the default is to use
the 'linear' option for posets with <= 6 vertices, and the 'ideals'
option otherwise.
Note that when the W-polynomial is evaluated at (q,t)=(1,1), the result
is the number of linear extensions of P. In this case (i.e., when the
supplied values for q and t are both 1), the procedure ignores any
optional arguments and calls a special subroutine for fast counting of
linear extensions.
It can be shown that
2 n s m
W(q,t) = (1-t)(1-q t)(1-q t)...(1-q t) * SUM N[s,m] * q t,
where N[s,m] is the number of order-reversing maps f from P to the
m-element chain 1 < 2 < ... < m such that
(1) the sum of f(x) over all x in X is s,
(2) f(x) > f(y) whenever L[x] > L[y].
In particular, specializing to the case q=1, one obtains
W(1,t) = (1-t)^(n+1) * SUM Ord(m) * t^m,
where Ord(m) is the order polynomial of P relative to L (see 'omega').
Relative to a natural labeling, the W-polynomial of P is the flag
h-polynomial of J(P,X) in the variables z[i]=q^i*t (see 'flag_h'),
and W(1,t) is the ordinary h-polynomial of J(P,X) (see 'h_poly').
EXAMPLES:
f:=W({},4,q,1);
factor(f); yields q^4*(q^2+q+1)*(q^2+1)*(q+1)^2
P:=chain(2) &* chain(3);
W(P,q,t,{[1,2],[5,6]}); yields
q^9*t^2 + q^11*t^3 + 2*q^12*t^3 + q^13*t^3
W({[a,b],[a,c]},{a,b,c,d},1,t,'ideals');
yields t + 5*t^2 + 2*t^3
W(chain(9),q,t,'linear',{[1,2],[3,4],[5,6]});
yields q^18*t^4
P:=chain(7) &* chain(7);
W(P,1,1); yields 475073684264389879228560
SEE ALSO: extensions, flag_h, h_poly, ideals, J, omega
FUNCTION: zeta - zeta polynomial of a poset
CALLING SEQUENCE: zeta(P,t);
zeta(P,X,t);
zeta(P,n,t);
PARAMETERS: P = a poset
X = a set (the vertex set)
n = a positive integer (the number of vertices)
t = a variable name or expression
SYNOPSIS:
The zeta polynomial of a poset P with vertex set X is the unique
polynomial Z(t) such that for every integer m>1, Z(m) is the number of
weakly increasing sequences x[1] <= x[2] <= ... <= x[m-1] in P.
In particular, Z(2) is the number of vertices, and Z(3) is the number
of (weakly) related pairs.
zeta(P,X,t) returns the zeta polynomial of the poset P, evaluated at t.
zeta(P,n,t) does the same, if the vertex set of P is {1,...,n}.
zeta(P,t) does the same, assuming that P has no isolated vertices.
The zeta polynomial is related to the chain polynomial (see 'chains')
as follows: Z(m) is the sum of c_k * binomial(m-2,k-1) for k >= 1,
where c_k denotes the number of k-element chains in P.
The order polynomial of P (see 'omega') is the zeta polynomial of J(P).
If P has a minimum element 0 and a maximum element 1, then the zeta
polynomial Z(t) has several significant features:
(1) Z(m) is the number of weakly increasing chains of length m
from 0 to 1; i.e., 0 <= x[1] <= ... <= x[m-1] <= 1.
(2) Z(m) is the sum of f_k * binomial(m,k), where f_k denotes the
number of chains of length k from 0 to 1 (see also 'f_poly').
(3) Z(-1) is the value of the mobius function on the interval
from 0 to 1; i.e., zeta(P,-1)=mobius(P,[0,1]).
EXAMPLES:
zeta({[a,b],[b,c]},{a,b,c,d},q); yields 1+1/2*q+1/2*q^2
zeta(J({},3),t); yields t^3
P:=({},1) &+ ({},3) &+ ({},1);
zeta(P,-1); yields 2
SEE ALSO: chains, f_poly, mobius, omega