[Information Index] [Generation Index] [COS homepage]

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.

[covers=1<2&3<4] 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 ni elements, then the number of ideals is (1+n1)(1+n2) ··· (1+nk).

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, Fn.

Programs available:
[Information Index] [Generation Index] [COS homepage]
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.
There have been 3123 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.