For a detailed introduction to the package, consult the TeX document "A Maple Package for Posets." 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 formfunctionname(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

© 2009 John R. Stembridge