## Information on Ideals of Partially Ordered Sets

A partially ordered set **P** = (**<**,*S*)
is a reflexive, transitive relation
on a set *S*.
Another name for partially ordered set is *poset*.
In the Object Server we assume that the set *S* consists of
[*n*] = {1,2,...,*n*}, the first *n* integers.
An *ideal*, *I*, of a poset **P** is a subset
of the elements of **P** that satisfies the following
property: If *y* in *I* and *x < y*,
then *x* in *I*.
For the poset whose Hasse diagram is shown above the ideals
are {}, {1}, {3}, {1,2}, {1,3}, {3,4}, {1,2,3}, {1,3,4}, {1,2,3,4}.

If Gray code output is requested, then each ideal
differs from its predecessor by one or two elements.

It is a #P-complete problem to count the number of
ideals of a poset.
See ???.

For "lex" order, the algorithm used is from the paper
G. Steiner, *An Algorithm to Generate the Ideals of a
Partial Order*, Operations Research Letters, 5 (1986) 317-320.
If Gray code output is requested, then the algorithm used
is from the paper:
G. Pruesse and F. Ruskey,
Gray Codes from Antimatroids, Order,
10 (1993) 239-252.

## Ideals of Special Posets

### Disjoint chains

If the poset consists of *k* disjoint chains, where the
*i*-th chain contains *n*_{i} elements,
then the number of ideals is
(1+*n*_{1})(1+*n*_{2}) ···
(1+*n*_{k}).
### The fence poset

The fence poset is defined by the relations (*i*-1,*i*),
(*i*+1,*i*) for odd *i*.
The number of ideals of a *n* element fence poset is given by the
*n*-th Fibonacci number, *F*_{n}.

Programs available:

**Questions??** Email
The wizard of COS.

(Please note that the suffix XXXX must be removed from the preceeding
email address.)

It was last updated Wednesday, 10-May-2006 10:32:14 PDT.

[Error Opening Counter File -- Click for more info]

©Frank Ruskey, 1995-2003.