%
% This is a plain TeX file. 
%
\hsize=5.4truein\hoffset=0.55truein
\vsize=7.5truein\voffset=0.75truein
\font\bold=cmbx10 at 14pt
\font\small=cmr8
\vglue 0.4truein
\centerline{\bold A Maple Package for Posets}
\smallskip
\centerline{\bf Version 1}
\smallskip
\centerline{August 8, 1991}
\bigskip
\centerline{John R. Stembridge\footnote{$^1$}{\small
  Partially supported by NSF Grants DMS--9057192 and DMS--9101898.}}
\centerline{Department of Mathematics}
\centerline{University of Michigan}
\centerline{Ann Arbor, Michigan 48109--1003}
\centerline{Internet: jrs@math.lsa.umich.edu}
\bigskip

\def\mysec#1{\bigskip\centerline{\bf #1}\nobreak\par}
\def\subsec#1{\medskip\noindent{\it #1}.\nobreak}
\def\maple{{\sl Maple}}
\def\cite#1{~[{\bf #1}]}
\def\pos{{\tt posets}}
\def\lb{{\char'173}}
\def\rb{{\char'175}}

{\openup 1\jot
\mysec{1. Introduction}
The \pos{} package consists primarily of 22 \maple{} programs that aid in the
manipulation of partially ordered sets. It also includes a library of posets
with 7 or fewer vertices and lattices with 9 or fewer vertices, as well as a
collection of several sample applications and supplementary procedures.  I'm
not about to claim that this package can answer every computational question
about posets, but there are a few things that it does well. I find it to be 
especially useful when studying questions of the form ``Does every poset in
class $X$ satisfy property $Y$?'' It is also good at performing operations
on posets, and for computing various poset invariants. If it doesn't do what
you want, there's a good chance you can build the procedures you need out of
the raw materials provided here.

I also do not claim that any of the algorithms I've used here are particularly
spectacular. A few of them are mildly clever, but since I'm not a computer
scientist, I don't have to be embarrassed when my algorithms are not
``state-of-the-art.'' If you are looking to squeeze the best possible
performance out of your hardware, you should probably be writing your own
code, and using something like {\sl c} or {\sl lisp}, not this package.

The purpose of this document is to give an overview of the workings of the
package, explain the types of data structures used, and to define a few
fundamental items of terminology. Installation details are given elsewhere.

\mysec{2. Share Library}
The version of the \pos{} package in the {\sl\maple~4.3} share library is
distributed as follows.
The file {\tt posets} contains the package itself.
The file can be loaded using the {\tt read} command.
The directory {\tt help} contains plain text help files.

The share library version differs from the original version in two significant
ways. First, only the core package of 22 procedures have been distributed, not
the supplementary procedures or sample applications. Secondly, the mechanism
for accessing lists of non-isomorphic posets and lattices has been modified.
Instead of reading these lists from pre-stored files, the lists are generated
and stored in ``remember'' tables whenever they are first requested. On a
Sun~4 running {\sl\maple~V}, it takes about 10 minutes to generate the list of
posets on seven elements.

\mysec{3. System Requirements}
I started developing this package with {\sl\maple~4.2}, later with
{\sl\maple~4.3}, and now with {\sl\maple~V}. Although I've attempted to keep
all of the code compatible with version~4.2, I no longer have a copy of~4.2 to
run tests with. I would appreciate hearing from~4.2 users who discover
significant incompatibilities.  (I already know of a relatively trivial one.
There are a few places in the {\tt /examples}  and {\tt /lib} subdirectories
where the {\tt interface} command is used to enter and exit the {\tt quiet}
mode. Ignoring these will not have serious consequences.)

\mysec{4. Definitions}
A {\it partially ordered set} (or poset) is a pair $P=(X,<)$ consisting of a
set $X$ of vertices, and a binary relation $<$ on $X$ satisfying the following
two conditions:
\item{1.} (antisymmetry) $x<y$ and $y<x$ are never both true for any
  $x,y\in X$.
\item{2.} (transitivity) $x<y$ and $y<z$ imply $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 unique least upper bound (i.e., an element $z$ satisfying the conditions
$x\le z$, $y\le z$, and $x,y\le v\Rightarrow z\le v$) and a unique greatest
lower bound. 

The poset $P$ is said to be {\it naturally labeled} if the set $X$ comes
equipped with a total ordering that is consistent with $P$; i.e., $x<y$ in $P$ 
implies $x<y$ in the total ordering of~$X$. For example, if $X$ is a set of
integers, then $P$ is naturally labeled if for every relation $i<j$ the
integer $i$ is smaller than the integer $j$.

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\to y$ for every related pair $x<y$. The digraph corresponding
to the covering relation of a poset is the so-called {\it Hasse diagram}, and
is the traditional means of representing posets graphically. 

Let $S\subset X$ be the set of minimal elements of $P$, or equivalently, the
set of sources in the Hasse diagram. We say that the poset $P$ is {\it ranked}
if for every $x\in X$, all paths in the Hasse diagram from $S$ to $x$ have
the same length. Some authors define ranked posets differently, and there is
also a similar (but not identical) notion of a {\it graded} poset. However,
all of these conflicting notions are in agreement when restricted to the
class of posets having unique maximal and minimal elements.

Most of the other terminology which we have not explicitly defined here or
in the {\tt help} files can be found in Chapter~3 of Stanley's book\cite{3}.
Other standard references are\cite{2} for posets and\cite{1} for lattices.

\mysec{5. The Data Structures}
The first question faced by anyone developing code for manipulating posets
is how to represent them. One has to worry about the usual trade-offs
involving space and speed.  I think the choice I've made in this regard is
fairly reasonable, but it has an aesthetic defect I'll need to explain.%
\footnote{$^2$}{\small Apologies to any computer scientist who may be reading
  this.}

For virtually all purposes, the \pos{} package represents a poset $P$ as the
set of ordered pairs of vertices corresponding to the covering relation of $P$.

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 $a<b$, $b<c$, $a<d$, and
$a<c$. Note that the pair {\tt [a,c]} is not listed, since it is not
part of the covering relation---it {\it is} one of the relations of the
poset, however.  You can recover all of the relations implied by transitivity
via the {\tt closure} command in the \pos{} package. Conversely, if you have
an acyclic relation that is transitive, or even partially transitive, you can
recover the covering relation via the {\tt covers} command. This brings up
another significant point: many of the procedures in the \pos{} package,
including {\tt closure} and {\tt covers}, can be applied to arbitrary acyclic
digraphs, not just the covering relations of posets. 

The vertices can be anything you like, but preferably they should be
nonnegative integers or unassigned names. You're asking for trouble if you
try to use something like {\tt x+y} or {\tt \lb a,[b,c]\rb} as the name of
a vertex.

Now we come to the ``defect'' I alluded to before; namely, how did I know
in the example above that the vertex set was $\{a,b,c,d\}$? What if the
poset I was really interested in had the same set of relations, but used
the vertex set $\{a,b,c,d,e\}$? The problem is that this method of
representation has no way of providing for the fact that a poset might
have isolated vertices; i.e., some vertices of $P$ might not be related to
any of the other vertices. 

To get around this defect, the procedures in this package that accept
posets as part of their input are flexible. For example, take the procedure
{\tt antichains}, whose purpose is to produce the set of all antichains
(sets of totally unrelated vertices) of a poset~$P$. If the poset has no
isolated vertices, then the only piece of information I need to pass to the
procedure is the set of covering pairs. Thus, the \maple{} commands

\line{\qquad\tt P:=\lb[a,b],[b,c],[a,d]\rb;\hfill}
\line{\qquad\tt antichains(P);\hfill}

\noindent
would suffice. However, {\tt antichains} and many of the other procedures
allow you to specify the vertex set of your poset as a second argument. Thus,
if I wanted to specify the vertex set $\{a,b,c,d,e\}$, this could be done via
the \maple{} commands

\line{\qquad\tt X:=\lb a,b,c,d,e\rb;\hfill} 
\line{\qquad\tt antichains(P,X);\hfill}

\noindent
Since it is often convenient to use $\{1,2,\ldots,n\}$ as a vertex set,
one is also allowed to use the integer {\tt n} as a second argument. Thus the
\maple{} command {\tt antichains(P,5);} would specify that $P$ is the set of
covering pairs of some poset with vertex set $\{1,2,3,4,5\}$.

\mysec{6. Overview of the Package}
Assuming that installation has been completed, the \maple{} command {\tt
with(posets);} will load the package. You could also load just one of the
procedures via the command {\tt with(posets,%
{\rm$\langle$function$\rangle$});}. The main procedures are:
$$\hbox{\vbox{\settabs 6\columns {\tt
\+J&          antichains& covers    & height    & omega\cr
\+Lattices&   chain     & dual      & invariants& permfit\cr
\+Posets&     char\_poly& extensions& isom      & rm\_isom\cr
\+W&          closure   & filter    & mobius    & zeta\cr}}}$$

Here is a brief indication of what each procedure does. For the full details,
including syntax, definitions, and examples, consult the {\tt /help}
subdirectory.

\subsec{Accessing the library}
\par{\tt Posets}. For a given integer $n\le7$, produces a complete list of
  nonisomorphic posets on $n$ vertices.
\par{\tt Lattices}. For a given integer $n\le9$, produces a complete list of
  nonisomorphic lattices on $n$ vertices.

\subsec{Some useful invariants}
\par{\tt omega, W, zeta} produce the order polynomial, $W$-polynomial, and
  zeta polynomial of a poset.
\par{\tt mobius} produces the m\"obius function of a poset.
\par{\tt char\_poly} produces the characteristic polynomial of any poset with
  a unique minimal element.

\subsec{Some useful structures associated with posets}
\par{\tt antichains} produces the set of antichains of a poset.
\par{\tt extensions} produces the set of linear extensions of a poset.
\par{\tt closure, covers} produce the transitive closure or covering relation
  of any acyclic digraph.

\subsec{Isomorphism testing and related procedures}
\par{\tt isom} tests two posets (or acyclic digraphs) for isomorphism.
\par{\tt rm\_isom} remove isomorphic duplicates from a list of posets or
  acyclic digraphs.
\par{\tt height} produces the length of the longest path in an acyclic digraph.
\par{\tt filter} produces a ``filtration'' of a poset or acyclic digraph.
  Also can be used to decide if a poset is ranked.
\par{\tt invariants} partitions the vertices of a poset into types that are
  invariant under isomorphism.
\par{\tt permfit} produces sets of permutations that fit certain requirements.
  (Used by {\tt isom} and {\tt rm\_isom}.)

\subsec{Procedures that create posets}
\par{\tt J} produces the lattice of order ideals of a poset.
\par{\tt chain} produces a chain (totally ordered poset) of specified length.
\par{\tt dual} produces the dual of a poset (or digraph).
\par{\tt \&+, \&*} ordinal sums and direct products of posets.
\medskip

Whenever the \pos{} package is loaded, the two neutral operators {\tt \&+} and
{\tt \&*} are defined.  These are binary in-fix operators for ordinal sum and
direct product. For example, \hbox{\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$.  The documentation for these operators can be found in the files
{\tt help/ord\_sum} and {\tt help/product}.

The source listings for all of the above procedures can be found in the
{\tt /src} subdirectory.

In addition to the procedures in the package itself, there are a number of
other useful procedures in the {\tt /examples} subdirectory. These must be
explicitly loaded by the user. There are also a number of extended 
applications of the \pos{} package stored in subdirectories of {\tt /examples}.
Documentation is provided in the directories themselves. Included among the
procedures in {\tt /examples} are the following.

\par{\tt allrealzeros} determines if all zeros of a polynomial are real.
\par{\tt divisor} produces the lattice of divisors of an integer $n$.
\par{\tt has\_cycles} determines if a directed graph has any cycles.
\par{\tt join, meet} compute meets and joins in a lattice.
\par{\tt lattice} determines if a given poset is a lattice.
\par{\tt partition} produces the lattice of partitions of a finite set.

Finally, there are two more procedures, {\tt gen\_Posets} and
{\tt gen\_Lattices}, in the {\tt /lib} subdirectory that can be used to 
reproduce the library of posets and lattices. \maple~4.2 users will have to
run these procedures since the new `{\tt .m}' file format is incompatible
with the old one.

\mysec{7. Bugs}
The \pos{} package does very little error trapping or testing for validity of
the input. One particularly gruesome danger is that many of the procedures
that accept posets or digraphs as input will enter an infinite loop if
the user submits a digraph containing a cycle, such as
{\tt \lb[a,b],[b,c],[c,a]\rb}.

Please send reports of bugs to my e-mail address on page~1.  Before reporting
the bug, please try to send me a reproducible example, and try to verify
that it is genuinely a bug in the \pos{} package, rather than \maple.

\mysec{8. The Future}
Obviously there are a lot of things one could add to the package. Here are
some things that I've at least thought about: (1) add a plotting heuristic
so that one could use {\tt plot} to graph a poset, (2) add more procedures
for producing particularly interesting posets, such as Bruhat orders, 
subspace lattices, or Ferrers posets, (3) add procedures for producing
subposets of given posets, and (4) extending the library to posets on~8
vertices and lattices on~10 vertices. To do (4) will require modifying the
existing algorithms so that \maple's capacity is not exceeded. It will also
require a fairly large amount of memory.

If this package proves to be useful in your own research, I would 
appreciate an acknowledgment in publications derived from that research.

\mysec{9. Copyleft}
Copyleft \copyright 1991 by John R. Stembridge.

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

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

\mysec{References}
{\frenchspacing\raggedbottom
\def\myref#1{\item{[{\bf #1}]}}
\myref{1}
  G. Birkhoff, {\it Lattice Theory,} 3rd ed., Amer. Math. Soc.,
  Providence, 1967.
\myref{2}
  I. Rival, {\it Ordered Sets,} Reidel, Dordrecht-Boston, 1982.
\myref{3}
  R. P. Stanley, {\it Enumerative Combinatorics, Vol. I,} Wadsworth \&
  Brooks/Cole, Monterey, CA, 1986.
\par}
\end