info prev up next book cdrom email home

Ideal (Partial Order)

An ideal $I$ of a Partial Order $P$ is a subset of the elements of $P$ which satisfy the property that if $y\in I$ and $x<y$, then $x\in I$. For $k$ disjoint chains in which the $i$th chain contains $n_i$ elements, there are $(1+n_1)(1+n_2)\cdots(1+n_k)$ ideals. The number of ideals of a $n$-element Fence Poset is the Fibonacci Number $F_n$.


References

Ruskey, F. ``Information on Ideals of Partially Ordered Sets.'' http://sue.csc.uvic.ca/~cos/inf/pose/Ideals.html.

Steiner, G. ``An Algorithm to Generate the Ideals of a Partial Order.'' Operat. Res. Let. 5, 317-320, 1986.




© 1996-9 Eric W. Weisstein
1999-05-26