%
% This is a plain TeX file. 
%
\hsize=5.4in\hoffset=0.55in
\vsize=7.5in\voffset=0.75in
%
\font\bold=cmbx10 scaled\magstep2
\font\small=cmr8
\font\smtt=cmtt8
\font\smb=cmbx8
%
\centerline{\bold A Maple Package for Posets}
\medskip
\centerline{\bf Version 2}
\medskip
\centerline{August 26, 1994}
\bigskip
\centerline{John R. Stembridge\footnote{$^*\!\!$}{\small
  Partially supported by NSF grants DMS--9057192 and DMS--9401575.}}
\centerline{Department of Mathematics}
\centerline{University of Michigan}
\centerline{Ann Arbor, Michigan 48109--1003 USA}
\medskip
\centerline{Internet: jrs@math.lsa.umich.edu}

\def\mysec#1{\bigskip\centerline{\bf #1}\nobreak\par}
\def\subsec#1{\medskip\noindent{\it #1}.\nobreak}
\def\cite#1{[{\bf #1}]}
\def\ttline#1{\line{\tt\qquad #1\hfil}}
\def\ss#1{$\scriptstyle #1$}
\def\fnote#1#2{\footnote{$^{#1}\!\!$}{\openup -2\jot\small #2\par}\ }
\skip\footins=1.5\medskipamount
\def\lb{{\char'173}}  % {
\def\rb{{\char'175}}  % }
\def\up{{\char'136}}  % ^
\def\ul{{\char'137}}  % _
\def\bitem{\item{$\bullet$}}
\def\pos{{\tt posets}}
\def\homelib{/usr/local/maple/packages}
\def\br#1{\langle #1\rangle}

\mysec{Contents}
\item{1.} Introduction
\item{2.} System Requirements
\item{3.} Getting Started
\item{4.} Some Definitions
\item{5.} Data Structures
\item{6.} Short Synopses of the Procedures
\item{7.} What's New in Version 2
\item{8.} Further Remarks
\item{9.} Copyleft
\item{10.} References

{\openup 1\jot
\mysec{1. Introduction}
This document is an introduction to Version 2 of \pos, a package of~32 Maple
programs that provide an environment for computations involving partially
ordered sets and related structures. The package is particularly useful for
visualization of posets and for computing various poset invariants, such as
M\"obius functions. Also included is a library containing all 19,449 posets
with $\le 8$ vertices and all 7,372 lattices with $\le 10$ vertices---this is
convenient for investigating questions of the form ``Which posets in class $X$
satisfy property $Y$?''.

There are numerous improvements that have been incorporated into this second
version of \pos, including:

\bitem Many new functions, including a procedure for plotting posets.
\bitem An expanded library.
\bitem Faster and more space-efficient code.
\bitem Help texts are now available on-line.

\noindent There have also been numerous changes in how the package operates
(all are improvements, of course!). This is discussed in detail in \S7.

\mysec{2. System Requirements: UNIX and {\sl Maple~V}}
At a minimum, you will need {\sl Maple~V} (Release~1 or later). In Release~1,
the procedure for plotting posets is disabled, since it uses graphics features
that were added in Maple V Release~2.

In addition, although there is no reason that the package cannot be run on
any system with {\sl Maple~V}, I much prefer to develop software in a UNIX
environment, and this initial release of Version~2 is designed specifically
for installation in such an environment. Hence, users of non-UNIX systems
will have to do some nontrivial work in order to install the package on their
systems. In the near future, I may release a version for installation on a
Macintosh. Also, the \pos{} package will probably appear in the Maple Share
Library at some point (Version~1 is there currently). When that happens, you
should be able to run \pos{} on any hardware that runs Maple.

In the meantime, in order to acquire and unpack the software for \pos,
you will need access to a UNIX machine and the Internet. If you send a
message to the e-mail address on page~1, I will send you instructions for
obtaining it by anonymous {\tt ftp} or via the World Wide Web.

\mysec{3. Getting Started}
Let's assume that the \pos{} package has been unpacked and compiled according
to the instructions that are supplied with it. If your system manager has
done this for you, then you'll need to find out the name of the directory
where the package has been installed. For the purposes of this discussion,
let's assume that the directory name is {\tt\homelib}. You can check this by
verifying that {\tt\homelib} has a subdirectory named \pos.

Next, you will need to create a file named {\tt .mapleinit} in your home
directory. Or add to it, if you already have one.\fnote{1}{Users who are
already running one of my previous packages can skip this step.}
In this file you should insert the following lines of Maple code:

\medskip\noindent
For Maple~V, Release 1:
\smallskip
\ttline{HomeLib:=`\homelib`:}
\ttline{\ul{}liblist:=[HomeLib]:}
\smallskip
\noindent For Maple~V, Release 2 or later:\hfil\break
\ttline{HomeLib:=`\homelib`:}
\ttline{libname:=libname, HomeLib:}
\noindent Be careful to correctly type the left quotation marks and underscore
character.  Each time Maple is invoked, these statements will define where the
packages are located.

You are now ready to run the \pos{} package. Simply type {\tt with(posets);}
during a Maple session. To access documentation about the individual commands,%
\fnote{2}{The help mechanism in Maple~V Release~1 is designed so that the
help text for an external function must be explicitly defined during a
Maple session (yuck). Instead of having every {\smtt posets} session
cluttered with the help text of every command (or even {\smtt readlib}-%
definitions), the {\smtt posets} package is designed so that the only help
that is initially defined is for {\smtt posets} itself. However, this help
file has a hidden ``trigger'' that causes all of the help texts for the
individual commands in the package to be {\smtt readlib}-defined whenever 
help is requested. The net effect is that the first time you request help
of the form {\smtt ?posets[<function>]}, it will fail to locate the text,
and instead return the predefined help for {\smtt posets}. But this releases
the ``trigger'' that defines all of the {\smtt posets} help texts, so that
subsequent help requests will succeed.\hfil\break\indent Users of Maple~V
Release~2 or 3 can be grateful that it has a more sophisticated help mechanism
that allows help texts to be loaded on demand.} use

\ttline{?posets[<function>]\quad{\rm or}\quad ?posets,<function>\rm .}

\noindent The source code for \pos{} is located in

\ttline{\homelib/posets/src\rm ,}

\noindent the poset library is located in

\ttline{\homelib/posets/lib\rm ,}

\noindent and the raw text for the on-line help is located in

\ttline{\homelib/help/posets\rm .}

\noindent A few additional files of examples and simple applications can be
found in the directory

\ttline{\homelib/posets/examples\rm .}

\medskip The rest of this document is concerned with giving an overview of
the workings of the package, explaining the types of data structures used,
and defining a few fundamental items of terminology. A short explanation of
the purpose of each of the commands is provided in \S6. For more detailed
information about the individual commands, consult the on-line help.

\mysec{4. Some Definitions}
We first summarize some of the basic definitions in the theory of finite
partially ordered sets and lattices. Standard references include~\cite{1},
\cite{3}, and Chapter~3 of~\cite{5}. We refer the reader to these sources
for the terminology which we have not explicitly defined here or in the
on-line help.

A {\it partially ordered set} (or poset) is a pair $P=(X,<)$ consisting of a
(finite) set $X$ of vertices, and a binary relation $<$ on $X$ satisfying the
following for all $x,y,z\in X$:
\item{1.} Anti-reflexivity: $x\not<x$.
\item{2.} Transitivity: $x<y$ and $y<z$ implies $x<z$.
\par\noindent The notation $x\le y$ is an abbreviation for `$x<y$ or $x=y$'.

The poset $P$ is said to be a {\it lattice} if every pair $x,y\in X$ has
a least upper bound (i.e., an element $z$ satisfying the conditions
$x\le z$, $y\le z$, and $x,y\le z'\Rightarrow z\le z'$) and a greatest
lower bound. In such cases, the least upper bound of $x$ and $y$ is also
known as the {\it join} of $x$ and $y$, and the greatest lower bound is also
known as the {\it meet}.

A vertex $y$ is said to {\it cover} vertex $x$ (in $P$) if $x<y$ and there
is no $z\in X$ such that $x<z<y$. Note that the transitive closure of the
covering relation yields the partial order~$<$, so the covering relation 
completely determines $P$.

It is sometimes useful to think of $P$ as a directed graph having vertex set
$X$ and arcs $x\gets y$ for every related pair $x<y$. The {\it Hasse diagram}
of $P$ is a planar embedding of the digraph corresponding to the covering
relation of $P$ with the property that whenever $x<y$, the vertical
coordinate of $x$ is less than the vertical coordinate of $y$.

We define a poset $P$ to be {\it ranked} if there is an integer-valued 
function $r:X\to{\bf Z}$ (the rank function) such that $r(y)-r(x)=1$
whenever $y$ covers $x$. Note that in~\cite{5}, a poset is defined to be
{\it graded} if all maximal chains (i.e., maximal vertex sequences satisfying
 $x_1<\cdots<x_n$ in $P$) have the same length. It is not hard to show that
graded posets are ranked, and also that the converse is false. However, among
posets having exactly one maximal and minimal element (e.g., lattices), the
properties of being graded or ranked are equivalent.

A {\it linear extension} of $P$ is an ordering $w=(w_1,\ldots,w_n)$ of the
vertex set of $P$ with the property that $w_i < w_j$ in $P$ implies $i<j$.

Although it does not seem to be a standard notion in the literature, another
important construct for the \pos{} package is the {\it filtration} of a poset.
This is an ordered partition $(F_1,F_2,\ldots,F_r)$ of the vertex set $X$,
defined so that $F_1$ is the set of minimal elements of~$X$, $F_2$ is the
set of minimal elements of $X-F_1$, $F_3$ is the set of minimal elements of
$X-(F_1\cup F_2)$, and so on. One can similarly define the filtration of 
an acyclic digraph, replacing ``minimal elements'' with ``sinks'' (vertices
of outdegree~0).

Two functions in the package, {\tt omega} and {\tt W}, make use of the
notion of a {\it labeling} of a poset $P=(X,<)$ as in~\cite{4}. By this we
mean an injective map $\lambda:X\to{\bf Z}$ that assigns integer labels to
the vertices. Two labelings of the poset $P$, say $\lambda$ and $\lambda'$,
are said to be {\it equivalent} if
$$
\lambda(x)>\lambda(y)\Leftrightarrow\lambda'(x)>\lambda'(y)
$$
for all $x,y\in X$ such that $y$ covers $x$. The equivalence class of a
labeling $\lambda$ is therefore determined by the set of pairs $(x,y)$ such
that $y$ covers $x$ and $\lambda(x)>\lambda(y)$. A labeling is {\it natural}
if this set is empty; i.e., $x<y$ implies $\lambda(x)<\lambda(y)$.

A $(P,\lambda)$-{\it partition} is a mapping $f:X\to\{1,2,\ldots\}$
such that for all $x<y$ in $X$, we have (1) $f(x)\ge f(y)$, and
(2) $\lambda(x)>\lambda(y)\Rightarrow f(x)>f(y)$.

The {\it order polynomial} of the pair $(P,\lambda)$ is the unique polynomial
$\Omega(P,\lambda;t)$ with the property that for all integers $m>0$,
$\Omega(P,\lambda;m)$ equals the number of $(P,\lambda)$-partitions $f$
such that $f(x)\le m$ for all $x\in X$. It can be shown that the order
polynomial of $(P,\lambda)$ depends only on the equivalence class of
$\lambda$. Note also that if $\lambda$ is a natural labeling, then
$\Omega(P,\lambda;m)$ equals the number of order-reversing (or equivalently,
order-preserving) maps from $P$ to an $m$-element chain. 

Assume that the poset $P$ has $n$ vertices. We define the $W$-{\it polynomial}
of the pair $(P,\lambda)$ by means of the power series expansion
$$
{W(P,\lambda;q,t)\over(1-qt)(1-q^2t)\cdots(1-q^nt)}=
  \sum_fq^{S(f)}t^{\max(f)},\eqno(*)
$$
where $S(f)=\sum_{x\in X}f(x)$ and the sum ranges over all $(P,\lambda)$-%
partitions $f$. It is true, but not clear from the definition, that
$W(P,\lambda;q,t)$ is a polynomial function of $q$ and $t$. Indeed, it can be
shown that
$$
W(P,\lambda;q,t)=\sum_{w\in L(P)}q^{n+\hbox{\small ind}(w,\lambda)}
  t^{d(w,\lambda)+1},
$$
where $L(P)$ denotes the set of linear extensions of $P$, ind$(w,\lambda)$
denotes the sum of the indices $i$ such that $\lambda(w_i)>\lambda(w_{i+1})$,
and $d(w,\lambda)$ denotes the number of such indices.

From~$(*)$, it follows that the order- and $W$-polynomials are related as
follows:$$
{W(P,\lambda;1,t)\over(1-t)^{n+1}}=\sum_{m\ge0}\Omega(P,\lambda;m)t^m.
$$
It is worth remarking that one of the original motivations that led me to
develop the \pos{} package was to test the Neggers-Stanley Conjecture~%
\cite{2}; namely, the conjecture that for every labeling $\lambda$ of every
(finite) poset $P$, all zeroes of the polynomial $W(P,\lambda;1,t)$ are real.%
\fnote{3}{Using the package, we have verified the conjecture for all labelings
of posets with $\scriptstyle\le 7$ vertices, and all natural labelings of
posets with~8 vertices.} $^4$\fnote{}{\vskip-.30in\textindent{$^4\!\!$}
The package was also instrumental in the development of the
``3+1 Conjecture'' of~[{\smb 6},$\,$\S5].}

\eject
\mysec{5. Data Structures}
There are several data structures that have special meanings for the \pos{}
package.

\subsec{Posets}
The package represents a poset $P$ as the set of ordered pairs of vertices
corresponding to the covering relation of $P$.\fnote{5}{This is a slight lie,
as we shall see in a moment.} This yields (in my opinion) a reasonable
compromise among space, speed, and convenience.

For example, the Maple expression {\tt \lb[a,b],[b,c],[a,d]\rb} represents
a poset on four vertices $\{a,b,c,d\}$ in which the covering relations are
$a<b$, $b<c$, and $a<d$. Note that transitivity implies $a<c$, but the pair
{\tt [a,c]} is not listed in the expression, since it is not part of the
covering relation.

One can recover all of the relations implied by transitivity via the
{\tt closure} command in the \pos{} package. Conversely, given an acyclic
relation that is transitive, or merely partially transitive, one can recover
the covering relation via the {\tt covers} command.

The vertices of a poset must be integers or names.

\subsec{Poset Structures}
There is an apparent defect in the way we have chosen to represent posets.
Continuing the above example, how did I know that the vertex set was
$\{a,b,c,d\}$? What if the vertex set was intended to be $\{a,b,c,d,e\}$,
with the vertex $e$ being unrelated to any of the other vertices? Indeed,
given the possibility of isolated vertices, there is no certain way to
recover the vertex set of a poset from its set of covering pairs.

To cope with these situations, the \pos{} package has the following more
general data structure. Suppose that {\tt P} is a Maple expression representing
the set of covering pairs of a poset $P$, as before. A {\it poset structure} 
for $P$ is a Maple expression sequence of one of the following three forms:

\item{1.} {\tt P}
\item{2.} {\tt P, X} \quad(where {\tt X} is a set)
\item{3.} {\tt P, n} \quad(where {\tt n} is a positive integer)

\noindent The first form can be used only when the poset $P$ has no isolated
vertices, the second when the vertex set is {\tt X}, and the third when the
vertex set is {\tt \lb1,2,...,n\rb}. Thus

\ttline{\lb[a,b],[b,c],[a,d]\rb}
\ttline{\lb[a,b],[b,c],[a,d]\rb, \lb a,b,c,d,e\rb}
\ttline{\lb[2,3],[2,4],[3,5],[4,5]\rb, 6}

\noindent are all valid examples of poset structures.

All posets in the package must have non-empty vertex sets. Thus {\tt \lb\rb}
and {\tt \lb\rb,\lb\rb} are not valid poset structures, but {\tt \lb\rb,1} and
{\tt \lb\rb,\lb a,b\rb} are valid. (Using a poset with~0 vertices will not
cause any fatal errors; we simply make no guarantee that the output returned
will conform to your expectation of the ``correct'' answer in such cases.)

Every procedure in the \pos{} package that accepts a poset as part of its input
will also accept any poset structure.\fnote{6}{A quasi-exception to this rule
is the procedure {\smtt rm\ul{}isom}, which accepts lists or sets of covering
relations of posets, but not individual posets.} For example, consider the
function {\tt antichains}, whose purpose is to produce the set of all
antichains (sets of totally unrelated vertices) of a poset~$P$. Any of the
calling sequences 

\ttline{antichains(P);}
\ttline{antichains(P,X);}
\ttline{antichains(P,n);}

\noindent can be used to produce the set of antichains of $P$. Of course,
the first form can be used only if $P$ has no isolated vertices.

Conversely, some of the procedures that produce posets as output, notably
{\tt chain}, {\tt subinterval} and the operators {\tt \&u}, {\tt \&+}, and
{\tt \&*} will return poset structures of the form {\tt P,X\ }
or {\ \tt P,n\ } in situations where isolated vertices occur.

\subsec{Acyclic Digraphs}
Many of the procedures in the \pos{} package, namely,
$$
\hbox{\tt\vbox{\settabs 4\columns
\+automorphisms  & closure     & connected  & covers\cr
\+dual           & extensions  & filter     & isom\cr
\+plot\ul{}poset & rm\ul{}isom & subinterval\cr}}
$$
can be applied to arbitrary acyclic digraphs, not just the covering relations
of posets. (Here, the function {\tt connected} is applied to the underlying
{\it undirected} graph.)

An acyclic digraph $D$ is represented in the \pos{} package as a set of
ordered pairs. For example, the Maple expression {\tt\lb[a,b],[b,c],[a,c]\rb}
represents the acyclic digraph with vertex set $\{a,b,c\}$, and arcs
$a\gets b$, $b\gets c$, $a\gets c$. As with posets, the above procedures
also accept what could be called ``acyclic digraph structures'' of the form
\hbox{\tt D,X} or \hbox{\tt D,n}, specifying that the vertex set of {\tt D}
is {\tt X} or {\tt\lb1,2,...,n\rb}, respectively.

It is useful to be aware that for general digraphs (possibly with cycles),
the function {\tt filter} returns the filtration of the acyclic part of
the digraph; i.e., the digraph obtained by deleting all vertices that belong
to a directed cycle. Thus the Boolean expression

\ttline{nops(filter(D,X)) = nops(X)}

\noindent provides a simple test for whether the digraph {\tt D} is acyclic.

\subsec{Labelings of posets} (This is relevant only for the functions
{\tt omega} and {\tt W}.) In the \pos{} package, one specifies a labeling 
$\lambda$ for a poset {\tt P} (recall the discussion in Section~4) by means of
the subset {\tt S} of {\tt P} consisting of those covering pairs {\tt [x,y]}
such that $\lambda({\tt x})> \lambda({\tt y})$; recall that this set
determines the labeling up to equivalence. In particular, to compute the
order polynomial or $W$-polynomial, one uses the calling sequences

\ttline{omega(P,t,S);}
\ttline{W(P,q,t,S);}

\noindent If the set {\tt S} is omitted, then the default value is
{\tt S=\lb\rb}, which corresponds to a natural labeling. If there is no
labeling of {\tt P} whose corresponding {\tt P}-subset is {\tt S}, then 
an error will occur when calling {\tt W} or {\tt omega}.

\mysec{6. Short Synopses of the Procedures}
Here is a brief indication of the purpose of each procedure in \pos. For the
full details, including syntax, definitions and examples, consult the on-line
help via the command {\tt ?posets,<function>\ } or {\ \tt ?posets[<function>]}.

\medskip
\settabs\+\tt {\tt automorphisms}\ \ &\cr
\+\tt antichains& antichains of a partially ordered set\cr
\+\tt atomic& test for atomicity of a lattice\cr
\+\tt automorphisms& automorphisms of a poset (or acyclic digraph)\cr
\+\tt chain& total order of specified length\cr
\+\tt char\ul{}poly& characteristic polynomial of a (graded) poset\cr
\+\tt closure& transitive closure of an acyclic digraph\cr
\+\tt connected& connected components and connectivity test for posets\cr
\+\tt covers& covering relation of an acyclic digraph\cr
\+\tt distributive& test distributivity of lattices\cr
\+\tt dual& dual of a poset (or directed graph)\cr
\+\tt extensions& linear extensions of a poset (or acyclic digraph)\cr
\+\tt filter& filtration of a poset (or acyclic digraph)\cr
\+\tt isom& test posets (or acyclic digraphs) for isomorphism\cr
\+\tt J& lattice of order ideals of a poset\cr
\+\tt lattice& test posets for the lattice and semi-lattice properties\cr
\+\tt Lattices& list of nonisomorphic lattices\cr
\+\tt meet& compute meets in a lattice, maximal lower bounds in a poset\cr
\+\tt mobius& M\"obius function of a poset\cr
\+\tt modular& test modularity and semi-modularity of lattices\cr
\+\tt omega& order polynomial of a poset.\cr
\+\tt plot\ul{}poset& plot posets (or acyclic directed graphs)\cr
\+\tt Posets& list of nonisomorphic posets\cr
\+\tt rand\ul{}poset& random poset generator\cr
\+\tt ranked& test whether a poset is ranked\cr
\+\tt rm\ul{}isom& remove isomorphic copies from a list of posets\cr
\+\tt subinterval& extract subintervals from posets\cr
\+\tt subposet& extract induced subposets from a poset\cr
\+\tt W& $W$-polynomial of a poset\cr
\+\tt zeta& zeta polynomial of a poset\cr

\medskip
When the \pos{} package is loaded, the following neutral operators are defined:
\smallskip
\settabs\+\tt \qquad\qquad& direct product of posets\quad&\cr
\+\tt \&u& disjoint union of posets &(for help, see
  {\tt posets[disj\ul{}union]})\cr
\+\tt \&+& ordinal sum of posets &(for help, see {\tt posets[ord\ul{}sum]})\cr
\+\tt \&*& direct product of posets &(for help, see {\tt posets[product]})\cr
\smallskip\noindent
These are binary in-fix operators---thus {\tt P \&+ Q} will return the ordinal
sum of~$P$ and~$Q$, and {\tt P \&* Q \&* R} will return the direct product
of~$P$, $Q$ and~$R$.

\medskip
Here is a short summary of the contents of the {\tt examples}
directory. These files must be explicitly loaded by the user.

\medskip
\settabs\+\tt {\tt young\ul{}lattice}\ \ &\cr
\+\tt bruhat\ul{}order& Bruhat order of a finite reflection group$^{*}$\cr
\+\tt divisor& lattice of divisors of an integer\cr
\+\tt dominance& dominance order on partitions of an integer$^{\dag}$\cr
\+\tt par\ul{}lattice& lattice of partitions of a set\cr
\+\tt weak\ul{}order& weak order (and Cayley graph) of a finite reflection
  group$^{*}$\cr
\+\tt young\ul{}diag& Young diagram of a (skew) partition\cr
\+\tt young\ul{}lattice& Young's lattice$^{\dag}$\cr

\medskip\noindent
The files {\tt bruhat\ul{}order} and {\tt weak\ul{}order} require that the
{\tt coxeter} package has been installed. Similarly, {\tt dominance} and
{\tt young\ul{}lattice} require the {\tt SF} package. (Both packages are
available in the Maple Share Library.)

\mysec{7. What's New in Version 2}
There are numerous changes in functionality that have been incorporated into
Version~2 of the \pos{} package, including:

{\raggedright
\bitem There are 13 new procedures: {\tt atomic}, {\tt automorphisms},
{\tt connected}, {\tt distributive}, {\tt \&u} (disjoint union), {\tt lattice},
{\tt meet}, {\tt modular}, {\tt plot\ul{}poset}, {\tt rand\ul{}poset},
{\tt ranked}, {\tt subinterval}, and {\tt subposet}.\par}

\bitem Almost all of the existing procedures are significantly faster and
more space-efficient. Several, including {\tt antichains}, {\tt isom},
{\tt Lattices}, {\tt omega}, {\tt Posets}, and {\tt W}, have new features.

\bitem Every procedure is consistent in its use of poset structures. Also,
a poset structure is now an expression sequence, not a list.

\bitem Filtering digraphs with cycles will no longer cause Maple to crash.

\bitem The library now has the 16,999 posets with 8 vertices and the 5,994
lattices with 10 vertices. The storage method (and ordering) of posets within
the library is new.

\bitem The {\tt examples} directory has been completely redesigned.

\bitem The procedures {\tt permfit} and {\tt invariants} have been renamed
{\tt `posets/permfit`} and {\tt `posets/invariants`} and are now internal
to the package.

\bitem The procedure {\tt height} has been removed from the package. A
functional replacement is {\tt proc() nops(filter(args)) end}.

\bitem The {\tt W} function now computes a two-variable polynomial attached
to a (labeled) poset. The old {\tt W} function is recovered by taking $q=1$.

\bitem {\tt rm\ul{}isom} now returns a sublist (or subset) of the input.

\bitem {\tt filter} no longer accepts the optional flag {\tt 'ranked'}. This
option is subsumed by the new procedure {\tt ranked}.
 
\mysec{8. Further Remarks}
\subsec{Plotting posets}
I've tested {\tt plot\ul{}poset} on both color and monochrome displays. After
some experimentation,\fnote{7}{Using X/Motif and a Sony Trinitron monitor.}
I've settled on {\tt red} and {\tt white} as the best choice of default colors
for the edges and vertices, respectively. However, I realize that your
mileage may vary, so the default color choices can be changed, either during
a Maple session, or permanently. (They can also be passed as arguments to
{\tt plot\ul{}poset}.) To change the default colors during a Maple session,
use (for example) the assignments

\ttline{`posets/default`[ecolor]:=magenta;}
\ttline{`posets/default`[vcolor]:=yellow;}

\noindent {\it after} loading the \pos{} package via the {\tt with} command.
To change the default colors permanently, edit the file {\tt src/posets} and
then recompile it. The color choices seem to have no effect on monochrome
displays.

\subsec{Using the library}
The library is accessed via the functions {\tt Posets} and {\tt Lattices}.
The list of posets on 8 vertices (and to a lesser extent, the list of lattices
on 10 vertices) is so large that using it severely taxes the capacity of
Maple.$^8$\fnote{}{\vskip-.30in\textindent{$^8\!\!$} As explained in the
installation instructions, it is recommended that low-end machines use a
smaller version of the library, omitting the 8 point posets and 10 point
lattices.} For example, even an operation as simple as
{\tt map(nops,Posets(8))} requires Maple to allocate about 3MB of memory.
Also, one must be especially wary about constructing {\tt do}-loops involving
lists as large as {\tt Posets(8)}. For example, a computation of the form

\ttline{keepers:=NULL;}
\ttline{for P in list\ul{}of\ul{}posets do}
\ttline{\quad if is\ul{}interesting(P) then keepers:=keepers,P fi}
\ttline{od:}
\ttline{keepers:=[keepers]:}

\noindent has a running time that is quadratic in the number of items in
{\tt list\ul{}of\ul{}posets}, and is virtually unusable for lists whose
sizes are in the range of {\tt Posets(8)}. On the other hand, the above
computation could be rewritten using {\tt map} or {\tt seq} so that the
running time is linear. To encourage such practices, the {\tt Posets}
and {\tt Lattices} commands optionally accept a Boolean procedure for
selecting sublists from the library satisfying a given property. Thus an 
efficient way to select the ``interesting'' posets on~8 points would be

\ttline{keepers:=Posets(8,is\ul{}interesting):}

\subsec{Isomorphism testing} There is no known polynomial-time algorithm
for poset isomorphism (it is also not known whether it is NP Complete), so
don't expect miracles from the {\tt isom} function. Of course, ``random''
posets are very easy to distinguish; the troublesome cases are the posets
with nontrivial automorphism groups and large numbers of vertex orbits.

\subsec{Bugs}
Please send reports of reproducible bugs to the e-mail address on page~1.
Be sure to include an example, preferably as small as possible. Note that
the package at present does only a small amount of error-trapping for legal
input.

\subsec{Mailing list} I maintain a mailing list of users of \pos{} and my
other packages {\tt SF}, {\tt coxeter}, and {\tt weyl}. If you would like to
be kept informed of new versions, new packages, or (God forbid) bugs, please
send a message to the e-mail address on page~1, and I will add you to the list.

\subsec{Compensation}
If the \pos{} package proves to be useful in your own research, I would
appreciate an acknowledgment of it in publications derived from that research.

\vfill\eject
\mysec{9. Copyleft}
Copyleft \copyright 1991, 1994 by John R. Stembridge.

Permission is granted to anyone to use, modify, or redistribute this
software freely, subject to the following restrictions:\medskip

{\openup -1\jot
\item{1.} The author accepts no responsibility for any consequences of this
software and makes no guarantee that the software is free of defects.
\smallskip
\item{2.} The origin of this software must not be misrepresented, either by
explicit claim or by omission.
\smallskip
\item{3.} This notice and the copyleft must be included in all copies or
altered versions of this software.
\smallskip
\item{4.} This software may not be included or redistributed as part of any
package to be sold for profit without the explicit written permission of the
author.\par}
\par}

\mysec{10. References}
{\frenchspacing\raggedbottom
\def\myref#1{\smallskip\item{[{\bf #1}]}}
\myref{1}
  G. Birkhoff, {\it Lattice Theory,} 3rd ed., Amer. Math. Soc.,
  Providence, 1967.
\myref{2}
  F. Brenti, Unimodal, log-concave and Polya frequency sequences in
  combinatorics, {\it Mem. Amer. Math. Soc.} (1989), no. 413.
\myref{3}
  I. Rival, {\it Ordered Sets,} Reidel, Dordrecht-Boston, 1982.
\myref{4}
  R. P. Stanley, Ordered structures and partitions, {\it Mem. Amer. Math.
  Soc.} (1972), no.~119.
\myref{5}
  R. P. Stanley, {\it Enumerative Combinatorics, Vol. I,} Wadsworth \&
  Brooks/Cole, Monterey, CA, 1986.
\myref{6}
  R. P. Stanley and J. R. Stembridge, On immanants of Jacobi-Trudi matrices and
  permutations with restricted position, {\it J. Combin. Theory Ser. A}
  {\bf 62} (1993), 261--279.
\par}
\end
